链表

链表和数组类似，是一种线性的数据结构，与数组不同的是，链表中的数据在内存中并不是顺序存储的，而是通过在链表的每个元素中，保存指向下一个元素的引用，来找到下一个元素。 这里的元素我们把它叫作节点，节点后面的节点我们把它叫作后继节点，节点前边的节点我们把它叫作前置节点。 链表的这种特性让我们无法通过索引直接访问节点，但是能够快速的删除和插入节点，因为只需要修改节点的引用。

应用

链表的应用场景有：分布式节点（例如 P2P），文件系统，或作为其它数据结构（如队列）的基础结构。

分类

常用的链表种类有：

• 单链表，单链表是链表的最简单的形式，每个节点都指向下一个节点。
• 双向链表：双向链表在单链表的基础上，每个节点还指向上一个节点。
• 循环列表：在循环列表中，链表的尾部节点会指向头部节点，如果是双向循环列表，头部节点还会指向尾部节点。

常用操作

对于一个单链表，我们只需要保存头部节点的引用，就能找到所有节点，所有的操作都是围绕头部节点操作的。单链表的常见操作有：

• 查找节点，给定一个值，找到对应的节点。
• 在指定节点后面插入新节点，先找到对应位置的节点，让它指向新节点，再让新节点指向查找到的节点后面的节点。
• 在尾部添加节点，找到尾部节点，让尾部节点的下一个节点指向新节点。
• 在头部之前插入节点，让新节点的下一个节点指向原头部节点，再把头部节点引用设置为新的节点。
• 删除指定节点，先找到要删除的节点的前置节点，让它指向要删除的节点的后继节点。
  • 如果删除的是头部节点，还需要把头部节点引用设置为原头部节点后面的节点
• 删除头部节点，把头部节点的引用设置为下一个节点。
• 删除尾部节点，找到尾部节点之前的节点，把它的指向设置为空。
• 遍历链表：从头到尾访问链表中的每一个节点。

JavaScript 实现

基于链表数据结构的特点，我们可以使用一个类来表示一个节点，这里的 Node class 包含两个属性：

• value 节点的数据。
• next 对下一个节点的引用。这里的 next 的值也是一个 Node 对象，所以这是一个递归的结构。

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

之后定义链表 class：

class LinkedList {
  constructor(value) {
    this.head = new Node(value);
  }
}

因为 Node 是递归的结构，对于单链表，我们只需要知道头节点的引用就可以了，所有的节点查找、插入和删除都需要通过头节点来操作，在新建一个链表时，我们通过构造函数接收头节点的值，创建一个 Node 对象，然后保存在 head 属性中，head 就是头部节点的引用。

查找节点

接下来定义查找节点的代码，findNode() ，方法接收要查找的值作为参数，返回查找到的节点，如果没找到则返回 null：

findNode(value) {
  let currentNode = this.head;
  while (currentNode.value !== value) {
    currentNode = currentNode.next;
  }
  if (!currentNode) {
    return null;
  }
  return currentNode;
}

在这个函数里，我们用一个临时变量 currentNode 来保存当前遍历的到的节点，默认为头节点，然后在循环中与 value 值进行比对，如果值不相等，说明还没找到，那么就把 currentNode 设置为下一个节点继续比对，如果值相等，那么 while 循环就会退出，此时的 currentNode 就是找到的节点。如果最后 currentNode 返回了 null，说明访问到了尾部节点的 next，但仍然没找到对应的值。

在指定位置插入节点

下面是在指定位置插入节点的方法，insertAfter()，这个方法接收两个参数，第一个指定在哪个节点的后面插入，这里接收节点的值，第二参数是新节点的值：

insertAfter(value, newValue) {
  const newNode = new Node(newValue);
  const currentNode = this.findNode(value);

  newNode.next = currentNode.next;
  currentNode.next = newNode;
}

在这个方法里面，我们先创建新节点的对象，然后调用 findNode() 方法找到第一个参数 value 值对应的节点，之后把新节点的 next 指向这个节点的后继节点，再把这个节点的后继节点指向新节点，这样新节点就插入到指定节点，以及指定节点的后继节点的中间了。

在尾部追加节点

再来看在链表的尾部追加节点的方法，append()，这个方法接收一个 value 作为参数，指定新节点的值：

append(value) {
  const newNode = new Node(value);
  let currentNode = this.head;
  while (currentNode.next) {
    currentNode = currentNode.next;
  }
  currentNode.next = newNode;
}

在方法中，根据 value 创建一个新节点，然后遍历整个链表，找到尾部节点，这里的逻辑和 findNode() 的类似，不过 while 循环中判断的是 curretNode.next 是否为空，也就是说遍历到的节点如果没有后继节点，那么它就是尾部节点了，最后把尾部节点的 next 指向新节点，这样就完成了在尾部追加节点操作了。

在头部插入节点

再定义从头部插入节点的方法，prepend()，它也接收一个值作为参数，代表新节点的值：

prepend(value) {
  const newNode = new Node(value);
  newNode.next = this.head;
  this.head = newNode;
}

在这个方法里，根据 value 创建节点对象，然后让它的 next 指向现有的头部节点，然后把当前对头节点的引用，head，指向这个新创建的节点，这一步是必须的，否则 head 指向的还是原来的头节点，导致插入失败。

删除指定节点

我们来看删除指定节点的方法，remove()，它接收一个 value 参数，即要删除的节点值：

remove(value) {
  let currentNode = this.head;
  let previousNode = null;

  while (currentNode.value !== value) {
    previousNode = currentNode;
    currentNode = currentNode.next;
  }

  if (currentNode === this.head) {
    this.head = currentNode.next;
  } else {
    previousNode.next = currentNode.next;
  }
}

在方法里，我们需要两个临时变量，一个保存查找到的要删除的节点，一个保存要删除的节点的前置节点，因为删除一个节点需要让该节点的前置节点指向该节点的后置节点。利用 while 循环，找到要删除的节点和它的前置节点，后面有一个 if 判断，如果要删除的是头节点，那么直接让 head 指向它后面的节点就可以了，如果不是头节点，那么就让前置节点指向要删除的节点的后继节点。

删除头部节点

删除头部节点的方法比较简单，我们定义 removeHead()方法，它不接收参数，因为我们知道要删除头部节点，在里边直接让 head 指向头节点的下一个节点：

removeHead() {
  this.head = this.head.next;
}

删除尾部节点

删除尾部节点的方法与删除指定节点的方法类似，我们定义 removeTail 方法，它也不接收参数：

removeTail() {
  let currentNode = this.head;
  let previousNode = null;
  while (currentNode.next) {
    previousNode = currentNode;
    currentNode = currentNode.next;
  }
  previousNode.next = null;
}

在这个方法中，我们找到尾部节点的前置节点，直接把它的 next 设置为空就可以了。

遍历链表

遍历链表的代码和查找节点的几乎一样，在这个 traverse() 方法中，利用 while 循环直接打印出遍历到的节点的值，这样就完成了遍历：

traverse() {
  let currentNode = this.head;
  while (currentNode) {
    console.log(currentNode.value);
    currentNode = currentNode.next;
  }
}

运行示例

我们使用 LinkedList 类来编写一些单链表的操作示例，首先我们初始化一个链表，把头部节点的值设置为 1，此时链表只有一个节点，值为 1：

let list = new LinkedList(1); // 1

然后调用 append() 方法追加 2、3、4 到链表的尾部，此时链表有 4 个节点，分别为 1， 2， 3， 4：

list.append(2);
list.append(3);
list.append(4);
// 1 -> 2 -> 3 -> 4

调用 insertAfter()，传递参数 2 和 5，在节点 2 的后面插入一个节点 5，此时链表有 5 个节点，分别是 1 2 5 3 4：

list.insertAfter(2, 5);

调用 prepend()，传递参数 6，在头部节点前边插入节点 6，此时链表有 6 个节点，分别是 6 1 2 5 3 4：

list.prepend(6);

调用 remove() 方法，传入参数 3，删除值为 3 的节点，此时链表有 5 个节点，分别是 6 1 2 5 4：

list.remove(3);

调用 removeHead() 方法删除头部节点，此时链表有 4 个节点，分别是 1 2 5 4：

list.removeHead();

调用 removeTail() 删除尾部节点，此时链表有 3 个节点，分别是 1 2 5：

list.removeTail();

小结

好了，这个就是单链表数据结构的定义、操作和 JavaScript 实现，对于双向链表我们可以在 Node class 中再用一个 pre 属性保存前置节点的引用，对于循环列表，我们可以在 LinkedList 中再定义一个 tail 属性保存尾部节点，并让尾部节点的 next 属性指向 head 节点，双向循环列表则再让 head 的 pre 指向 tail 就可以了，相关的操作你可一自己实现一下。