6. 链表

6.1 链表数据结构

要存储多个元素，数组（或列表）可能是最常用的数据结构。正如本书之前提到的，每种语言都实现了数组。这种数据结构非常方便，提供了一个便利的[]语法来访问其元素。然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。（尽管我们已经学过，JavaScript 有来自 Array 类的方法可以帮我们做这些事，但背后的情况同样如此。）

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。在数组中，我们可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素。

• push(element)：向链表尾部添加一个新元素。
• insert(element, position)：向链表的特定位置插入一个新元素。
• getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回 undefined。
• remove(element)：从链表中移除一个元素。
• indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
• removeAt(position)：从链表的特定位置移除一个元素。
• isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
• size()：返回链表包含的元素个数，与数组的 length 属性类似。
• toString()：返回表示整个链表的字符串。由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

import { defaultEquals } from "../util";
import { Node } from "./models/linked-list-models"; // {1}

export default class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.count = 0; // {2} 存储链表中的元素数量
    this.head = undefined; // {3} 定义链条的头节点
    this.equalsFn = equalsFn; // {4} 比较链表中的元素是否相等的函数
  }
  // 向链表尾部添加元素
  push(element) {
    const node = new Node(element); // {1} 创建一个Node，将element作为值传入
    let current; // {2} 定义一个变量，存储当前链表中最后一个元素
    if (this.head == null) {
      // {3} 如果head为null，直接让head指向该元素就可以
      this.head = node;
    } else {
      current = this.head; // {4} current默认指向head
      while (current.next != null) {
        // {5} 获得最后一项
        current = current.next;
      }
      // 将其next赋为新元素，建立链接
      current.next = node; // {6} 让当前（也就是最后一个）元素的next指针指向想要添加到链表的节点
    }
    this.count++; // {7} 递增链表的长度
  }

  // 从链表中移除元素
  removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      // {1} 验证该index是有效的
      let current = this.head; // {2} 获取到链条的头，赋值给current

      // 移除第一项
      if (index === 0) {
        // {3} 如果移除的是第一项，直接将current的next指向头节点就好
        this.head = current.next;
      } else {
        let previous; // {4} 定义变量previous 记录目标节点的上一个节点
        for (let i = 0; i < index; i++) {
          // {5} 遍历整个链表，找到目标节点
          previous = current; // {6} 获取到previous
          current = current.next; // {7} 获取到目标节点的引用
        }
        // 将previous与current的下一项链接起来：跳过current，从而移除它
        previous.next = current.next; // {8} 将目标节点的后一个节点和前一个节点连接起来
      }
      this.count--; // {9} 递减链表的长度
      return current.element;
    }
    return undefined; // {10} index无效，直接返回undefined
  }

  // 循环迭代链表直到目标位置
  getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      // {1} 验证该index是有效的
      let node = this.head; // {2} 获取到链表的头节点
      for (let i = 0; i < index && node != null; i++) {
        // {3} 遍历整个列表，直到找到目标节点
        node = node.next;
      }
      return node; // {4} 返回目标节点
    }
    return undefined; // {5} index无效，直接返回undefined
  }

  // 使用getElementAt重构removeAt
  removeAt2(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      // {1} 验证该index是有效的
      let current = this.head; // {2} 获取到链条的头，赋值给current

      // 移除第一项
      if (index === 0) {
        // {3} 如果移除的是第一项，直接将current的next指向头节点就好
        this.head = current.next;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        // 将previous与current的下一项链接起来：跳过current，从而移除它
        previous.next = current.next; // {8} 将目标节点的后一个节点和前一个节点连接起来
      }
      this.count--; // {9} 递减链表的长度
      return current.element;
    }
    return undefined; // {10} index无效，直接返回undefined
  }

  // 在任意位置插入元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      // {1} 验证该index是有效的
      const node = new Node(element);
      if (index === 0) {
        // 在第一个位置添加
        const current = this.head;
        node.next = current; // {2} 将头节点指向添加的元素
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1); // {3} 获取到插入位置前一个元素
        const current = previous.next; // {4} 获取到目标位置节点
        node.next = current; // {5} 将目标位置节点连接到插入元素后面
        previous.next = node; // {6} 插入元素连接到前一个位置元素后面
      }
      this.count++; // 更新链表的长度
      return true;
    }
    return false; // {7} index无效，直接返回false
  }

  // indexOf方法：返回一个元素的位置
  indexOf(element) {
    let current = this.head; // {1} 获取到头节点位置
    for (let i = 0; i < this.count && current != null; i++) {
      // {2} 遍历整个链表
      if (this.equalsFn(element, current.element)) {
        // {3} 验证current节点的元素和目标元素是否相等
        return i; // {4} 返回找到的元素位置
      }
      current = current.next; // {5} 没有找到，继续迭代
    }
    return -1; // {6} 遍历整个链表也没有找到，返回-1
  }

  // 从链表中移除元素
  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  // 链表长度
  size() {
    return this.count;
  }

  // 链表是否为空
  isEmpty() {
    return this.size() === 0;
  }

  // 获取链表头节点
  getHead() {
    return this.head;
  }

  // toString方法
  toString() {
    if (this.head == null) {
      // {1} 链表为空，直接返回一个空字符串
      return "";
    }
    let objString = `${this.head.element}`; // {2} 获取到头节点
    let current = this.head.next; // {3} 获取到下一个节点
    for (let i = 1; i < this.size() && current != null; i++) {
      // {4} 遍历链表
      objString = `${objString}, ${current.element}`;
      current = current.next;
    }
    return objString; // {5} 返回遍历的结果
  }
}

6.2 双向链表

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素，如下图所示。

先从实现 DoublyLinkedList 类所需的变动开始。

class DoublyNode extends Node {
  // {1}
  constructor(element, next, prev) {
    super(element, next); // {2}
    this.prev = prev; // {3} 新增的
  }
}

class DoublyLinkedList extends LinkedList {
  // {4}
  constructor(equalsFn = defaultEquals) {
    super(equalsFn); // {5}
    this.tail = undefined; // {6} 新增的
  }
}

DoublyLinkedList 类是一种特殊的 LinkedList 类，我们要扩展 LinkedList 类（行{4}）。这表示 DoublyLinkedList 类将继承（可访问）LinkedList 类中所有的属性和方法。一开始，在 DoublyLinkedList 的构造函数中，我们要调用 LinkedList 的构造函数（行{5}），它会初始化 equalsFn、count 和 head 属性。另外，我们也会保存对链表最后一个元素的引用（tail——行{6}）。

双向链表提供了两种迭代的方法：从头到尾，或者从尾到头。我们也可以访问一个特定节点的下一个或前一个元素。为了实现这种行为，还需要追踪每个节点的前一个节点。所以除了 Node 类中的 element 和 next 属性，DoubleLinkedList 会使用一个特殊的节点，这个名为 DoublyNode 的节点有一个叫作 prev 的属性（行{3}）。DoublyNode 扩展了 Node 类，因此我们可以继承 element 和 next 属性（行{1}）。由于使用了继承，我们需要在 DoublyNode 类的构造函数中调用 Node 的构造函数（行{2}）。

在单向链表中，如果迭代时错过了要找的元素，就需要回到起点，重新开始迭代。这是双向链表的一个优势。

在任意位置插入新元素

向双向链表中插入一个新元素跟（单向）链表非常类似。区别在于，链表只要控制一个 next 指针，而双向链表则要同时控制 next 和 prev（previous，前一个）这两个指针。在 DoublyLinkedList 类中，我们将重写 insert 方法，表示我们会使用一个和 LinkedList 类中的方法行为不同的方法。

下面是向任意位置插入一个新元素的算法。

    insert(element, index) {
      if (index >= 0 && index <= this.count) {
        const node = new DoublyNode(element);
        let current = this.head;
        if (index === 0) {
          if (this.head == null) { // {1} 新增的
            this.head = node;
            this.tail = node;
          } else {
            node.next = this.head; // {2}
            current.prev = node; // {3} 新增的
            this.head = node; // {4}
          }
        } else if (index === this.count) { // 最后一项 // 新增的
          current = this.tail; // {5}
          current.next = node; // {6}
          node.prev = current; // {7}
          this.tail = node; // {8}
        } else {
          const previous = this.getElementAt(index -1); // {9}
          current = previous.next; // {10}
          node.next = current; // {11}
          previous.next = node; // {12}
          current.prev = node; // {13} 新增的
          node.prev = previous; // {14} 新增的
        }
        this.count++;
        return true;
      }
      return false;
    }

我们来分析第一种场景：在双向链表的第一个位置（起点）插入一个新元素。如果双向链表为空（行{1}），只需要把 head 和 tail 都指向这个新节点。如果不为空，current 变量将是对双向链表中第一个元素的引用。就像我们在链表中所做的，把 node.next 设为 current（行{2}），而 head 将指向 node（行{4}——它将成为双向链表中的第一个元素）。不同之处在于，我们还需要为指向上一个元素的指针设一个值。current.prev 指针将由指向 undefined 变为指向新元素（node——行{3}）。node.prev 指针已经是 undefined，因此无须更新。

下图演示了这个过程。

现在来分析另一种场景：假设我们要在双向链表最后添加一个新元素。这是一种特殊情况，因为我们还控制着指向最后一个元素的指针。current 变量将引用最后一个元素（行{5}），然后开始建立链接，current.next 指针（指向 undefined）将指向 node（行{6}——基于构造函数的缘故，node.next 已经指向了 undefined）。node.prev 将引用 current（行{7}）。最后只剩一件事了，就是更新 tail，它将由指向 current 变为指向 node（行{8}）。

下图展示了这些行为。

然后还有第三种场景：在双向链表中间插入一个新元素。就像我们在之前的方法中所做的，迭代双向链表，直到要找的位置（行{9}）。getElementAt 方法是从 LinkedList 类中继承的，不需要重写一遍。我们将在 current（行{10}）和 previous 元素之间插入新元素。首先，node.next 将指向 current（行{11}），而 previous.next 将指向 node（行{12}），这样就不会丢失节点之间的链接。然后需要处理所有的链接：current.prev 将指向 node（行{13}），而 node.prev 将指向 previous（行{14}）。下图展示了这一过程。

我们可以对 insert 和 remove 这两个方法的实现做一些改进。在结果为否的情况下，可以把元素插入双向链表的尾部。性能也可以有所改进，比如，如果 position 大于 length/2，就最好从尾部开始迭代，而不是从头开始（这样就能迭代双向链表中更少的元素）。

从任意位置移除元素

从双向链表中移除元素跟链表非常类似。唯一的区别就是，还需要设置前一个位置的指针。我们来看一下它的实现。

    removeAt(index) {
      if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index === 0) {
          this.head = current.next; // {1}
          // 如果只有一项，更新tail // 新增的
          if (this.count === 1) { // {2}
            this.tail = undefined;
          } else {
            this.head.prev = undefined; // {3}
          }
        } else if (index === this.count -1) { // 最后一项 //新增的
          current = this.tail; // {4}
          this.tail = current.prev; // {5}
          this.tail.next = undefined; // {6}
        } else {
          current = this.getElementAt(index); // {7}
          const previous = current.prev; // {8}
          // 将previous与current的下一项链接起来——跳过current
          previous.next = current.next; // {9}
          current.next.prev = previous; // {10} 新增的
        }
        this.count--;
        return current.element;
      }
      return undefined;
    }

我们需要处理三种场景：从头部、从中间和从尾部移除一个元素。

我们来看看如何移除第一个元素。current 变量是对双向链表中第一个元素的引用，也就是我们想移除的元素。我们需要做的就是改变 head 的引用，将其从 current 改为下一个元素（current.next——行{1}），还需要更新 current.next 指向上一个元素的指针（因为第一个元素的 prev 指针是 undefined）。因此，把 head.prev 的引用改为 undefined（行{3}——因为 head 也指向双向链表中新的第一个元素，也可以用 current.next.prev）。由于还需要控制 tail 的引用，我们可以检查要移除的元素是否是第一个元素，如果是，只需要把 tail 也设为 undefined（行{2}）。

下图展示了从双向链表移除第一个元素的过程。

下一种场景是从最后一个位置移除元素。既然已经有了对最后一个元素的引用（tail），我们就不需要为找到它而迭代双向链表。这样也就可以把 tail 的引用赋给 current 变量（行{4}）。接下来，需要把 tail 的引用更新为双向链表中倒数第二个元素（行{5}——current.prev，或者 tail.prev）。既然 tail 指向了倒数第二个元素，我们就只需要把 next 指针更新为 undefined（行{6}——tail.next=null）。下图演示了这一行为。

第三种也是最后一种场景：从双向链表中间移除一个元素。首先需要迭代双向链表，直到要找的位置（行{7}）。current 变量所引用的就是要移除的元素（行{7}）。要移除它，我们可以通过更新 previous.next 和 current.next.prev 的引用，在双向链表中跳过它。因此，previous.next 将指向 current.next（行{9}），而 current.next.prev 将指向 previous（行{10}），如下图所示。

6.3 循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用 undefined，而是指向第一个元素（head），如下图所示。

双向循环链表有指向 head 元素的 tail.next 和指向 tail 元素的 head.prev。

我们来看创建 CircularLinkedList 类的代码。

    CircularLinkedList extends LinkedList {
      constructor(equalsFn = defaultEquals) {
    super(equalsFn);
      }
    }

CircularLinkedList 类不需要任何额外的属性，所以直接扩展 LinkedList 类并覆盖需要改写的方法即可。

我们将在后面重写 insert 和 removeAt 方法的实现。

6.3.1 在任意位置插入新元素

向循环链表中插入元素的逻辑和向普通链表中插入元素的逻辑是一样的。不同之处在于我们需要将循环链表尾部节点的 next 引用指向头部节点。下面是 CircularLinkedList 类的 insert 方法。

    insert(element, index) {
      if (index >= 0 && index <= this.count) {
        const node = new Node(element);
        let current = this.head;
        if (index === 0) {
          if (this.head == null) {
            this.head = node; // {1}
            node.next = this.head; // {2} 新增的
          } else {
            node.next = current; // {3}
            current = this.getElementAt(this.size()); // {4}
            // 更新最后一个元素
            this.head = node; // {5}
            current.next = this.head; // {6} 新增的
          }
        } else { // 这种场景没有变化
          const previous = this.getElementAt(index -1);
          node.next = previous.next;
          previous.next = node;
        }
        this.count++;
        return true;
      }
      return false;
    }

我们来分析一下不同的场景。第一种是我们想在循环链表第一个位置插入新元素。如果循环链表为空，我们就和在 LinkedList 类中一样将 head node 赋值为新创建的元素（行{1}），并且将最后一个节点链接到 head（行{2}）。这种情况下，循环链表最后的元素就是我们创建的指向自己的节点，因为它同时也是 head。

下图展示了第一种情况。

第二种情况是在一个非空循环链表的第一个位置插入元素，因此我们要做的第一件事是将 node.next 指向现在的 head 引用的节点（current 变量）。这是我们在 LinkedList 类中使用过的逻辑。但是，在 CircularLinkedList 中，我们还需要保证最后一个节点指向了这个新的头部元素，所以需要取得最后一个元素的引用。我们可以使用 getElementAt 方法，传入循环链表长度作为参数（行{2}）。我们将头部元素更新为新元素，再将最后一个节点（current）指向新的头部节点（行{3}）。

下图展示了第二种情况。

如果我们想在循环链表中间插入新元素，代码就和在 LinkedList 类中的一样了，因为我们对循环链表的第一个和最后一个节点没有做任何修改。

6.3.2 从任意位置移除元素

要从循环链表中移除元素，我们只需要考虑第二种情况，也就是修改循环链表的 head 元素。removeAt 方法的代码如下。

    removeAt(index) {
      if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index === 0) {
          if (this.size() === 1) {
            this.head = undefined;
          } else {
            const removed = this.head; // {1}
            current = this.getElementAt(this.size()); // {2} 新增的
            this.head = this.head.next; // {3}
            current.next = this.head; // {4}
            current = removed; // {5}
          }
        } else {
          // 不需要修改循环链表最后一个元素
          const previous = this.getElementAt(index -1);
          current = previous.next;
          previous.next = current.next;
        }
        this.count--;
        return current.element; // {6}
      }
      return undefined;
    }

第一个场景是从只有一个元素的循环链表中移除一个元素。这种情况下，我们只需要将 head 赋值为 undefined，和 LinkedList 类中的实现一样。

第二种情况是从一个非空循环链表中移除第一个元素。由于 head 的指向会改变，我们需要修改最后一个节点的 next 属性。那么，我们首先保存现在的 head 元素的引用，它将从循环链表中移除（行{1}）。与我们在 insert 方法中所做的一样，同样需要获得循环链表最后一个元素的引用（行{2}），它会被存储在 current 变量中。在取得所有所需节点的引用后，我们可以开始构建新的节点指向了。先更新 head element，将其指向第二个元素（head.next ——行{3}），然后我们将最后一个 element（current.next）指向新的 head（行{4}）。我们可以更新 current 变量的引用（行{5}），这样就能返回它（行{6}）来表示移除元素的值。

下图展示了这些操作。

6.4 有序链表

有序链表是指保持元素有序的链表结构。除了使用排序算法之外，我们还可以将元素插入到正确的位置来保证链表的有序性。

先来声明 SortedLinkedList 类。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
};
function defaultCompare(a, b) {
  if (a === b) {
    // {1}
    return 0;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; // {2}
}

class SortedLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
    super(equalsFn);
    this.compareFn = compareFn; // {3}
  }
}

SortedLinkedList 类会从 LinkedList 类中继承所有的属性和方法，但是由于这个类有特别的行为，我们需要一个用来比较元素的函数。因此，还需要声明 compareFn（行{3}），用来比较元素。该函数会默认使用 defaultCompare。如果元素有相同的引用，它就返回 0（行{1}）。如果第一个元素小于第二个元素，它就返回-1，反之则返回 1。为了保证代码优雅，我们可以声明一个 Compare 常量来表示每个值。如果用于比较的元素更复杂一些，我们可以创建自定义的比较函数并将它传入 SortedLinkedList 类的构造函数中。

有序插入元素

我们会用下面的代码来覆盖 insert 方法。

    insert(element, index = 0) { // {1}
      if (this.isEmpty()) {
        return super.insert(element, 0); // {2}
      }
      const pos = this.getIndexNextSortedElement(element); // {3}
      return super.insert(element, pos); // {4}
    }

    getIndexNextSortedElement(element) {
      let current = this.head;
      let i = 0;
      for (; i < this.size() && current; i++) {
        const comp = this.compareFn(element, current.element); // {5}
        if (comp === Compare.LESS_THAN) { // {6}
          return i;
        }
        current = current.next;
      }
      return i; // {7}
    }

由于我们不想允许在任何位置插入元素，我们要给 index 参数设置一个默认值（行{1}），以便直接调用 list.insert(myElement)而无须传入 index 参数。如果 index 参数传给了方法，它的值会被忽略，因为插入元素的位置是内部控制的。我们这么做的原因是不想重写整个 LinkedList 类的方法，我们只需要覆盖 insert 方法的行为。如果你愿意，也可以从头创建 SortedLinkedList 类，把 LinkedList 类中的代码复制过来。但是这样会使代码维护变得困难，因为后面要修改代码的话，就需要修改两处而非一处。

如果有序链表为空，我们可以直接调用 LinkedList 的 insert 方法并传入 0 作为 index（行{2}）。如果有序链表不为空，我们会知道插入元素的正确位置（行{3}）并调用 LinkedList 的 insert 方法，传入该位置来保证链表有序（行{4}）。

要获得插入元素的正确位置，我们需要创建一个叫作 getIndexNextSortedElement 的方法。在该方法里，我们需要迭代整个有序链表直至找到需要插入元素的位置，或是迭代完所有的元素。在后者的场景中，返回的 index（行{7}）将是有序链表的长度（元素将被插入在链表的末尾）。我们将使用 compareFn（行{5}）来比较传入构造函数的元素。当我们要插入有序链表的元素小于 current 的元素时，我们就找到了插入元素的位置（行{6}）。

就是这样了！我们可以在内部复用 LinkedList 的 insert 方法。其他方法例如 remove、indexOf 和 on 都和 LinkedList 是一样的。

6.5 创建 StackLinkedList 类

我们还可以使用 LinkedList 类及其变种作为内部的数据结构来创建其他数据结构，例如栈、队列和双向队列。在本节中，我们将学习怎样创建栈数据结构（参考第 4 章）。

StackLinkedList 类结构和 push 与 pop 方法声明如下。

class StackLinkedList {
  constructor() {
    this.items = new DoublyLinkedList(); // {1}
  }
  push(element) {
    this.items.push(element); // {2}
  }
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.removeAt(this.size() - 1); // {3}
  }
}

对于 StackLinkedList 类，我们将使用 DoublyLinkedList 来存储数据（行{1}），而非使用数组或 JavaScript 对象。之所以使用双向链表而不是链表，是因为对栈来说，我们会向链表尾部添加元素（行{2}），也会从链表尾部移除元素（行{3}）。DoublyLinkedList 类有列表最后一个元素（tail）的引用，无须迭代整个链表的元素就能获取它。双向链表可以直接获取头尾的元素，减少过程消耗，它的时间复杂度和原始的 Stack 实现相同，为 O(1)。

我们也可以对 LinkedList 类进行优化，保存一个指向尾部元素的引用，并使用这个优化版本来代替 DoublyLinkedList。

我们可以观察下面的 Stack 方法的代码。

    peek() {
      if (this.isEmpty()) {
        return undefined;
      }
      return this.items.getElementAt(this.size() -1).element;
    }
    isEmpty() {
      return this.items.isEmpty();
    }
    size() {
      return this.items.size();
    }
    clear() {
      this.items.clear();
    }
    toString() {
      return this.items.toString();
    }

我们实际在为每个其他方法调用 DoublyLinkedList 类的方法。在栈的实现内部使用链表数据结构会更加简单，因为不需要重新创建这些代码，也使代码的可读性更好。

我们可以用相同的逻辑用 DoublyLinkedList 来创建 Queue 和 Deque 类，甚至使用 LinkedList 类也是可以的！