JavaScript数据结构与算法之链表

什么是链表

链表是一种线性数据结构，它由一个一个的节点组成，每个节点包含两个部分：当前节点存储的数据，以及指向下一个节点的指针。相比于数组，链表可以实现更加灵活的内存分配，可以动态增加或删除节点，但访问链表中的节点比访问数组要慢。

单向链表

单向链表是最简单的一种链表，它每个节点只有一个指针，指向它的下一个节点。单向链表的尾部节点指针为null，表示链表的结束。

下面是一个单向链表的节点结构的定义：

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

整个链表可以通过第一个节点来访问：

class LinkedList {
  constructor() {
    this.head = null;
  }

  traverse() {
    let curr = this.head;
    while (curr != null) {
      console.log(curr.val);
      curr = curr.next;
    }
  }
}

在一个空链表中插入节点：

const linkedList = new LinkedList();

linkedList.head = new Node(1);
linkedList.head.next = new Node(2);
linkedList.head.next.next = new Node(3);

linkedList.traverse();  // 输出1, 2, 3

在链表尾部添加节点：

const linkedList = new LinkedList();

if (linkedList.head == null) {
  linkedList.head = new Node(1);
} else {
  let curr = linkedList.head;
  while (curr.next != null) {
    curr = curr.next;
  }
  curr.next = new Node(2);
}

linkedList.traverse();  // 输出1, 2

双向链表

双向链表每个节点除了指向下一个节点的指针之外，还有指向上一个节点的指针。双向链表可以方便地反向遍历链表，但同时也需要更多的内存空间来存储指向上一个节点的指针。

下面是一个双向链表的节点结构的定义：

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

双向链表的插入和删除节点与单向链表基本相同，只是需要同时更新新节点和旧节点的指针。

下面是一个在双向链表中插入新节点的例子：

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  append(val) {
    const newNode = new Node(val);
    if (this.head == null) {  // 为空链表
      this.head = newNode;
      this.tail = newNode;
    } else {  // 不为空链表
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
}

const doublyLinkedList = new DoublyLinkedList();

doublyLinkedList.append(1);  // 在尾部添加1
doublyLinkedList.append(2);  // 在尾部添加2
doublyLinkedList.append(3);  // 在尾部添加3

let curr = doublyLinkedList.tail;
while (curr != null) {
  console.log(curr.val);
  curr = curr.prev;
}
// 输出 3, 2, 1

链表优化

链表与数组不同，在获取链表中第n个元素时，需要从链表的头部逐步遍历到第n个元素。因此，如果我们需要频繁地获取链表中的第n个元素，链表的效率就会变得非常低下。

为了避免这种情况，可以在链表中加入一个缓存，用来存储访问过的节点，下次再访问相同节点时就可以直接从缓存中获取，而无需遍历整个链表。这种缓存又称之为LRU缓存。

除了LRU缓存之外，还可以使用其他一些技巧来优化链表，例如使用哨兵节点、使用虚拟头节点等。

小结

链表作为一种经典的数据结构，用来解决一些传统的算法问题非常方便。此外，在编写一些特殊的数据结构时，例如跳表等，也会经常用到链表。

链表的应用非常广泛，而且难度适中，非常适合作为入门算法训练的练习题。