链表到底是什么：从一条寻宝路线理解节点与指针

2023/12/09

链表是我以前很容易“看懂定义，但写代码时又忘记”的数据结构。后来我发现，理解它的关键不是背节点类，而是先接受一件事：链表没有一排连续编号的格子，每个节点只知道下一个节点在哪里。

一、把链表想成一条寻宝路线

假设有三张寻宝卡片。每张卡片写着一份内容，以及下一张卡片的位置：

A 卡片：内容是 10，下一张去找 B
B 卡片：内容是 20，下一张去找 C
C 卡片：内容是 30，没有下一张

head → [10 | next] → [20 | next] → [30 | null]

每张卡片就是一个节点（Node），包含两部分：value 保存数据，next 保存下一个节点的引用。head 是入口，最后一个节点的 next 是 null。

链表的“链”不是节点真的挨在一起，而是它们通过引用连接。JavaScript 会自己管理对象的实际内存位置，我们只需要理解对象之间的引用关系。

二、最小的单链表长什么样

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

const first = new ListNode(10);
const second = new ListNode(20);
const third = new ListNode(30);

first.next = second;
second.next = third;

const head = first;

如果要找到值为 30 的节点，不能写 head[2]。只能从 head 出发，沿着 next 一张卡片一张卡片地找：

function printList(head) {
  let current = head;

  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
}

这就是链表不能按下标快速访问的原因。访问第 n 个节点，最坏需要走 n 步，时间复杂度是 O(n)。数组可以通过索引快速定位元素，访问通常是 O(1)。

三、插入和删除，其实是在改路线

链表插入节点不需要把后面的元素整体搬走。假设要在 10 和 20 之间插入 15，只需要修改两条引用：

const newNode = new ListNode(15);

newNode.next = first.next; // 15 → 20
first.next = newNode;      // 10 → 15

顺序不能反。如果先让 first.next 指向新节点，又没有提前保存原来的下一个节点，就可能丢掉后面的链。

删除也不是销毁一块连续空间，而是让前一个节点绕过目标节点。删除 15 可以写成：

first.next = first.next.next;
// 10 直接指向 20，15 不再属于这条链

如果已经拿到插入位置或前一个节点，修改引用可以是 O(1)。但如果只给一个值，仍然要先从头查找位置，这一步是 O(n)。所以“链表插入删除一定比数组快”并不准确，是否已经知道位置很关键。

四、链表和数组怎么选

  1. 经常按下标读取元素：数组更合适。
  2. 经常在已知节点附近插入或删除：链表更合适。
  3. 链表的每个节点要额外保存引用，内存开销通常更大。
  4. 数组结构直观、访问快，在普通前端业务中通常更常见。

单链表只有 next，只能向后走；双向链表还会保存 prev，可以前后移动，但每个节点会多保存一个引用。LRU 缓存常使用哈希表配合双向链表：哈希表负责快速找到节点，链表负责快速调整节点顺序。

五、我需要记住的核心画面

链表不是“一个装着很多数据的大盒子”，而是一串彼此引用的小盒子。遍历就是沿着 next 一直走；插入就是接入一段新路线；删除就是绕过一个节点。只要脑中能画出 head → node → node → null，大多数基础代码都只是移动引用。

泰斯