链表详解：核心原理、手写实现与工程应用

学数据结构时，大多数人接触的第一个动态结构就是链表。老实说，我当年看教材里那些方块加箭头的示意图，心里嘀咕的始终是同一句话：数组用得好好的，为什么非要搞个指针串起来的链表？直到后来在项目里被数组的插入删除性能反复教育，又因为链表的空指针bug熬夜排查，才算把二者的本质想明白。这篇我打算把链表彻底讲透——从基础结构、手写代码、常见坑点到工程选型和面试题型，该给结论给结论，该上代码上代码，该讲教训讲教训。刚入门的新手、准备期末或考研的同学、马上要面算法的开发者，应该都能在这篇里拿到点直接能用的东西。

1. 为什么要有链表：数组的插入之痛和CPU缓存真相

1.1 数组的“连续性”：既是优势也是枷锁

数组在内存里是一块连续的存储空间。这个“连续”是它最大的本钱：靠下标访问元素时，CPU只需要做一次基地址加偏移量的计算，就能直接命中目标，时间复杂度是O(1)。同时，因为元素在内存中紧挨着，遍历数组时CPU缓存可以提前把相邻数据一起载入，实际运行速度往往比理论复杂度看起来还要快。

但“连续”同时也是数组最大的枷锁。往数组中间插入一个元素，比如在10个元素的数组下标5处插入一个新值，后面5个元素全都得往后挪动一位；如果是尾部，还得看数组有没有空位。如果这个数组已经满了，那就得重新申请一块更大的内存，再把所有旧数据复制过去。这种搬移的成本是O(n)，n越大越痛。

我在真实项目里遇到过类似场景：一个正在不断增删元素的在线列表，一开始图省事用了动态数组。用户量一上来，每次插入删除都触发成片的数据搬移，CPU占用率肉眼可见地上升，偶尔还会因为扩容导致短暂的卡顿。后来把核心操作改成链表结构，问题才缓解。数组和链表的取舍，不是哪个“更新”，而是它们分别解决了不同的问题。

1.2 链表的核心设计：每个节点记住下一个在哪

链表的设计思路很直接：不再要求元素在内存里连续存放。每个节点除了保存自己的数据，还额外保存一个指针，指向下一个节点的位置。第一个节点叫头节点（head），整个链表就靠这个头节点作为入口。

你可以把它理解成一群人玩“找下一个”的游戏：每个人手里都有一张纸条，上面写着下一个队友在哪。大家不需要站成一排，散落在城市的各个角落也没关系，只要从第一个人开始，按照纸条一路找下去，就能把所有人串起来。纸条，就是next指针。

因为节点之间是靠指针连接的，往链表中插入一个新节点就变得非常轻量。比如在节点A后面插入节点B：

1. 给B分配内存并填入数据；
2. 让B的next指向A原来的下一个节点；
3. 让A的next指向B。

这个操作跟链表里到底有多少个节点没有任何关系。链表现在有一百个节点还是一万个节点，只要你知道A的位置，插入耗时都是常数级别，也就是O(1)。删除同理，让A的next跳过B直接指向B的下一个节点即可。

当然，代价也很明显：想访问链表里的第k个元素，你没法像数组那样直接算地址，必须从头节点开始，一个节点一个节点地跳过去，平均复杂度是O(n)。这就像一群人散落在城市不同角落，你想找到排在第5位的队友，只能从第1个人开始一个个问过去。

1.3 复杂度对比表：别再凭直觉选数据结构

把数组和链表的核心操作复杂度放在一张表里，很多模糊的认知会一下子清晰起来。

这里有几个容易被忽略的细节。一是数组的尾部插入其实效率很高，动态数组（比如C++的vector、Java的ArrayList）会预留一部分空位，只有在容量耗尽时才扩容，所以均摊下来是O(1)。二是链表只有在“已经知道操作位置”的前提下，插入删除才是O(1)。如果只知道要删除某个值，你得先从头遍历找到这个节点，代价仍然是O(n)。三是CPU缓存的因素：数组遍历时缓存命中率高，链表节点散落在堆内存的不同地址，每次跳转可能都面临缓存未命中，所以即便理论复杂度相同，实际跑起来链表往往比数组慢不少。这也是为什么工程里很多场景下vector反而比list更受欢迎。

2. 单链表、双向链表、循环链表：三种形态分别解决什么问题

2.1 单链表：结构最简，逻辑最碎

单链表就是最基础的那种链表，节点里只有一个next指针。它只支持一个方向：从head出发，一路走向tail。优点是省内存，每个节点只多一个指针；缺点是往回走做不到。

比如单链表删除某个节点，如果你手里只有指向这个节点的指针cur，想把它删掉，就必须先找到它的前驱节点prev，才能让prev->next跳过cur。怎么找前驱？只能从头节点开始重新遍历，这就又多了一次O(n)的轮询。很多人刚开始写单链表时，经常在删除这里绕晕，原因就在于忘了“单链表只有next没有prev，前驱必须靠遍历获得”。

单链表的典型场景是那些不需要回溯的序列操作，比如邻接表存图、任务队列等。C++标准库里的forward_list就是单链表，如果你明确永远不需要往回遍历，用它比std::list更省一点内存。

2.2 双向链表：多一个prev指针，删除从此不用回头

双向链表给每个节点增加了一个prev指针，指向它的前驱节点。这样一来，节点的“方向感”就完整了：既可以沿着next向后走，也可以沿着prev向前走。

收益最直接的操作就是删除。在双向链表里，如果已经拿到了要删除的节点cur，直接通过cur->prev拿到前驱，通过cur->next拿到后继，两条指针一接，节点就摘下来了，时间复杂度是O(1)，完全不需要从头遍历。同理，如果你要在某个节点前面插入新节点，也不需要先找前驱。

代价是内存翻倍——每个节点多一个prev指针，如果链表里存的是小对象，这个额外开销会非常明显。Java的LinkedList底层就是双向链表，C++的std::list也是。工程里常见的LRU缓存、浏览器前进后退历史，都是双向链表的典型应用，后面第5章我会详细展开。

2.3 循环链表：首尾相接解决环形问题

循环链表把链表的尾部节点“接”回头节点，让链表变成一个环。判断遍历结束的条件也从“cur == nullptr”变成了“cur == head”或者“让指针走一圈回到起点”。

最常见的是循环单链表和循环双链表。这些结构很适合天然的环形场景。比如约瑟夫环游戏：一群人围成一圈报数，数到某个数字的人出列，再从下一个人继续报。用循环链表模拟这个游戏，逻辑特别贴合直觉：从当前节点开始数，数到的人直接摘除，然后从后继节点继续。

操作系统里的时间片轮转调度也常用环形队列：每个进程轮流执行一个时间片，指针在进程链表上不断循环。播放器的循环播放列表同理，末尾一首播完自动回到第一首。循环链表的核心优点是：你不需要额外记录头尾，从任意节点出发都能遍历整个集合。

3. 手写链表核心操作：建表、插入删除、逆序与快慢指针的全部细节

3.1 节点定义与两种建表方式：头插法、尾插法

链表代码的第一步是定义节点。以C++为例，最简单也最经典的结构体是这样的：

cpp复制struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

数据域存具体值，指针域存下一个节点的地址，构造函数顺便把next初始化为空指针。这个结构体几乎出现在所有数据结构教材里，面试手写题也基本沿用。

建表有两种经典方式：头插法和尾插法。头插法每次把新节点插到头节点的位置，结果是数据顺序完全反过来：

cpp复制ListNode* createByHeadInsert(const vector<int>& data) {
    ListNode* head = nullptr;
    for (int x : data) {
        ListNode* node = new ListNode(x);
        node->next = head;
        head = node;
    }
    return head;
}

假设传入[1, 2, 3]，头插法生成的链表顺序是3->2->1。原因很简单：每次新节点都抢占了head的位置，原来的head变成了它的后继。

尾插法则是维护一个tail指针，让新节点不断接在末尾，数据顺序保持一致：

cpp复制ListNode* createByTailInsert(const vector<int>& data) {
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    for (int x : data) {
        ListNode* node = new ListNode(x);
        tail->next = node;
        tail = node;
    }
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

这里我引入了一个虚拟头节点dummy。它的作用是避免“链表为空时插入第一个元素”这种边界判断，所有新节点都统一接在tail后面，最后再把dummy删除即可。虚拟头节点的这个优点，后面第4章会专门再说。

3.2 插入与删除：指针操作的顺序是命门

在已知节点pre后面插入一个新的节点node，核心代码只有三行，但顺序不能错：

cpp复制void insertAfter(ListNode* pre, int val) {
    if (pre == nullptr) return;
    ListNode* node = new ListNode(val);
    node->next = pre->next; // 第一步：新节点先接住pre的后继
    pre->next = node;       // 第二步：pre的next指向新节点
}

我见过太多新手把这两步顺序写反：先执行pre->next = node，再去node->next = ...，结果原来的后续节点全都丢了，链表在pre这里断成两截。这里可以记住一个口诀：“先接后断”——先让新节点和其他节点建立连接，再修改前驱的next指针。顺序一旦反了，后面的节点就再也找不回来了。

删除操作的命门同样体现在指针交接上。以单链表删除cur节点为例（我们知道pre是cur的前驱）：

cpp复制void deleteNode(ListNode* pre) {
    if (pre == nullptr || pre->next == nullptr) return;
    ListNode* target = pre->next;
    pre->next = target->next;
    delete target;
}

先把pre的next绕开target，指到target的下一个节点，再释放内存。如果是双向链表，删除当前节点会更方便，但也要注意对称处理：

cpp复制node->prev->next = node->next;
node->next->prev = node->prev;
delete node;

两条指针都必须接上，漏掉一条链就断了。

3.3 链表逆序：三指针法的每一步都有讲究

链表逆序是面试中的高频题，也是最考验指针基本功的题。标准解法是三指针法：

cpp复制ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* nextTemp = cur->next; // 先保存后继，否则一会就找不到了
        cur->next = prev;               // 当前节点回头指向prev
        prev = cur;                     // prev前进
        cur = nextTemp;                 // cur前进
    }
    return prev; // 循环结束时，prev指向新链表的头
}

我来逐步拆解。初始状态下，prev为nullptr，cur指向原链表头。循环第一轮：先用nextTemp保存cur->next，因为下一步cur->next就要被改成prev了，如果不提前保存，原链表的后半段就彻底丢失；然后把cur->next指向prev，相当于第一个节点的next从第二个节点改为nullptr；接着prev、cur分别向后移动一步。第二轮时，第二个节点的next就会指向第一个节点，链条一步步完成原地反转。

循环结束时，cur为nullptr，prev指向最后一个节点。此时最后一个节点已经变成了新链表的头，所以必须返回prev，而不是cur。

递归版本也可以实现，思路是“先反转后面的链表，再把当前节点接上”：

cpp复制ListNode* reverseListRecursive(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* newHead = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

递归版本理解起来稍微绕，但代码更短，面试时如果被追问，能写出来会很加分。

3.4 快慢指针：找中点和检测环的通用玩法

快慢指针是链表里最实用的技巧之一，思路就是让两个指针以不同速度遍历链表。最常见的是找中间节点：快指针每次走两步，慢指针每次走一步。当快指针到达末尾时，慢指针恰好走到中间位置。

cpp复制ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

这个写法有几个边界需要注意。循环条件必须同时判断fast != nullptr和fast->next != nullptr，否则fast->next->next这一句可能对空指针做解引用，直接崩溃。当链表只有一个节点时，fast->next为nullptr，循环直接不进入，slow就是唯一节点，结果正确。

同样的思路可以用来检测链表中是否有环：

cpp复制bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

如果链表有环，快指针最终一定会和慢指针相遇；如果无环，快指针会先走到nullptr。为什么快指针要一次走两步而不是走一步？走一步的话两个指针步调永远一致，永远无法相遇；走两步以上虽然也能在环里相遇，但可能还没有走二步稳定高效，所以二步是默认选择。

4. 空指针、虚拟头节点与内存泄漏：链表最容易翻车的三个坑

4.1 空指针：十次链表崩溃，八次栽在这个地方

链表代码里所有的问题，可以说大部分都空指针有关。最常见的崩溃场景是：头节点为空时，仍然调用head->next或head->val。

比如这样一个遍历逻辑：

cpp复制while (head->next != nullptr) {
    // 处理节点
    head = head->next;
}

链表为空时，head本身是nullptr，执行head->next的一瞬间程序就炸了。正确的写法是：

cpp复制while (head != nullptr && head->next != nullptr) {
    // ...
}

删除节点时也要先确认前驱和后继存在。我的习惯是：任何使用->运算符的地方，先问自己一句“这个指针有没有可能是空的”。这道心理防线养成后，很多崩溃问题在写代码的时候就能避免，而不是等运行时才被编译器教做人。

4.2 虚拟头节点（dummy node）：统一边界逻辑的第一选择

链表操作里最容易写错的就是边界情况：空链表插入第一个元素、删除第一个节点、在头部插入新节点。这些场景都会引入一堆if判断，代码写起来又长又容易漏。

虚拟头节点dummy可以一次性解决这些问题。它并不是真实数据节点，只是一个占位的头，它的next指向真正的第一个数据节点。所有操作都从dummy->next开始，头节点方面的边界就直接消失了。

以删除倒数第N个节点为例，这是LeetCode第19题，也是面试高频题。用dummy可以写出非常干净的代码：

cpp复制ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* fast = dummy;
    ListNode* slow = dummy;
    while (n-- > 0) fast = fast->next;      // 快指针先走n步
    while (fast->next != nullptr) {          // 快慢指针一起走
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;           // 跳过倒数第n个节点
    return dummy->next;
}

快指针先走n步，然后快慢指针同步前进。当快指针到达末尾时，慢指针正好停在倒数第n+1个节点，此时直接跳过下一个节点即可。如果没有dummy，当删除的是头节点时，处理逻辑会非常别扭。这种“先把dummy建好，最后返回dummy->next”的模式，在算法题里几乎成了标准套路。

4.3 内存管理：C/C++手写链表额外背的债

用C或C++写链表，内存管理是绕不开的。每new一个节点，到达生命周期结束就必须delete，否则就是内存泄漏。释放整个链表也要注意顺序：先把当前节点的next保存下来，再删除当前节点，否则删完当前节点后，后面的节点地址就找不到了。

cpp复制void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
}

调试内存泄漏我一般会用valgrind检查，或者编译时打开AddressSanitizer（ASan）：

bash复制g++ -g -fsanitize=address main.cpp -o main
./main

ASan会在程序跑完时报告有没有内存泄漏、有没有越界访问。手写链表阶段就养成检查和排查内存的习惯，对以后做底层开发、嵌入式开发非常有帮助。Java和Python因为自带垃圾回收，不用手动delete，但如果你理解了C++的删除逻辑，更容易明白GC到底在帮你干什么。

5. 从LRU缓存到内核链表：真实项目里的链表长什么样

5.1 LRU缓存：哈希表加双向链表为什么是黄金搭档

LRU（Least Recently Used，最近最少使用）缓存是链表最经典的工程应用之一。它的需求是：缓存容量固定，每次访问某个数据就把它标记为最近使用；当缓存满时，淘汰最久没有使用的数据。

要支持O(1)的访问和O(1)的淘汰，需要两种数据结构配合。哈希表负责快速判断某个key是否存在，做到O(1)查询；双向链表负责维护数据的新旧顺序——新访问或插入的数据移动到头部，最久未使用的数据在尾部。缓存满了，直接删掉尾部节点即可。

为什么必须是双向链表？因为“把中间某个节点移动到头部”这个操作需要同时改动它的前驱和后继的指针。如果是单链表，你想把某个节点挪到头部，还得先遍历找到它的前驱，这一下就退化成了O(n)，整个缓存的效率就崩了。双向链表的prev指针让每个节点都能瞬间定位前驱，移动、删除都保持在O(1)。LeetCode第146题的LRU Cache，包括许多缓存中间件的核心思想，都是这套思路。

5.2 语言内建链表、嵌入式链表：同一个思想的不同包装

实际开发中，不太需要自己从头实现一个链表，因为主流语言都提供了现成的实现。但理解它们的差异仍然重要。

• C++的std::list是双向链表，std::forward_list是单向链表。不过日常开发中，std::vector在绝大多数场景下表现更好，因为它连续存储、缓存友好，除非你明确需要大量中间插入删除，否则不必优先选list。
• Java的LinkedList也是双向链表，但业务代码里使用频率远低于ArrayList，原因同样是缓存友好度和随机访问性能差距。
• Python的deque（双端队列）底层其实是块状双向链表，任意一端append和pop都是O(1)，比内置list在头部操作上高效得多。
• Go标准库里的container/list提供了一个通用双向链表实现。

嵌入式领域还有另一种被称为“侵入式链表”的设计，典型代表是Linux内核的list_head。它不把业务数据塞进链表节点，而是把链表节点结构嵌入到业务结构体内部。这样做的好处是整个链表的管理代码可以复用，业务数据和链表指针解耦。这种设计跟教科书里“结构体包含next指针”的思路刚好反过来，我第一次看的时候甚至有点不太适应，但理解之后会发现它在内存和灵活性上都有很大优势。

一句话总结：链表的底层思想在所有语言里是一致的，封装形式不同而已。考试和面试的重点在于你能否看透封装，直接写出核心操作。

5.3 究竟该用数组还是链表：一张决策表加三个判断原则

很多人在实际开发里纠结“到底用数组还是链表”。我的建议是，先用需求指标去套下面这张表。

三个判断原则，我总结成一句话：优先数组成员，除非插入删除需求真的非常频繁；其次看缓存性能，连续内存是硬优势；最后看内存分配策略，如果数据块太大且频繁扩容，链表反而更稳定。

6. 面试、考研与竞赛里的链表套路：常见题型和解题模板

6.1 高频面试题型和对应套路速览

算法面试中，链表题虽然不像二叉树那么花哨，但出现的频率极高，因为它在很短篇幅内就能考察候选人的指针操作功底。我梳理了几个最高频的题型和标准思路。

• 反转链表：三指针法或递归，代码模板见3.3节。
• 环形链表：快慢指针，快指针每次走两步，相遇即有环，模板见3.4节。
• 合并两个有序链表：可以用递归，也可以用迭代。

cpp复制ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val <= l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = (l1 != nullptr) ? l1 : l2;
    return dummy->next;
}

• 删除倒数第N个节点：双指针，先让快指针走N步，再同步走，模板见4.2节。
• 相交链表：先算出两个链表长度的差值，长链表先走差值步，然后同步遍历。
• 回文链表：先用快慢指针找中点，再反转后半段，逐节点比对。

这些题目有一个共性：都可以拆成“操作节点指针”这一件事。刷题的时候不用背代码，把每一步画出来，理解指针的指向变化，比死记硬背可靠得多。

6.2 实验报告、考研408和蓝桥杯里的链表题

数据结构课程里的链表实验报告，基本离不开这几件事：单链表的基本操作、两个链表的集合差集、约瑟夫环、多项式相加。

以“基于链表的两个集合的差集”为例。思路是：对于A链表中每个节点，在B链表中查找是否存在相同数据，如果存在则从A中删除。单链表删除需要前驱，所以可以一边遍历一边维护prev指针，找到需要删除的节点时直接通过prev摘除。这个题的考察点其实不是“查找”逻辑，而是“删除时前驱怎么维护”这一链表基本功。

考研数据结构408里，链表经常以选择题和算法设计题出现。选择题喜欢考不同操作的时间复杂度、带头节点和不带头节点的差异、循环链表的判空条件等。算法设计题则经常要求原地操作且不改变时间复杂度，比如原地反转、删除重复节点。蓝桥杯这类算法竞赛里，链表题更偏爱“用数组模拟链表”的写法。

6.3 用数组模拟链表：竞赛中的隐藏技巧

在很多竞赛场景下，直接new节点会产生大量内存分配开销，而且调试起来也不方便。更常见的做法是用数组来模拟链表：用下标作为节点地址，用两个数组分别存数据和下一节点的下标。

cpp复制const int MAXN = 100005;
int e[MAXN];  // e[i] 存储节点i的值
int ne[MAXN]; // ne[i] 存储节点i的下一个节点下标
int head = -1; // 头节点的下标，-1表示空链表
int idx = 0;   // 当前用到了哪个下标

void addToHead(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

这里节点之间的“指针”其实就是数组下标，ne数组的作用等同于next指针。好处是：内存分配是预先申请好的，运行速度快，打调试信息也方便。其实很多高性能基础库内部也采用类似的“池化”思路，提前分配一块连续内存，再通过下标模拟指针关系，从而兼顾效率和灵活性。

如果你在蓝桥杯或者ACM里遇到链表题，第一个想到的解法不应该是新建List节点，而是考虑这个数组模拟方案。它可能不直观，但确实能帮你避开大量new和delete的问题，让代码跑得又快又稳。

最后再分享一个我自己的习惯：刷链表题，尤其是反转链表和删除节点这类操作，动手写代码之前先在纸上画图。我第一次写反转链表时，连续改了半天bug，最后发现就是三个指针的先后顺序没想清楚。找张纸把节点和箭头画出来，标上每一步操作前后的状态，比盯着代码干想要高效得多。链表没那么神秘，但它确实会逼着你在脑子里维护一套“指针的世界观”。练熟之后，再回头看数组，你会对“连续性”三个字产生完全不同的理解。