背景

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

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

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

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

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

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

链表

数组的缺点

数组不总是组织数据的最佳数据结构，原因如下。在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。然而，JavaScript的数组并不存在上述问题，因为使用splice()方法不需要再访问数组中的其他元素了。

JavaScript中数组的主要问题是，它们被实现成了对象，与其他语言（比如C++和Java）的数组相比，效率很低（请参考Crockford那本书的第6章）。

如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。

定义链表

遍历链表，就是跟着链接，从链表的首元素一直走到尾元素（但这不包含链表的头节点，头节点常常用来作为链表的接入点）。

链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。

从链表中删除一个元素也很简单。将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向null，元素就删除成功了。

设计一个基于对象的链表

设计的链表包含两个类。Node类用来表示节点，LinkedList类提供了插入节点、删除节点、显示列表元素的方法，以及其他一些辅助方法。

Node类

Node类包含两个属性：element用来保存节点上的数据，next用来保存指向下一个节点的链接。我们使用一个构造函数来创建节点，该构造函数设置了这两个属性的值：

function Node(element) {
  this.element = element;
  this.next = null;
}

LinkedList类

LList类提供了对链表进行操作的方法。该类的功能包括插入删除节点、在列表中查找给定的值。该类也有一个构造函数，链表只有一个属性，那就是使用一个Node对象来保存该链表的头节点。

该类的构造函数如下所示：

function LList() {
  this.head = new Node('head');
  this.find = find;
  this.insert = insert;
  this.remove = remove;
  this.display = display;
}

head节点的next属性被初始化为null，当有新元素插入时，next会指向新的元素，所以在这里我们没有修改next的值。

插入新节点

在一个已知节点后面插入元素时，先要找到“后面”的节点。为此，创建一个辅助方法find()，该方法遍历链表，查找给定数据。如果找到数据，该方法就返回保存该数据的节点。find()方法的实现代码如下所示：

function find(item) {
  var currNode = this.head;
  while (currNode.element != item) {
    currNode = currNode.next;
  }
  return currNode;
}

find()方法演示了如何在链表上进行移动。首先，创建一个新节点，并将链表的头节点赋给这个新创建的节点。然后在链表上进行循环，如果当前节点的element属性和我们要找的信息不符，就从当前节点移动到下一个节点。如果查找成功，该方法返回包含该数据的节点；否则，返回null。

一旦找到“后面”的节点，就可以将新节点插入链表了。首先，将新节点的next属性设置为“后面”节点的next属性对应的值。然后设置“后面”节点的next属性指向新节点。insert()方法的定义如下：

function insert(newElement, item) {
  var newNode = new Node(newElement);
  var current = this.find(item);
  newNode.next = current.next;
  current.next = newNode;
}

现在已经可以开始测试我们的链表实现了。然而在测试之前，先来定义一个display()方法，该方法用来显示链表中的元素：

function display() {
  var currNode = this.head;
  while (!(currNode.next == null)) {
    print(currNode.next.element);
    currNode = currNode.next;
  }
}

该方法先将列表的头节点赋给一个变量，然后循环遍历链表，当前节点的next属性为null时循环结束。为了只显示包含数据的节点（换句话说，不显示头节点），程序只访问当前节点的下一个节点中保存的数据：

currNode.next.element;

从链表中删除一个节点

从链表中删除节点时，需要先找到待删除节点前面的节点。找到这个节点后，修改它的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。我们可以定义一个方法findPrevious()，来做这件事。该方法遍历链表中的元素，检查每一个节点的下一个节点中是否存储着待删除数据。如果找到，返回该节点（即“前一个”节点），这样就可以修改它的next属性了。findPrevious()方法的定义如下：

function findPrevious(item) {
  var currNode = this.head;
  while (!(currNode.next == null) && currNode.next.element != item) {
    currNode = currNode.next;
  }
  return currNode;
}

现在就可以开始写remove()方法了：

function remove(item) {
  var prevNode = this.findPrevious(item);
  if (!(prevNode.next == null)) {
    prevNode.next = prevNode.next.next;
  }
}

测试remove()方法的程序：

var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
cities.display();
cities.remove('Carlisle');
cities.display();

在调用remove()方法前的输出为：

Conway;
Russellville;
Carlisle;
Alma;

但是Carlisle在阿肯色州的东部，因此我们需要将其从链表中删除，删除之后链表显示成下面这个样子：

Conway;
Russellville;
Alma;

总结

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。

本文分享了一个基于对象的链表的实现。

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