Skip to content

链表

单链表、双链表与循环链表的实现,以及用数组模拟链表的写法。

Updated View as Markdown

数组的优点是访问快,随便给个下标就能 O(1) 拿到元素。它的缺点是插入和删除麻烦:往中间插一个元素,后面的都得往后挪。

链表换了个思路。它不要求元素连续存放,每个元素记住下一个元素在哪。这样插入和删除只需改几个「指针」,缺点是访问第 k 个元素得从头一个个走过去。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

考试 大纲要求 本章位置
GESP C++ 五级 考点 3:链表的创建、插入、删除、遍历和反转,单链表、双链表、循环链表的区别 全章
CSP-J/S 入门级 3.1 线性结构:单链表、双向链表、循环链表 全章

数组与链表的对比

对比项 数组 链表
存储方式 连续内存 分散,靠指针连接
随机访问第 k 个 O(1) O(n)
已知位置后插入或删除 O(n),要移动元素 O(1),只改指针
查找某个值 O(n) O(n)
额外空间 无 每个节点多存一个指针

结论很简单:经常随机访问就用数组,经常在中间插入删除就用链表。竞赛里绝大多数情况数组更划算,链表更多出现在需要频繁增删的场景,以及初赛的阅读程序题里。

单链表

单链表的每个节点存两部分:数据,以及指向下一个节点的指针。

struct Node {
    int data;    // 数据域
    Node *next;  // 指针域,指向下一个节点
};

一个链表用一个头指针标记起点。如果头指针是 NULL(或 nullptr),说明链表为空。

建立链表(头插法)

头插法每次把新节点放到最前面。读入 1 2 3,建出来的链表是 3 → 2 → 1。

Node *head = NULL;
for (int i = 1; i <= n; i++) {
    Node *p = new Node;  // 申请一个新节点
    p->data = a[i];
    p->next = head;      // 新节点指向原来的头
    head = p;            // 头指针移到新节点
}

建立链表(尾插法)

尾插法保持读入顺序。读入 1 2 3,链表就是 1 → 2 → 3。

Node *head = NULL, *tail = NULL;
for (int i = 1; i <= n; i++) {
    Node *p = new Node;
    p->data = a[i];
    p->next = NULL;
    if (head == NULL) {
        head = tail = p;  // 第一个节点
    } else {
        tail->next = p;   // 接到尾巴后面
        tail = p;         // 尾巴后移
    }
}

遍历

for (Node *p = head; p != NULL; p = p->next) {
    cout << p->data << " ";
}

查找

Node *find(Node *head, int x) {
    for (Node *p = head; p != NULL; p = p->next) {
        if (p->data == x) return p; // 找到就返回节点地址
    }
    return NULL; // 没找到
}

在节点 p 之后插入

Node *q = new Node;
q->data = x;
q->next = p->next; // 先让新节点接上后面
p->next = q;       // 再让 p 指向新节点

这两行的顺序不能反。如果先写 p->next = q,原来 p 后面的那串节点就丢了。

删除节点 p 之后的节点

Node *q = p->next;
p->next = q->next; // 跳过 q
delete q;          // 释放内存

删除头节点

头节点没有前驱,要单独处理。

if (head != NULL) {
    Node *q = head;
    head = head->next;
    delete q;
}

这个「头节点要特殊处理」的麻烦,可以用一个不存数据的虚拟头节点(也叫哨兵)绕开,让所有节点的删除逻辑统一。

双向链表

双向链表的节点多存一个指向前驱的指针,可以往前也能往后走。

struct DNode {
    int data;
    DNode *prev; // 指向前一个
    DNode *next; // 指向后一个
};

在节点 p 之后插入 q:

q->next = p->next;
q->prev = p;
if (p->next != NULL) p->next->prev = q; // 后面还有节点才需要
p->next = q;

代价是每个节点多一个指针,插入删除要改更多地方,写错一处整条链就断了。

循环链表

循环链表把尾节点的 next 指回头节点,形成一个环。从任意一个节点出发,一直走都能回到自己。

循环链表没有天然的「末尾」,遍历时要记住起点,走到回到起点为止:

Node *p = head;
do {
    cout << p->data << " ";
    p = p->next;
} while (p != head);

约瑟夫环问题用循环链表描述最自然。

反转单链表

经典题,也是初赛阅读程序的高频素材。

Node *reverse(Node *head) {
    Node *prev = NULL, *cur = head;
    while (cur != NULL) {
        Node *nxt = cur->next; // 先记住下一个
        cur->next = prev;      // 当前节点指向前一个
        prev = cur;            // prev 前进
        cur = nxt;             // cur 前进
    }
    return prev; // 新头指针
}

三根指针依次挪动,走完一遍就反转了,时间 O(n),额外空间 O(1)。

用数组模拟链表

竞赛里 new 和 delete 很慢,而且容易忘记释放。常见做法是用两个数组模拟:一个存数据,一个存「下一个节点的下标」。

const int N = 100005;
int val[N], nxt[N];
int head = -1, cnt = 0; // head = -1 表示空链表

void insert_head(int x) {  // 头插
    val[cnt] = x;
    nxt[cnt] = head;
    head = cnt++;
}

void insert_after(int p, int x) { // 在 p 之后插入
    val[cnt] = x;
    nxt[cnt] = nxt[p];
    nxt[p] = cnt++;
}

void erase_after(int p) { // 删除 p 之后的节点
    nxt[p] = nxt[nxt[p]];
}

用 -1 表示「没有下一个」,遍历时判断 p != -1 即可。这种写法在初赛阅读程序里很常见,看到两个数组加一个 nxt,基本就是链表。

复杂度

操作 单链表 双向链表
访问第 k 个 O(n) O(n)
已知位置插入/删除 O(1) O(1)
在头部插入/删除 O(1) O(1)
遍历整个链表 O(n) O(n)

常见易错点

  • 插入时先接后面再接前面,顺序反了会丢链。
  • 删除后要 delete,或者改用数组模拟。
  • 头节点、尾节点要单独处理,忘了就崩。
  • 遍历循环链表不能用 p != NULL,永远为真,要用起点判断。
  • -> 和 . 别混:指针访问成员用 ->,对象访问成员用 .。
  • 链表不支持下标访问,l[i] 这种写法只属于数组和 vector。
  • 反转链表时先改指针、后存后继。顺序反了就直接丢链,后面的节点全找不回来。
  • 数组模拟链表用 0 表示空。0 是合法下标,必须用 -1 表示「没有下一个」。
  • 约瑟夫环走了 m 步而不是 m-1 步。当前节点自己已经报了 1。
  • 循环链表删除后忘记维护前驱。单向链表没法回头,prev 要在移动时顺手记下来。

练习

练习 1:反转单链表

题目描述

给定 n 个整数,用链表存储,把它们反转后输出。

输入格式

第一行一个整数 n;第二行 n 个整数。

输出格式

输出一行 n 个整数,为反转后的序列。

输入输出样例

输入

5
1 2 3 4 5

输出

5 4 3 2 1

数据范围

  • 1 \le n \le 10^5,元素在 int 范围内。

题目分析

反转链表是链表操作里最经典、也最能考出「你有没有真的理解指针」 的一道题。核心是三指针法:

  • prev:已经反转好的部分的头(初始为「空」);
  • cur:当前要处理的节点;
  • nxt:暂存 cur 的下一个节点(必须先存下来,因为 cur->next 马上就要被改掉)。

每一步做三件事:

  1. 先把 cur 的下一个节点存进 nxt(不然改完就找不到了);
  2. 把 cur 的 next 指向 prev(完成这一步的反转);
  3. prev 和 cur 各往前走一格。

走完一遍,prev 就是新链表的头。

为什么第 1 步不能省? 这是链表题最典型的坑:一旦写下 cur->next = prev,原来的后继就永久丢失了,后面的节点全部「断链」找不回来。

用数组模拟的写法(竞赛里更常用,避免 new 的开销)只需要把「指针」换成「下标」:

int prev = -1, cur = head;
while (cur != -1) {
    int nx = nxt[cur];   // 1. 存后继
    nxt[cur] = prev;     // 2. 反转指向
    prev = cur;          // 3. 前进
    cur = nx;
}
head = prev;             // 新的头

注意用 -1 表示空(而不是 0),因为 0 是合法的数组下标。这个约定和正文一致。

参考代码

练习 2:约瑟夫环(循环链表)

在线评测练习:P1423 报数出圈

题目描述

n 个小朋友围成一圈,编号从 1 到 n。从 1 号开始顺时针报数,报到 m 的人出圈,他旁边的人从 1 重新开始报数。按顺序输出所有出圈的小朋友的编号。

输入格式

输入一行,包含两个正整数 n 和 m,中间用一个空格隔开。

输出格式

输出一行,包含 n 个整数,依次为出圈的小朋友的编号,相邻两个整数之间用一个空格隔开。

输入输出样例

输入

5 3

输出

3 1 5 2 4

输入

1 1

输出

1

数据范围

  • 1 \le n \le 1000,1 \le m \le 1000。

题目分析

这是「循环链表」最标准的应用场景:一圈人天然对应一个首尾相连的链表,出圈就是「删除一个节点」,然后从下一个节点接着数。

用数组模拟循环链表,写法比真指针干净得多:

  1. 建表:nxt[i] = i + 1,最后 nxt[n] = 1(首尾相连);
  2. 循环 n 次,每次:
    • 走 m - 1 步(因为当前这个人自己就报了 1,所以只需再走 m-1 步);
    • 输出当前节点,然后把它从链表里删掉:nxt[prev] = nxt[cur];
    • cur 移到下一个节点,继续。
  3. 因为只有一个人时 nxt[cur] = cur(自己指向自己),删除后仍然指向自己,所以循环能自然终止。

最容易错的两个地方:

  1. 走 m-1 步而不是 m 步。想一想:cur 指向的人现在报的是 1,报 2 要走到下一个,……,报到 m 一共走了 m-1 步。
  2. 删除时要维护 prev。数组模拟的单向循环链表没法回头,所以循环里要始终记住「当前节点的前一个」:
for (int step = 1; step < m; step++) {
    prev = cur;        // 记住前驱
    cur = nxt[cur];    // 前进
}
nxt[prev] = nxt[cur];  // 删除 cur
cur = nxt[cur];        // 从下一个继续

为什么不用双向链表或直接 vector 删除? vector 删除中间元素是 O(n),总复杂度 O(n^2) 到 O(n^3);链表删除是 O(1)。本题 n \le 1000 用 vector 也能过,但链表才是这个问题的「正确」数据结构——这也是本章为什么把约瑟夫环放在链表这一节。

想进一步优化到 O(n),需要用「递推公式」f(n) = (f(n-1) + m) \bmod n(只能求最后剩下的那个人,不能输出全部出圈顺序)。见《找规律与打表》那一章的示例。

参考代码

小结

  • 链表用指针把分散的节点串起来,插入删除 O(1),但随机访问要 O(n)。
  • 单链表只能往后走,双向链表能双向走,循环链表首尾相连。
  • 头插法会反转顺序,尾插法保持顺序。
  • 竞赛里常用两个数组模拟链表,避免 new / delete 的开销。
  • 反转链表用三指针法,必须先把后继存下来再改指针,否则会断链。
  • 约瑟夫环用循环链表:nxt[n] = 1 首尾相连,出圈就是删除节点,注意「走 m-1 步」和维护前驱。
  • 用数组模拟时用 -1 表示「空」,不要用 0(0 是合法下标)。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close