背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读四个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》。

当前阅读周书籍：《数据结构与算法JavaScript描述》。

列表

列表的抽象数据类型定义

列表是一组有序的数据。每个列表中的数据项称为元素。在JavaScript中，列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有事先限定，实际使用时元素的数量受到程序内存的限制。

不包含任何元素的列表称为空列表。列表中包含元素的个数称为列表的length。在内部实现上，用一个变量listSize保存列表中元素的个数。可以在列表末尾append一个元素，也可以在一个给定元素后或列表的起始位置insert一个元素。使用remove方法从列表中删除元素，使用clear方法清空列表中所有的元素。

还可以使用toString()方法显示列表中所有的元素，使用getElement()方法显示当前元素。列表拥有描述元素位置的属性。列表有前有后（分别对应front和end）。使用next()方法可以从当前元素移动到下一个元素，使用prev()方法可以移动到当前元素的前一个元素。还可以使用moveTo(n)方法直接移动到指定位置，这里的n表示要移动到第n个位置。currPos属性表示列表中的当前位置。

表1-1：列表的抽象数据类型定义

实现列表类

根据上面定义的列表抽象数据类型，可以直接实现一个List类。让我们从定义构造函数开始，虽然它本身并不是列表抽象数据类型定义的一部分：

function List() {
  this.listSize = 0;
  this.pos = 0;
  this.dataStore = []; //初始化一个空数组来保存列表元素
  this.clear = clear;
  this.find = find;
  this.toString = toString;
  this.insert = insert;
  this.append = append;
  this.remove = remove;
  this.front = front;
  this.end = end;
  this.prev = prev;
  this.next = next;
  this.hasNext;
  this.hasPrev;
  this.length = length;
  this.currPos = currPos;
  this.moveTo = moveTo;
  this.getElement = getElement;
  this.contains = contains;
}

append：给列表添加元素

该方法给列表的下一个位置增加一个新的元素，这个位置刚好等于变量listSize的值：

function append(element) {
  this.dataStore[this.listSize++] = element;
}

当新元素就位后，变量listSize加1。

remove：从列表中删除元素

remove()方法是cList类中较难实现的一个方法。首先，需要在列表中找到该元素，然后删除它，并且调整底层的数组对象以填补删除该元素后留下的空白。

function find(element) {
  for (var i = 0; i < this.dataStore.length; ++i) {
    if (this.dataStore[i] == element) {
      return i;
    }
  }
  return -1;
}

find：在列表中查找某一元素

find()方法通过对数组对象dataStore进行迭代，查找给定的元素。如果找到，就返回该元素在列表中的位置，否则返回-1，这是在数组中找不到指定元素时返回的标准值。我们可以在remove()方法中利用此值做错误校验。

remove()方法使用find()方法返回的位置对数组dataStore进行截取。数组改变后，将变量listSize的值减1，以反映列表的最新长度。如果元素删除成功，该方法返回true，否则返回false。代码如下所示：

function remove(element) {
  var foundAt = this.find(element);
  if (foundAt > -1) {
    this.dataStore.splice(foundAt, 1);
    --this.listSize;
    return true;
  }
  return false;
}

length：列表中有多少个元素

length()方法返回列表中元素的个数：

function length() {
  return this.listSize;
}

toString：显示列表中的元素

toString()方法用来显示列表中的元素了：

function toString() {
  return this.dataStore;
}

insert：向列表中插入一个元素

insert()方法需要知道将元素插入到什么位置，因此现在我们假设插入是指插入到列表中某个元素之后。知道了这些，就可以定义insert()方法了：

function insert(element, after) {
  var insertPos = this.find(after);
  if (insertPos > -1) {
    this.dataStore.splice(insertPos + 1, 0, element);
    ++this.listSize;
    return true;
  }
  return false;
}

在实现中，insert()方法用到了find()方法，find()方法会寻找传入的after参数在列表中的位置，找到该位置后，使用splice()方法将新元素插入该位置之后，然后将变量listSize加1并返回true，表明插入成功。

clear：清空列表中所有的元素

clear()方法清空列表中的所有元素，为插入新元素腾出空间：

function clear() {
  delete this.dataStore;
  this.dataStore.length = 0;
  this.listSize = this.pos = 0;
}

contains：判断给定值是否在列表中

当需要判断一个给定值是否在列表中时，contains()方法就变得很有用。下面是该方法的定义：

function contains(element) {
  for (var i = 0; i < this.dataStore.length; ++i) {
    if (this.dataStore[i] == element) {
      return true;
    }
  }
  return false;
}

遍历列表

方法getElement()返回列表的当前元素：

function front() {
  this.pos = 0;
}

function end() {
  this.pos = this.listSize - 1;
}

function prev() {
  --this.pos;
}

function next() {
  if (this.pos < this.listSize) {
    ++this.pos;
  }
}

function currPos() {
  return this.pos;
}

function moveTo(position) {
  this.pos = position;
}

function getElement() {
  return this.dataStore[this.pos];
}

function hasNext() {
  return this.pos < this.listSize;
}

function hasPrev() {
  return this.pos >= 0;
}

让我们创建一个由姓名组成的列表，来展示怎么使用这些方法：

var names = new List();
names.append('Clayton');
names.append('Raymond');
names.append('Cynthia');
names.append('Jennifer');
names.append('Bryan');
names.append('Danny');

现在移动到列表中的第一个元素并且显示它：

names.front();
print(names.getElement()); // Clayton

使用迭代器访问列表

使用迭代器，可以不必关心数据的内部存储方式，以实现对列表的遍历。前面提到的方法front()、end()、prev()、next()和currPos就实现了cList类的一个迭代器。

和使用数组索引的方式相比，使用迭代器的优点；

• 访问列表元素时不必关心底层的数据存储结构。
• 当为列表添加一个元素时，索引的值就不对了，此时只用更新列表，而不用更新迭代器
• 可以用不同类型的数据存储方式实现cList类，迭代器为访问列表里的元素提供了一种统一的方式。

来看一个使用迭代器遍历列表的例子：

for (names.front(); names.hasNext(); names.next()) {
  print(names.getElement());
}

在for循环的一开始，将列表的当前位置设置为第一个元素。只要currPos的值小于列表的长度，就一直循环，每一次循环都调用next()方法将当前位置向前移动一位。

总结

在日常生活中，经常使用列表：待办事项列表、购物清单、十佳榜单、最后十名榜单等。计算机程序也在使用列表，尤其是列表中保存的元素不是太多时。当不需要在一个很长的序列中查找元素，或者对其进行排序时，列表显得尤为有用。反之，如果数据结构非常复杂，列表的作用就没有那么大了。

如何创建一个简单的列表类。首先给出列表的抽象数据类型定义，然后描述如何实现该抽象数据类型（ADT）。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。