列表的抽象数据类型界说

  • 一组有序的数据。
  • 列表中每一项称之为元素
  • 不包括元素的列表称之为空列表
  • 列表有前后（prev/next）
  • 有移动的概念 moveTo
  • 迭代规划办法

与书本上不同的是，咱们运用原型进行完成, 也便是 List 数据结构的一切办法挂载到 List 的原型上,当然仅仅完成了基本功能，没有编程边界处理。

完成列表类 List

  • List 类
function List() {
  this.listSize = 0;
  this.pos = 0;
  this.dataStore = [];
}

看起
看，其是一个简单版别的 List 列表，便是三个特点，下面便是界说操作这三个特点了。

  • 特点：listSize 列表长度
List.prototype.length = function() {
  return this.dataStore;
}
  • 特点： length 长度
List.prototype.length = function() {
  return this.dataStore;
}
  • 办法：append 添加一个元素到列表中
// 添加一个元素
List.prototype.append = function(element) {
  this.dataStore[this.listSize++] = element;
}
  • 办法：find 查找一个元素的方位
List.prototype.find = function(element) {
  for( let i = 0; i < this.dataStore.length; ++i) {
    if(this.dataStore[i] == element) {
      return i
    }
  }
  return -1;
}
  • 办法：remove 一个函数
List.prototype.remove = function(element) {
  let foundAt = this.find(element);
  if(foundAt > -1) {
    this.dataStore.splice(foundAt, 1);
    --this.listSize;
    return true;
  }
  return false
}
  • 办法：在指定方位（after） 刺进元素 element
List.prototype.insert = function (element, after) {
  let insertPos = this.find(after);
  if (insertPos > -1) {
    this.dataStore.splice(insertPos + 1, 0, element);
    ++this.listSize;
    return true;
  }
  return false;
};
  • 办法：clear 清空数据
List.prototype.clear = function() {
  delete this.dataStore;
  this.dataStore.length = 0;
  this.listSize = this.pos = 0;
}
  • 办法：contains 判别给定值是否在列表中
List.prototype.contains = function (element) {
  for (let i = 0; i < this.dataStore.length; ++i) {
    if (this.dataStore[i] == element) {
      return true;
    }
  }
  return false;
};

运用迭代器访问列表

  • 办法：front 节点 pos 放在 start 方位
List.prototype.front = function() {
  this.pos = 0;
}
  • 办法：end 节点 pos 放在 end 方位
List.prototype.end = function() {
  this.pos = this.listSize - 1;
}
  • 办法：prev 节点 pos 方位前移一个方位
List.prototype.prev = function () {
  --this.pos;
};
  • 办法：next 节点 pos 方位后移一个方位
List.prototype.next = function () {
  if (this.pos < this.listSize) {
    ++this.pos;
  }
};
  • 办法： currPos 节点当前方位
List.prototype.currPos = function () {
  return this.pos
}
  • 办法: moveTo 移动到当前节点
List.prototype.moveTo = function (position) {
  this.pos = position
}
  • 办法：getElement 获取指定元素 this.pos
List.prototype.getElement = function () {
  return this.dataStore[this.pos]
}
  • 办法：有下一个
ist.prototype.hasNext = function() {
  return this.pos < this.listSize
}
  • 办法：有上一个
List.prototype.hasPrev = function() {
  return this.pos >= 0
}

其实这些行为便是一个迭代器的概念。

小结

  • 列表与数组的类似，但是列表不是内置支撑，这儿运用 JS 原型 + 阅览有各种有用办法的完成。
  • 这儿没有展示运用实例，了解 数据结构 api 的基本规划。
  • 理解 JavaScript 原型链编程，以及列表的迭代 api 规划。