上篇动态数组最大的软肋是：在中间插入或删除一个元素，要搬移其后所有的元素，代价 O(n)。链表（linked list）号称能绕开这个软肋——它不靠"连续内存 + 下标"组织数据，而是让每个元素自己记住"下一个是谁"。

但"链表删除是 O(1)"这句话，九成初学者都记漏了前提。这篇就把单链表、双链表、以及那个能把一堆边界特判消灭干净的**哨兵节点（sentinel）**讲透，顺便留三道面试开胃题。

一、单链表：每个节点只认识"下一个"

单链表由一串 节点（Node） 串成。每个节点干两件事：存自己的数据 val，再存一个指向下一个节点的引用 next。最后一个节点的 next 是 null，表示"到头了"。一个独立的 head 引用指向第一个节点，靠它才能摸到整条链。

1 val next 2 val next 3 val next null head

本质一句话：单链表用"每个节点记住下一个"换来了不连续存储，但代价是失去了随机访问——想找第 k 个，只能从头 next 一路走，O(k)。

二、单链表的最小 Java 实现

下面是一份能跑的最小骨架。重点看三件事：头插（head 要改）、尾插（要走到尾巴）、按值删除（要找前驱）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
static class Node {
    int val;
    Node next;
    Node(int v) { val = v; }
}

static class SinglyList {
    Node head;                       // 指向第一个节点，空表时为 null

    void insertHead(int v) {         // O(1)：新节点顶到最前面
        Node n = new Node(v);
        n.next = head;
        head = n;
    }

    void insertTail(int v) {         // O(n)：要先走到最后一个节点
        Node n = new Node(v);
        if (head == null) { head = n; return; }
        Node p = head;
        while (p.next != null) p = p.next;
        p.next = n;
    }

    void deleteByValue(int v) {      // O(n)：要找"待删节点的前驱"
        if (head == null) return;
        if (head.val == v) { head = head.next; return; }   // 删头是特例
        Node p = head;
        while (p.next != null && p.next.val != v) p = p.next;
        if (p.next != null) p.next = p.next.next;
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node p = head; p != null; p = p.next)
            sb.append(p.val).append(p.next != null ? " -> " : "");
        return sb.toString();
    }
}

public static void main(String[] args) {
    SinglyList list = new SinglyList();
    list.insertTail(1);
    list.insertTail(2);
    list.insertTail(3);
    list.insertHead(0);
    System.out.println(list);        // 0 -> 1 -> 2 -> 3
    list.deleteByValue(2);
    System.out.println(list);        // 0 -> 1 -> 3
}

输出：

1
2
0 -> 1 -> 2 -> 3
0 -> 1 -> 3

三、坑：单链表的"删除 O(1)"到底成立吗

这是全文最容易被背错的一句。分三种情况：

  • 已知前驱 prev，删 prev 的后继：O(1)，一行 prev.next = prev.next.next。
  • 只给你节点 p 本身，要删 p：单链表只有 next，够不着前驱，所以必须先 O(n) 遍历找到前驱——此时删除整体是 O(n)。
  • 只给你 p、但允许"作弊删除"：把 p.next 的值抄到 p，再删 p.next：
1
2
3
// 删掉"给定节点 p 本身"，O(1)，但有代价
p.val = p.next.val;
p.next = p.next.next;

它确实 O(1)，但改写了节点的身份——原来 p 这个位置现在存的是后一个节点的值。如果节点带唯一 key、或外部还攥着 p 的引用，语义就乱了；而且尾节点没法这么干（p.next 是 null）。所以正规的"按前驱删除"，单链表就是 O(n)。

本质一句话：单链表只能"向前看"（沿 next），做不到"向后找前驱"，这就是为什么"删自己"要 O(n)。

四、双链表：多一倍指针，换 O(1) 删除

给每个节点再加一个 prev 指针，能直接摸到前驱，于是"已知任意节点 p，删掉 p 自己"变成两行改指针，O(1)：

1
2
p.prev.next = p.next;   // 前驱绕过 p
p.next.prev = p.prev;   // 后继回头指向 p 的前驱

为什么不需要遍历？因为 p 手里本来就攥着前后两个邻居的引用，两行把"前后"直接接上、p 自然脱链。这就是双链表相对单链表的核心卖点：用多一倍的指针，换来"已知任意节点 O(1) 删除"。

prev 1 next prev 2 next prev 3 next head

本质一句话：双链表用空间（多一个 prev）换时间（任意节点 O(1) 删除 + 还能反向遍历）。

五、哨兵（sentinel）：把"头特殊"变成"头普通"

单/双链表写删除时，有个躲不掉的麻烦：删头节点和删中间节点逻辑不一样。删头要改 head 指针本身（head = head.next）；删中间只改前驱的 next。于是代码里到处是 if (p == head) ... else ... 特判，空表、只有一个节点时尤其容易写崩。

哨兵就是个永远在头的"假节点" dummy，真正的第一个元素变成 dummy.next。因为 dummy 永远存在，头节点就不再是"特殊的那个"——删头、删中间、甚至删尾，都变成同一套"改前驱的 next / 后继的 prev"代码。下面把两种写法对照一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 无哨兵：删头是特例，必须单独处理
void removeNoSentinel(Node head, Node p) {
    if (p == head) { head = p.next; return; }   // 特判
    Node prev = head;
    while (prev.next != p) prev = prev.next;
    prev.next = p.next;
}

// 有哨兵：dummy 永远在，删头 = 删中间，无需特判
void removeWithSentinel(Node dummy, Node p) {
    p.prev.next = p.next;     // dummy 充当"头的前驱"
    p.next.prev = p.prev;
}
空表：dummy.next 指向自己 dummy next = prev = 自己 非空：dummy.next 即 head D A B

用哨兵时通常不保留单独的 head 变量——dummy.next 自己就是 head 指针；空表时它指回 dummy 自己，读作"没元素"。这样连"删最后一个真实节点"也不会崩（p 是尾时 p.next 就是 dummy，dummy.prev 被正确接上）。

本质一句话：哨兵用一个永不删除的假节点，把所有"头特殊"的边界特判抹平，代码更短也更不易写崩。

六、三道开胃面试题

链表是面试高频，这三道最经典，建议亲手写一遍：

1. 反转链表（迭代，O(n) 空间 O(1)）

1
2
3
4
5
6
7
8
9
Node reverse(Node head) {
    Node prev = null, cur = head;
    while (cur != null) {
        Node nxt = cur.next;   // 先存后继
        cur.next = prev;       // 掉头
        prev = cur; cur = nxt; // 双指针前移
    }
    return prev;               // 新的头
}

2. 快慢指针判环（Floyd 判圈）

1
2
3
4
5
6
7
8
9
boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;   // 追上即环
    }
    return false;
}

3. 删倒数第 k 个节点（双指针间距法）

1
2
3
4
5
6
void removeKthFromEnd(SinglyList list, int k) {
    Node fast = list.head, slow = list.head;
    for (int i = 0; i < k; i++) fast = fast.next;  // fast 先走 k 步
    while (fast.next != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;                     // slow 停在待删前驱
}

七、C 语言对照

C 里没有引用和类，节点用 struct + 指针，内存手动 malloc/free，改 head 必须传二级指针（因为 C 是值传递，想改调用方的指针变量得取它的地址）：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct Node { int val; struct Node* next; } Node;

void insert_head(Node** head, int v) {
    Node* n = malloc(sizeof(Node));
    n->val = v;
    n->next = *head;     // 新节点顶到最前
    *head = n;           // 改的是"调用方那个 head 指针"
}

void free_list(Node* head) {           // 一定要手动释放，否则内存泄漏
    while (head) { Node* t = head->next; free(head); head = t; }
}

Java 把引用、自动 GC、对象封装都包好了，所以你只管 head = n；C 把"指针怎么传、内存谁释放"全甩给你，更接近链表在内存里的真实样子。

八、🐾 小结

  • 单链表：每个节点记 next，不连续存储、失去随机访问，但换来"不在中间搬移元素"。
  • 最易被背错的一句话：单链表"删自己"是 O(n)（够不着前驱）；只有已知前驱、或允许"覆盖式删除"时才是 O(1)。
  • 双链表：加 prev，换来任意节点 O(1) 删除和反向遍历，代价是多一倍指针。
  • 哨兵：永不删除的假头节点，把"头特殊"的所有边界特判抹平——这正是工业级链表（如 Java LinkedList）的内部做法。

链表用"指针跳转"换掉了数组的"连续 + 随机访问"，换来任意位置的 O(1) 插入删除（前提是已知邻居）；而哨兵节点，是把这套代码从"处处特判"收拾成"处处统一"的那块拼图。