数据结构之链表

链表#

链表，一般指的是单向不循环链表，它的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

链表相对于数组，在添加或移除元素的时候不需要移动其他元素，性能很好。但是链表不能直接访问某个元素，需要从表头一个个迭代去查找，此时性能又比较差。

在 JavaScript 中没有内置的链表数据结构，需要手动去实现。

代码实现#

链表一般都是null的, 它的表头head也是不存在的，也为null的，第一个添加的节点会替换掉null成为新的表头，同时它的next也是不存在的，指向null。这样之后，后面增加的节点才会被上一个节点的next指向它。

这里需要考虑到表头为null时情况，需要特殊处理。比如在添加元素时，表头为null则设置为新的节点为表头，表头不为null时，在表头后面添加元素。

为了更好实现链表的其他的功能，我们维护一个虚拟的表头dummyHead，这个表头的element和next都为null，它是不存在的，它在链表实际表头的前面，所以它的next指向的一定是链表的表头，有了这个特性之后，就不用考虑表头为null的情况了，非常方便。

// 链表的节点
class Node {
  constructor(element = null, next = null) {
    this.element = element;
    this.next = next;
  }
}
 
// 链表
class LinkedList {
  constructor() {
    this.dummyHead = new Node(null, null); // 虚拟头部节点
    this.count = 0;
  }
 
  // 获取链表中的元素个数
  size() {
    return this.count;
  }
 
  // 返回链表是否为空
  isEmpty() {
    return this.size() === 0;
  }
 
  // 在链表的 index（0-based）位置添加新的元素 element
  // 在链表中不是一个常用的操作，练习用
  add(index, element) {
    if (index < 0 || index > this.size) {
      throw new Error("Add failed. Illegal index.");
    }
 
    let prev = this.dummyHead;
    for (let i = 0; i < index; i++) {
      prev = prev.next;
    }
 
    prev.next = new Node(element, prev.next);
    this.count++;
  }
 
  // 在链表头添加元素 element
  addFirst(element) {
    this.add(0, element);
  }
 
  // 在链表末尾添加元素 element
  addLast(element) {
    this.add(this.size, element);
  }
 
  // 获得链表第 index（0-based）个位置的元素
  // 在链表中不是一个常用的操作，练习用
  get(index) {
    if (index < 0 || index >= this.size) {
      throw new Error("Get failed. Illegal index.");
    }
 
    let cur = this.dummyHead.next;
    for (let i = 0; i < index; i++) {
      cur = cur.next;
    }
    return cur.element;
  }
 
  // 获得链表的第一个元素
  getFirst() {
    return this.get(0);
  }
 
  // 获得链表的最后一个元素
  getLast() {
    return this.get(this.size - 1);
  }
 
  // 设置链表第 index（0-based）个位置的元素为新元素 e
  // 在链表中不是一个常用的操作，练习用
  set(index, element) {
    if (index < 0 || index >= this.size) {
      throw new Error("Set failed. Illegal index.");
    }
 
    let cur = this.dummyHead.next;
    for (let i = 0; i < index; i++) {
      cur = cur.next;
    }
    cur.element = element;
  }
 
  // 查找链表中是否有元素 element
  contains(element) {
    let cur = this.dummyHead.next;
 
    while (cur !== null) {
      if (cur.element === element) {
        return true;
      }
      cur = cur.next;
    }
    return false;
  }
 
  // 删除链表第 index（0-based）个位置的元素，返回删除的元素
  // 在链表中不是一个常用的操作，练习用
  remove(index) {
    if (index < 0 || index >= this.size) {
      throw new Error("Remove failed. Illegal index.");
    }
 
    let prev = this.dummyHead;
    for (let i = 0; i < index; i++) {
      prev = prev.next;
    }
 
    const retNode = prev.next;
    prev.next = retNode.next;
    retNode.next = null;
    this.count--;
    return retNode.element;
  }
 
  // 删除链表的第一个元素，返回删除的元素
  removeFirst() {
    return this.remove(0);
  }
 
  // 删除链表的最后一个元素，返回删除的元素
  removeLast() {
    return this.remove(this.size - 1);
  }
 
  // 从链表中删除元素 element
  removeElement(element) {
    let prev = this.dummyHead;
 
    while (prev.next !== null) {
      if (prev.next.element === element) {
        break;
      }
      prev = prev.next;
    }
 
    if (prev.next !== null) {
      let delNode = prev.next;
      prev.next = delNode.next;
      delNode.next = null;
      this.count--;
    }
  }
 
  // 转成字符串
  toString() {
    let cur = this.dummyHead.next,
      str = "";
 
    // 遍历节点
    while (cur !== null) {
      str += cur.element + " -> ";
      cur = cur.next;
    }
 
    str += "NULL";
    return str;
  }
}

上面代码实现了链表的增删改查，其中改只能修改指定值之外，其他的 3 种方法都实现了普通的方法，可以任意操作链表的不同位置的节点。下面简单分析下它们的时间复杂度：

增加节点。因为有了虚拟的表头节点，不用考虑特殊情况。需要在哪个索引上增加节点，就遍历到这个索引的节点上，然后插入其中，同时调整一下前后节点的next的指向即可。其中在表头添加节点，是最快的，因为是从表头开始遍历的，只需要遍历一次就能找到节点，时间复杂度为 O(1)。而插入到表尾是最慢的，需要遍历一遍全部的节点，才能找到最后一个节点，在它之后插入节点，时间复杂度为 O(n)。
删除节点。原理和增加节点是一样的，需要在哪个索引删除节点，就遍历到这个索引的节点上，然后删除掉它，同时还调整一下原来节点的前位置的next的指向。同理删除表头位置的节点最快，时间复杂度为 O(1)。表尾位置的节点最慢，时间复杂度为 O(n)。
修改节点。时间复杂度取决于节点的索引位置，因为从链表的表头开始遍历的，修改表头的节点的值自然是最快的，时间复杂度为 O(1)。而修改表尾的节点的值是最慢的，时间复杂度为 O(n)。
查找节点。原理还是和增加节点一样，需要查找哪个索引的节点的值，就遍历到这个索引的节点上，然后获取它的值。同理获取表头位置的节点的值最快，时间复杂度为 O(1)。获取表尾位置的节点的值最慢，时间复杂度为 O(n)。

上面的时间复杂度，只代表当前实现链表的结构的时间复杂度，而不是所有的链表的时间复杂度都是一样的。

虽然实现了增删查的普通方法，但是一般是不会使用的，而是使用addFirst、removeFirst、getFirst这 3 个方法，也就是表头的操作方法，它们的性能非常好，实际复杂度都是 O(1)。

从上面的链表中找到表头的节点是最快的，因为是从表头的节点开始遍历的，而找到表尾节点却是最慢的，有没有方法改善下表尾的查找速度了，答案是肯定的。

可以设置一个表尾的属性tail，然后你直接就可以获取表尾的值，然后可以像上面操作表头一个操作表尾了，时间复杂度是一样的。但是这只适合一些特殊的情况。比如在用链表实现的的队列中，入列的直接从表尾后面添加节点，时间复杂度为 O(1)，出列是删除表头的节点，时间复杂度还是 O(1)，这样的实现的队列性能就和数组一样好。

虽然有了表尾的属性tail，但是如果索引的在链表的具体位置，那还是需要遍历链表才能找到相应的节点的。

其实链表是可以千变万化的，它的结构和规则都由你来自定义，然后它的实现也就变的不一样，实现后的属性和方法也会变得不同。

比如上面结构就只实现了修改指定索引的值，如果不知道索引，只知道节点的值，那么实现就不同了，需要比较每个遍历的节点的值，才能找到该节点，然后修改值。又比如链表中节点的值可以设置成唯一的值，也可以是重复的值，具体要根据实际的使用场景来决定。

代码测试#

下面简单测试下上面实现的链表

let linkedList = new LinkedList();
 
for (let i = 0; i < 5; i++) {
  linkedList.addFirst(i);
  console.log(linkedList.toString());
}
// 0 -> NULL
// 1 -> 0 -> NULL
// 2 -> 1 -> 0 -> NULL
// 3 -> 2 -> 1 -> 0 -> NULL
// 4 -> 3 -> 2 -> 1 -> 0 -> NULL
 
linkedList.add(3, 100);
console.log(linkedList.toString()); // 4 -> 3 -> 2 -> 100 -> 1 -> 0 -> NULL
 
linkedList.remove(3);
console.log(linkedList.toString()); // 4 -> 3 -> 2 -> 1 -> 0 -> NULL
 
linkedList.removeFirst();
console.log(linkedList.toString()); // 3 -> 2 -> 1 -> 0 -> NULL
 
linkedList.removeLast();
console.log(linkedList.toString()); // 3 -> 2 -> 1 -> NULL

其他链表#

上面实现的链表是单向列表，而且还是非循环的。那什么是循环链表呢？就是链表的节点不仅一节一节的连在一起的，而且首位还要相接，形成一个循环，像一个圆圈一样。

这就要求我们的单向链表的最后一个节点不能指向null，而是指向它的头部，可以维护一个属性tail(尾巴) 来表示链表的最后一个节点，this.tail.next = this.head，这样就形成了一个循环。循环链表的表头和表尾连接在一起，在遍历链表的时候，需要注意边界条件，不然可能造成死循环。

除了循环链表之外，还有双向链表，顾名思义，就是链表的节点除了next指向下一个节点外，还有prev属性指向上一个节点，这样链表的每个每个节点都有两个个指向，就是双向链表。双向链表的表头的prev指向null，表尾的next也指向null，这是双向非循环链表。

如果是双向循环链表呢，它的表头的prev指向的是表尾，而表尾的next指向的是表头，这样就形成了一个循环。

另外还有排序链表，即链表的元素是按照一定的顺序（升序或者降序）排列的，这就要求我们在增加和删除元素的时候维护好链表元素的顺序。

总结#

链表和数组一样，都是常见的线性结构，区别于树状结构和图表。而且链表天然的带有递归性，递归操作非常方便。

链表虽然查找和修改元素的时候，性能不是很好，因为它需要遍历节点。但是在添加和删除元素的时候，特别是在表头和表尾节点上添加和删除元素时，性能还不错。

现在已经直到了链表的结构特点，然后在根据实际情况定制细化的结构和规则，可以有效的提高代码的性能。