链表

在计算机科学中，链表是一种数据结构，用于存储和组织元素的集合。与数组不同，链表中的元素不是按照它们在内存中的物理位置顺序存储的。相反，每个元素都包含一个指向下一个元素的引用。链表由一系列节点组成，这些节点一起表示一个序列。

链表最简单的形式是每个节点包含数据和指向下一个节点的引用。这种结构允许在迭代过程中高效地在任何位置插入或删除元素。

更复杂的链表变体添加了额外的链接，允许高效地插入或删除任意元素的引用。链表的一个缺点是访问元素的时间复杂度是线性的（难以进行快速随机访问），而数组具有更好的缓存局部性。

链表的实现通常涉及两个主要的类：LinkedListNode（链表节点）和LinkedList（链表）。

Linked List

链表节点（LinkedListNode）

链表节点表示链表中的一个元素，它包含一个值和一个指向下一个节点的引用。它的实现可以参考下面的代码：

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

链表（LinkedList）

链表是由一系列链表节点组成的数据结构。它具有一个头节点（head）和一个尾节点（tail），分别表示链表的开头和结尾。

链表类提供了一系列方法来操作链表，如在开头插入节点（prepend）、在末尾插入节点（append）、在指定位置插入节点（insert）、删除节点（delete）、查找节点（find）等。以下是链表类的实现代码：

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

  // 在链表尾部添加新节点
  append(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
  }

  // 在链表指定位置插入新节点
  insertAt(value, index) {
    if (index < 0 || index > this.length) {
      throw new Error("Index out of range");
    }

    const newNode = new Node(value);

    if (index === 0) {
      newNode.next = this.head;
      this.head = newNode;
      if (!this.tail) {
        this.tail = newNode;
      }
    } else if (index === this.length) {
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      let currentNode = this.head;
      let prevNode = null;
      let currentIndex = 0;

      while (currentIndex < index) {
        prevNode = currentNode;
        currentNode = currentNode.next;
        currentIndex++;
      }

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

    this.length++;
  }

  // 获取指定位置节点的值
  getAt(index) {
    if (index < 0 || index >= this.length) {
      throw new Error("Index out of range");
    }

    let currentNode = this.head;
    let currentIndex = 0;

    while (currentIndex < index) {
      currentNode = currentNode.next;
      currentIndex++;
    }

    return currentNode.value;
  }

  // 删除指定位置的节点
  removeAt(index) {
    if (index < 0 || index >= this.length) {
      throw new Error("Index out of range");
    }

    let currentNode = this.head;
    let prevNode = null;
    let currentIndex = 0;

    if (index === 0) {
      this.head = currentNode.next;
      if (this.length === 1) {
        this.tail = null;
      }
    } else if (index === this.length - 1) {
      while (currentIndex < index) {
        prevNode = currentNode;
        currentNode = currentNode.next;
        currentIndex++;
      }

      prevNode.next = null;
      this.tail = prevNode;
    } else {
      while (currentIndex < index) {
        prevNode = currentNode;
        currentNode = currentNode.next;
        currentIndex++;
      }

      prevNode.next = currentNode.next;
    }

    this.length--;
  }

  // 遍历链表并将节点值以数组形式返回
  toArray() {
    const result = [];
    let currentNode = this.head;

    while (currentNode) {
      result.push(currentNode.value);
      currentNode = currentNode.next;
    }

    return result;
  }
}

const linkedList = new LinkedList();
linkedList.append(10);
linkedList.append(20);
linkedList.insertAt(15, 1);
linkedList.removeAt(0);

console.log(linkedList.toArray()); // 输出: [15, 20]

复杂度

链表的时间复杂度如下：

• 访问：O(n)
• 搜索：O(n)
• 插入：O(1)
• 删除：O(1)

链表的空间复杂度为O(n)，其中n是链表中的节点数。

参考资料

• Wikipedia
• YouTube