Lecture 11: 链表（单向/双向、尾指针）（Linked Lists）（对应课程真实讲座 L19–L20）

目录 · ← l10 · l12 →

Lecture 11: 链表（单向/双向、尾指针）（Linked Lists）（对应课程真实讲座 L19–L20）

概述

本讲引入课程中第一种”基于节点的链式结构”——链表：元素不再挤在一整块连续内存里，而是散落在堆上，彼此用指针（存着下一个节点的地址）串成一条”链”。核心问题是数组在任意位置插入/删除时的 O(n) 搬移代价与”预分配容量”的浪费；链表用指针换来 O(1) 的头尾插入与按需增长，代价是失去 O(1) 的随机访问。我们还会讨论维护”尾指针”带来的运行时收益与维护成本、双向链表（每个节点再多一个 prev 指针），以及如何用链表实现栈与队列。 对应官方讲座：L19（Monday, July 27 — Introduction to Linked Lists）与 L20（Tuesday, July 28 — More Linked Lists）；官方配套作业为 Assignment 6（Listy Things）。官方在第 19 讲开场就用”前方有龙（Here Be Dragons）”警告：链表是本季最需要指针操控与动态内存功底、也最容易让人受挫的主题之一，官方给的学习建议是——尽早开工、多画内存图、多去答疑。

核心概念与算法原理

1. 数组的两块短板：为什么需要链表。 数组的单元（cell）在内存里连续摆放，所以 arr[3] 可以 O(1) 直达——C++ 只做一次”基地址 + 3 × 单元大小”的算术。但连续摆放带来两个麻烦：其一，容量要事先估计，估计大了浪费空间，估计小了就得扩容（新建更大的数组、把旧元素整体拷过去、释放旧数组，是昂贵的 O(n) 操作，vector 扩容就是这套流程）；其二，在数组头部或中部插入/删除，需要把一串元素逐个”挪窝”，同样是 O(n)。链表的思路是：不再承诺连续摆放，每个节点自带”下一个节点在哪”的地址，节点需要几个就 new 几个，头插永远只是两步指针操作。

2. 链表的基本解剖。 把”数据 + 指向下一个节点的指针”打包成一个 struct，就得到一个节点（node）；一串节点由 next 指针互相咬合就是链表：

head（一个指针变量，不是节点！）
 │
 ▼
┌────────┬───────┐   ┌────────┬───────┐   ┌────────┬───────┐
│ data:10│ next:●│──▶│ data:20│ next:●│──▶│ data:30│ next:●│──▶ nullptr
└────────┴───────┘   └────────┴───────┘   └────────┴───────┘

图中每个 ● 里存的是”下一个节点的内存地址”。注意两点：节点在内存里其实散落各处（上面只是画得整齐），地址才是把链条粘起来的胶水；head 是一个独立存在的指针变量，它只保存第一个节点的地址，并不是节点本身。遍历链表就像”顺着面包屑一路找下去”（官方原话的比喻是跟着记忆里的面包屑走）。

3. 头指针、nullptr 与箭头运算符。 链表的唯一（通常也是主要）入口是头指针 head。nullptr 专门表示”此指针当前不指向任何有用的东西”，我们用它标记链尾，也用它给”还没准备好指向哪里”的指针做初始化——在解引用一个指针之前先判空，叫”防御性编程”。解引用空指针会触发段错误（segmentation fault）直接崩溃。若有一个指向 struct 的指针 p，访问其字段用箭头 p->data；它等价于 (*p).data，但后者既啰嗦又不规范，课程明确要求别那么写。用 -> 跟在 head->next->next 这种”长链”后面访问深层字段，是链表代码的日常。

4. 遍历：跟着 current 走。 打印链表的经典写法是拿一个临时指针 current 从 head 出发，循环体内打印 current->data，然后执行 current = current->next（把指针”往前走一步”），直到 current 变成 nullptr。注意两种循环条件的差别：while (current != nullptr) 是在 current 自己”掉下链尾”后停止，适合”访问每个节点”；而尾插时我们想停在最后一个节点上（它的 next 还是 nullptr），所以条件要写成 while (current->next != nullptr)。printList 用值传递 Node *head 就够了——因为函数只是让局部拷贝往前走，并没有改动链表本身；改 head 里保存的地址与改节点内容完全是两回事。

5. 修改头指针必须传引用（Node *&head）。 这是官方在笔记里用 🤯 强调的最关键预备知识。如果函数要”改变调用方那个指针变量里存的值”（例如头插要 head 指向新节点），按值传指针是不行的：形参只是主调方指针的一份拷贝，函数里 head = newNode 改的是拷贝，回到 main() 后原指针纹丝不动，插入等于”丢失”。要修改原指针，必须传”指针的引用”，语法是 Node *&head——可以把它想成一个直通主调方变量的”传送门（🌀）”：函数里对这个引用赋值，就是直接改 main() 里那个 head 变量。

按值传指针（失败）:         传指针的引用（成功）:
main:  head=0x9A00          main:  head=0x9A00
函数:  head=0x9A00 ─拷贝─┐  函数:  head 🌀 直接连着 main 的 head
                          │         │ head = newNode
       main 的 head 不变 ◀─┘         main:  head=0x9B40 ← 真的变了

反之，如果函数只是”读”链表（打印、数长度、查找），传普通 Node *head 即可；如果函数要”造一个新节点并把它交还调用方”，则用返回值 Node *createNode(...)。判断标准就一条：这个函数会不会改主调方那个指针变量的值？会 → 传引用。

6. 头插 headInsert：先连新节点、后改头指针。 头插只需三步，顺序至关重要：

初始:    head ─▶ [20]─▶[30]─▶nullptr
① 造新节点 n（new 出来的 10 号节点，next 暂为乱值→先置 nullptr）
② n->next = head        先让新节点指向旧头 —— 链条先接上，旧链表没丢！
      n=[10]─▶[20]─▶[30]─▶nullptr
③ head = n              最后才把 head 拨到新节点上
      head─▶[10]─▶[20]─▶[30]─▶nullptr   ✔ 头插完成，O(1)

若把 ②③ 颠倒成 head = n; n->next = head;，第二步 n->next 指向的其实是 n 自己——旧链表 [20][30] 从此没有任何指针可达，白白泄漏在堆里。所以口诀是：先让新节点指到旧头，再把头指针拨到新节点（先连后改）。

7. 头删 removeFront：先移头、再删旧头。 删除节点必须回收它占的堆内存（delete），但顺序同样讲究：

head─▶[10]─▶[20]─▶[30]─▶nullptr
① 判空：空表直接报错，绝不解引用 nullptr
② retval = head->data            先保存要返回的值
③ victim = head                  记住旧头的地址（待会儿要 delete 它）
④ head = head->next              先把 head 拨到下一个节点
⑤ delete victim                  最后才释放旧头节点
   head─▶[20]─▶[30]─▶nullptr ✔

最经典的反面教材是 delete head; head = head->next;：先 delete 再解引用 head->next，是在访问”程序已不再拥有”的内存，属于未定义行为，可能崩溃也可能悄悄出错。铁律：delete 之后再也不要碰那个地址，所以要把需要的指针先保存下来。

8. 尾插：O(n) 走路 vs O(1) 尾指针。 没有额外信息时，尾插只能从 head 出发一路走到最后一个节点再挂新节点，O(n)。优化思路是再维护一个 tail 指针，让它始终指向最后一个节点：

tailInsert(head, 25) 无尾指针:               tailInsert(head, tail, 25) 有尾指针:
head─▶[10]─▶[20]─▶nullptr                   head─▶[10]─▶[20]─▶nullptr
      cur=10→cur=20→停! cur->next=新节点      tail 已在 20: tail->next=新节点
      O(n)                                   tail = tail->next   O(1) ✨

代价只有两样：一个额外的 8 字节指针变量，以及”每个可能改变链头/链尾的操作都要顺手维护 tail”的编码复杂度。空表是特殊情形：tail 为 nullptr 时，新节点同时成为 head 和 tail，必须两个指针一起更新。

9. 尾指针让头插/头删也变复杂了。 维护尾指针之后，头插/头删多出两个必须处理的边界：往空表头插，新节点既是头又是尾，要 head = tail = newNode；头删把唯一一个节点删光后链表空了，要 head = tail = nullptr（如果忘了把 tail 置空，tail 就成了指向已释放节点的悬垂指针）。官方还点破一个”聪明方案”为何不成立：有人提议再维护一个”倒数第二个”指针来实现 O(1) 尾删——可删完尾之后倒数第二个指针自己也得后退一格，除非给每个位置都准备一个指针，否则退不回去。尾删在单向链表上永远是 O(n)，无论有没有尾指针，因为单向的 next 没法”倒车”：

         插入        删除
头部     O(1)        O(1)
尾部     O(1)（有尾指针）      O(1)（尾指针 + 双向链表）
         否则 O(n)             否则 O(n)

10. 双向链表：每节点多一个 prev，多两步操作。 给每个节点补一个指向前驱的 prev 指针，就能 O(1) 后退一格，尾删随之变成 O(1)：

head                                                        tail
 │                                                           │
 ▼                                                           ▼
nullptr ◀── [prev│ 87 │next] ⇄ [prev│ 93 │next] ⇄ [prev│ 12 │next] ──▶ nullptr

在节点 cur 之后插入新节点 n，需要四步（单向只要两步）：

① n->prev = cur            ② n->next = cur->next
③ if (cur->next) cur->next->prev = n     ← 原后继回指 n（若 cur 是最后一个则跳过）
④ cur->next = n

删除节点 cur 则是两步”绕开”：cur->prev->next = cur->next; 与 cur->next->prev = cur->prev;（删头/删尾时还要同步 head/tail），然后 delete。双向链表的代价：每个节点从 12 字节涨到 20 字节（int 4B + 两个指针各 8B），空间多约 67%；且一切插入/删除都要维护两条方向的指针，代码明显更绕。这是计算机科学里最经典的一类交易：多花一点内存，换大幅提升的运行时间。

11. 用链表实现栈与队列。 栈要求 push/pop 在同一端，全部放在头部即可（O(1)）。队列要求入队、出队在两端：入队放队尾（借助 tail 指针 O(1)），出队放队头（O(1)）——绝不能在尾部出队，否则撞上”尾删 O(n)”。这就是 LLQueue 的布局：

dequeue ◀── head（出队，O(1)）                 tail（入队，O(1)）──▶ enqueue
              │                                 │
              ▼                                 ▼
         ┌──────┬──────┐                  ┌──────┬──────┐
         │ data │ next:●│──▶  …  ──▶      │ data │ null │
         └──────┴──────┘                  └──────┴──────┘

与动态数组版队列相比：数组版绝大多数入队 O(1)，但偶发一次 O(n) 扩容（最坏延迟不可控）；链表版每次入队都是稳定 O(1)（代价是每次都要 new 节点、设置多个字段，常数因子更慢）。如果软件对”任何单次操作都不许超时”有硬性要求，链表版的确定性反而是优点。

12. 权衡总表：数组 vs 链表。

代码示例与实现详解

示例 1：完整单向链表类 LinkedList（struct Node + head，含全套基础操作与析构）

#include <iostream>
#include <stdexcept>
using namespace std;

// 链表节点：一个数据字段 + 一个指向下一个节点的指针
struct Node {
    int data;      // 节点存放的值
    Node *next;    // 指向"下一个节点"的指针；链表末尾为 nullptr
    Node(int d) : data(d), next(nullptr) {}
};

// 单向链表类：只维护一个头指针作为整个链表的入口
class LinkedList {
public:
    LinkedList() : head(nullptr), _size(0) {}
    ~LinkedList() { clear(); }

    // 析构需要释放堆内存，因此禁用浅拷贝，避免同一块内存被 delete 两次
    LinkedList(const LinkedList &) = delete;
    LinkedList &operator=(const LinkedList &) = delete;

    void insertFront(int val);   // 头插 O(1)
    int removeFront();           // 头删 O(1)
    void insertBack(int val);    // 尾插 O(n)
    int removeBack();            // 尾删 O(n)
    bool contains(int val) const;
    void print() const;
    int size() const { return _size; }

private:
    void clear();                // 逐个 delete 所有节点
    Node *head;
    int _size;
};

void LinkedList::insertFront(int val) {
    Node *newNode = new Node(val); // ① 在堆上造一个新节点
    newNode->next = head;          // ② 先让新节点指向旧头（先连！）
    head = newNode;                // ③ 再让头指针指向新节点（后改！）
    ++_size;
}

int LinkedList::removeFront() {
    if (head == nullptr)
        throw runtime_error("removeFront() on empty list!");
    Node *victim = head;        // 先记住要删除的旧头节点
    int retval = victim->data;  // 保存要返回的值
    head = head->next;          // 头指针先往前走一步
    delete victim;              // 最后才释放旧头节点
    --_size;
    return retval;
}

void LinkedList::insertBack(int val) {
    Node *newNode = new Node(val);
    if (head == nullptr) {        // 空链表：新节点同时就是头
        head = newNode;
    } else {
        Node *cur = head;
        while (cur->next != nullptr)  // 一路走到最后一个节点
            cur = cur->next;
        cur->next = newNode;          // 把新节点挂在末尾
    }
    ++_size;
}

int LinkedList::removeBack() {
    if (head == nullptr)
        throw runtime_error("removeBack() on empty list!");
    if (head->next == nullptr) {   // 只剩一个节点：删完链表就空了
        int retval = head->data;
        delete head;
        head = nullptr;
        --_size;
        return retval;
    }
    Node *cur = head;
    while (cur->next->next != nullptr) // 停在"倒数第二个"节点
        cur = cur->next;
    int retval = cur->next->data;
    delete cur->next;
    cur->next = nullptr;
    --_size;
    return retval;
}

bool LinkedList::contains(int val) const {
    for (Node *cur = head; cur != nullptr; cur = cur->next)
        if (cur->data == val)
            return true;
    return false;
}

void LinkedList::print() const {
    cout << "head";
    for (Node *cur = head; cur != nullptr; cur = cur->next)
        cout << " -> " << cur->data;
    cout << " -> nullptr" << endl;
}

void LinkedList::clear() {
    while (head != nullptr) {
        Node *tmp = head->next;  // 先保存下一个节点的地址
        delete head;             // 再删除当前节点
        head = tmp;              // 指针前移（tmp 为 nullptr 时循环结束）
    }
    _size = 0;
}

int main() {
    LinkedList list;
    list.insertFront(30);
    list.insertFront(20);
    list.insertFront(10);      // 链表现在为: 10 -> 20 -> 30
    list.insertBack(99);       // 链表现在为: 10 -> 20 -> 30 -> 99
    list.print();

    cout << "contains(20)? " << list.contains(20) << endl;
    cout << "size = " << list.size() << endl;

    cout << "removeFront() -> " << list.removeFront() << endl; // 10
    cout << "removeBack()  -> " << list.removeBack() << endl;  // 99
    list.print();              // 20 -> 30

    list.insertBack(7);
    list.print();              // 20 -> 30 -> 7
    return 0;                  // 离开作用域，析构函数自动释放剩余节点
}

【代码做什么】 main() 演示了全套操作：三次头插得到 10->20->30，一次尾插得到 10->20->30->99；打印、查找 20、查询 size；removeFront 删掉 10、removeBack 删掉 99，链表回到 20->30；再尾插 7 得到 20->30->7。程序结束时 list 对象离开作用域，析构函数 ~LinkedList 调用 clear() 把仍存活的两个节点全部 delete，无内存泄漏。insertFront 忠实落实”先连新节点、后改头指针”：新节点先指向旧头（newNode->next = head），再更新头指针；removeFront 忠实落实”先移头、再删旧头”：先用 victim 保存旧头地址，head 前移之后才 delete victim。两个删除函数都对空表抛出 std::runtime_error，避免解引用 nullptr。

【实现机制解说】 类的全部状态就是 head 指针与计数器 _size，head 是唯一入口，所以每个成员函数都从 head 出发。insertBack/removeBack 没有尾指针，只能靠 while (cur->next != nullptr) / while (cur->next->next != nullptr) 先定位到”最后一个/倒数第二个”节点——前者停住时 cur 的 next 为 nullptr 可挂新节点，后者停住时 cur->next 就是要删的尾节点，删完要把 cur->next = nullptr 让新尾封口。removeBack 还特判了”只剩一个节点”：此时 head->next == nullptr，直接删 head 并置空，否则通用循环里 cur->next->next 会解引用空指针。析构/clear 用”先存 tmp 再 delete 再前移”的三步循环，正是为了避免第 7 节那个 delete head; head = head->next; 的悬垂错误；循环结束后 head 自然为 nullptr。_size 在每次插入/删除时同步增减，使 size() 达到 O(1)。因为类管理着堆内存，浅拷贝会让两个对象共享同一串节点、析构时 double free，所以示例用 = delete 显式禁用拷贝（若业务需要拷贝，应按”Rule of Three”补拷贝构造与拷贝赋值——本讲重点是链表的指针机制，故不展开）。

示例 2：用链表实现队列 LLQueue（front + back，两端 O(1)）

#include <iostream>
#include <stdexcept>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int d) : data(d), next(nullptr) {}
};

// 用单向链表实现队列：队尾入队(enqueue)、队头出队(dequeue)。
// 同时维护 front(头) 与 back(尾) 两个指针，使两端操作都是 O(1)。
class LLQueue {
public:
    LLQueue() : front(nullptr), back(nullptr), _size(0) {}
    ~LLQueue() { clear(); }

    LLQueue(const LLQueue &) = delete;
    LLQueue &operator=(const LLQueue &) = delete;

    void enqueue(int val); // 在队尾（链表尾）加入：O(1)
    int dequeue();         // 从队头（链表头）取出：O(1)
    int peek() const;      // 只看队头不取走
    int size() const { return _size; }
    bool isEmpty() const { return front == nullptr; }

private:
    void clear();
    Node *front;  // 队头 = 链表头
    Node *back;   // 队尾 = 链表尾
    int _size;
};

void LLQueue::enqueue(int val) {
    if (back == nullptr) {            // 空队列：新节点既是头也是尾
        front = back = new Node(val);
    } else {
        back->next = new Node(val);   // 挂到当前队尾之后
        back = back->next;            // 尾指针向后移动
    }
    ++_size;
}

int LLQueue::dequeue() {
    if (front == nullptr)
        throw runtime_error("dequeue() on empty queue!");
    Node *victim = front;
    int retval = victim->data;
    front = front->next;              // 头指针前移
    if (front == nullptr)             // 队列变空：尾指针也必须归零！
        back = nullptr;
    delete victim;
    --_size;
    return retval;
}

int LLQueue::peek() const {
    if (front == nullptr)
        throw runtime_error("peek() on empty queue!");
    return front->data;
}

void LLQueue::clear() {
    while (front != nullptr) {
        Node *tmp = front->next;
        delete front;
        front = tmp;
    }
    back = nullptr;   // 防止留下指向已释放节点的悬垂尾指针
    _size = 0;
}

int main() {
    LLQueue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << "front = " << q.peek() << ", size = " << q.size() << endl;

    while (!q.isEmpty())
        cout << q.dequeue() << " ";
    cout << endl;

    q.enqueue(99);                     // 清空后再入队：考验尾指针的维护
    cout << "again: " << q.dequeue() << endl;
    return 0;
}

【代码做什么】 main() 先入队 10、20、30，打印队头 10 与大小 3；随后循环出队打印 10 20 30，队列被清空；此时再入队 99 并立刻出队——这一步专门考验”队列清空后 front/back 指针是否仍被正确维护”。enqueue 在队尾加节点：空队时新节点同时成为 front 与 back，非空时挂到 back 之后并把 back 后移；dequeue 在队头取：保存旧头地址与返回值，front 前移，若队列因此变空则把 back 一并置空（否则 back 将指向已 delete 的节点），最后释放旧头。peek/size/isEmpty 都只读不写，声明为 const 成员函数——编译器会保证它们不会误改成员变量。

【实现机制解说】 队列是 FIFO，入队、出队发生在链表两端：入队走尾（back 让我们 O(1) 直达链尾，不必像示例 1 的 insertBack 那样从头走一遍），出队走头（front 就是链头，O(1)）。维护 back 的核心是两条”同步规则”：入队时空表特判（新节点 = 头 = 尾）；出队后若链表变空，必须把 back 置 nullptr。dequeue 里 front = front->next 之后再判空，而不是先判 front->next 再移动——若队列只有一个节点，front->next 本来就是 nullptr，移动后判空恰好命中，逻辑统一。clear() 循环释放所有节点后把 back 归零，是因为循环结束时 back 仍指着最后一个被删除的节点，不归零就是悬垂指针。这个结构再次印证：“用空间（多维护一个指针）换时间（尾插 O(n)→O(1)）”，同时所有可能改变链首/链尾的操作都必须意识到 back 的存在。

示例 3：双向链表——pushFront / popBack / 中间 insertAfter（演示多出的 prev 步骤）

#include <iostream>
#include <stdexcept>
using namespace std;

// 双向链表节点：比单向多一个 prev 指针，可向前走
struct DNode {
    int data;
    DNode *prev;   // 指向前一个节点
    DNode *next;   // 指向后一个节点
    DNode(int d) : data(d), prev(nullptr), next(nullptr) {}
};

// 头插：除单向链表的两个步骤外，还要让旧头指回新节点（多一步）
void pushFront(DNode *&head, DNode *&tail, int val) {
    DNode *n = new DNode(val);
    n->next = head;              // ① 新节点指向旧头
    if (head != nullptr)
        head->prev = n;          // ② 旧头回指新节点（双向特有的步骤）
    else
        tail = n;                // 空表：新节点同时成为尾
    head = n;                    // ③ 头指针指向新节点
}

// 头删：返回被删值；只剩一个节点时 head/tail 都要置空
int popFront(DNode *&head, DNode *&tail) {
    if (head == nullptr)
        throw runtime_error("popFront() on empty list!");
    DNode *victim = head;
    int retval = victim->data;
    head = head->next;
    if (head != nullptr)
        head->prev = nullptr;    // 双向特有：新头没有前驱了
    else
        tail = nullptr;          // 链表空了，尾指针同步归零
    delete victim;
    return retval;
}

// 尾删：双向链表 O(1)（单向链表即使有尾指针也要 O(n) 找倒数第二）
int popBack(DNode *&head, DNode *&tail) {
    if (tail == nullptr)
        throw runtime_error("popBack() on empty list!");
    DNode *victim = tail;
    int retval = victim->data;
    tail = tail->prev;
    if (tail != nullptr)
        tail->next = nullptr;    // 双向特有：新尾的后继清空
    else
        head = nullptr;          // 链表空了，头指针同步归零
    delete victim;
    return retval;
}

// 在节点 node 之后插入新节点（演示"中间插入"的四步指针重连）
void insertAfter(DNode *node, int val) {
    DNode *n = new DNode(val);
    n->prev = node;               // ① 新节点指回 node
    n->next = node->next;         // ② 新节点指向 node 原来的后继
    if (node->next != nullptr)
        node->next->prev = n;     // ③ 原后继回指新节点（若存在）
    node->next = n;               // ④ node 的 next 指向新节点
}

void printForward(DNode *head) {
    for (DNode *p = head; p != nullptr; p = p->next)
        cout << p->data << " ";
    cout << endl;
}

void printBackward(DNode *tail) {
    for (DNode *p = tail; p != nullptr; p = p->prev)
        cout << p->data << " ";
    cout << endl;
}

void destroy(DNode *&head) {
    while (head != nullptr) {
        DNode *tmp = head->next;
        delete head;
        head = tmp;
    }
}

int main() {
    DNode *head = nullptr, *tail = nullptr;
    pushFront(head, tail, 30);
    pushFront(head, tail, 20);
    pushFront(head, tail, 10);   // 10 <-> 20 <-> 30

    cout << "forward : ";
    printForward(head);
    cout << "backward: ";
    printBackward(tail);

    insertAfter(head->next, 99); // 在 20 之后插入 99: 10 <-> 20 <-> 99 <-> 30
    cout << "after insertAfter(20, 99): ";
    printForward(head);

    cout << "popBack -> " << popBack(head, tail) << endl;  // 30
    cout << "popFront -> " << popFront(head, tail) << endl; // 10
    cout << "remaining: ";
    printForward(head);

    destroy(head);   // 释放所有节点（head 变 nullptr）
    return 0;
}

【代码做什么】 main() 用三次头插建成 10 ⇄ 20 ⇄ 30，正序打印 10 20 30、用 prev 逆序打印 30 20 10（证明双向行走有效）；insertAfter 在 20 之后插 99，链表变成 10 20 99 30；popBack 删掉 30、popFront 删掉 10，剩 20 99；最后 destroy 释放全部节点。

【实现机制解说】 双向链表的每个操作都比单向多”一到两步对称动作”：pushFront 多一句 head->prev = n（旧头回指新节点），popFront 多一句 head->prev = nullptr（新头斩断前驱），popBack 之所以 O(1)，正是因为它能借 tail->prev 直接后退一格找到新尾，再 tail->next = nullptr 把新尾封口——单向链表做不到这一步，所以尾删必须 O(n)。两个边界情形贯穿始终：空表时头插的节点同时是尾（tail = n）；删空链表时头、尾必须双双归零（popFront 删最后一个时 tail = nullptr，popBack 删最后一个时 head = nullptr）。insertAfter 的四步顺序是经过设计的：第③步要访问 node->next->prev，因此必须先于第④步执行（第④步一旦改写 node->next，原后继就找不到了），并且要先判 node->next != nullptr——若 node 是尾节点，原后继不存在，跳过第③步即可。对比示例 1 会发现：双向链表多出来的所有代码，本质上都在维护”对称的第二条链”。

复杂度分析

最好/平均/最坏说明。 链表的形态不随插入历史变化，头尾操作基本是”恒定 O(1) 或恒定 O(n)”，没有明显的最好/最坏之分；真正分化的只有”访问/查找第 k 个”（头附近快、越深越慢，最坏到链尾 O(n)）以及数组版队列的”入队”（平常 O(1)、扩容那一次 O(n)）。因此官方给出的精确说法是”取决于实现”：问”尾插多快”要答”若维护尾指针则 O(1)，否则 O(n)”。空间上，链表节点比数组单元贵得多：官方以 int 4 字节、指针 8 字节（64 位系统）为例，单向链表每节点 12 字节约为数组的 3 倍，双向链表每节点 20 字节约为 5 倍——这是”把地址作为胶水”的固有开销。

关键要点

• 头指针是链表的唯一入口，nullptr 是链尾哨兵；画内存图（连地址一起画）是理解与调试链表的头号武器。
• 头插永远”先让新节点指向旧头，再移动头指针”（先连后改）；头删永远”先保存/移动指针，再 delete”——delete 之后绝不访问那个地址。
• 只要函数要改变主调方指针变量的值，就用 Node *&head 传引用；只读遍历用普通 Node *head，造节点用返回值。
• 尾指针把尾插从 O(n) 降到 O(1)，但空表、只剩一个节点这两类边界必须在头插/头删/出队时同步维护 head 与 tail。
• 双向链表用”每个节点多一个 prev”换取 O(1) 尾删与逆序遍历，代价是空间 +67% 与两套指针维护——这是”空间换时间”的经典示范。

常见陷阱与注意事项

• 丢失头指针：head = head->next 前忘了先保存旧头地址，旧节点无法释放（泄漏），链表入口也丢了。规避：删除前先 Node *tmp = ... 保存，或先移动再 delete。
• 头插顺序写反：head = n; n->next = head; 会让 n 指向自己，旧链表整体丢失。规避：牢记”先连后改”，写完立即画图验证。
• delete 后解引用：delete head; head = head->next; 是未定义行为。规避：先保存 head->next，再 delete，再赋值。
• 解引用 nullptr / 对空表操作：空表上 removeFront 会段错误。规避：进入函数先判 head == nullptr 并抛出异常或提前返回。
• 忘记初始化头指针：Node *head; 不初始化就 tailInsert，head 里是垃圾地址，函数会”顺着垃圾地址走”然后崩溃。规避：一律 Node *head = nullptr;。
• 维护尾指针时漏掉边界：头插进空表忘更新 tail、删光唯一节点忘把 tail 置空，都会留下悬垂的尾指针。规避：把”空表 / 只剩一个节点”作为 checklist 逐函数过一遍。
• 内存泄漏：每个 new Node 都必须有对应的 delete（析构/clear 循环释放全部节点）。规避：写完链表类先测空表、单节点、多节点三种情况，确认析构无泄漏。
• 把”改指针”误当”改节点”：current = current->next 只是让局部指针前进，不会破坏链表；而 *current = ... 才是改节点内容——两者别混淆，printList 里想明白这一点就能放心用局部拷贝遍历。
• 忘了 const：peek()/size()/isEmpty() 这类只读成员函数应在声明末尾加 const，防止误改成员，也让常量对象可调用。
• 不会用 -> 的等价物：(*head).data 虽合法但官方明令避免，统一写 head->data。

思考题（带答案）

问题 1：为什么 void insertFront(Node *head, int val)（按值传指针）无法真正完成头插？如何修改？ 答案：形参 head 是 main() 里 head 的一份拷贝，函数内 head = newNode 只改写拷贝，返回后 main() 的头指针不变，新节点脱离链表（泄漏且”插入失败”）。修改方法：参数改为 Node *&head（指针的引用），让函数直通调用方的变量；或者用返回值 Node *insertFront(Node *head, int val) 由调用方接住新头。

问题 2：单链表删除尾节点时，为什么必须停在”倒数第二个”节点而不是停在尾节点？尾删在维护了尾指针的单向链表上为何仍是 O(n)？ 答案：停在尾节点时我们手里只有尾节点自己，无法把它从链表上”摘下来”——摘除需要改写它前驱的 next 字段，而单向链表没有 prev 指针，找不到它的前驱，所以循环条件要写成 cur->next->next != nullptr，停在倒数第二，改写 cur->next。同理，即便维护了尾指针，删除尾节点后 tail 要后退一格指向新尾，单向链表无法从旧尾一步退到前驱，只能从头重新走 O(n) 找到倒数第二；要 O(1) 尾删必须引入 prev 指针（双向链表）。

问题 3：LLQueue 用”front + back”实现，为什么入队走队尾、出队走队头，而不能反过来？ 答案：出队（删除）若发生在队尾，就是”尾删”：单向链表上无论如何都是 O(n)，即使有 back 指针也退不回去；而入队（插入）发生在队尾时，back 指针能让我们 O(1) 直达链尾完成插入。反过来配置（入队走头、出队走尾）会把 O(n) 的尾删强加给每次出队，队列两端就无法同时高效了。栈则不同，push/pop 都发生在同一端，放在头即可全部 O(1)。