单链表

2026 大纲 二（二）线性表的实现 · 2 链式存储。本篇是链式存储主篇，共性内容全在这里，双链表、循环链表、静态链表只写增量。

用一个指针域买断了什么

链表的结点由数据域和指针域两部分组成，指针域里存的是直接后继的地址。就这么一个改动，把顺序表那条"第 $i$ 个元素必须放在第 $i$ 个物理位置"的约定彻底废掉了——元素之间的关系不再靠位置隐含，而是被指针显式写了出来。

这笔交易的三项后果，一项赚两项赔：

赚：结点爱放哪放哪，插入删除只改指针，不必搬动任何元素；
赔：没有了位置约定，也就没法由位序算地址，取第 $i$ 个元素只能从头一步步走， $O (n)$ ；
赔：每个结点多出一个指针域，存储密度小于 1（int 与指针各 4 字节时恰好是 $1 / 2$ ）。

图里那条 $E$ 分支要特别留意：插入删除的总代价 = 定位前驱 $O (n)$ + 改指针 $O (1)$ 。 所谓"链表插删 $O (1)$ "，说的只是后半截。

先看一眼

加载可视化中...

插入和删除各走一遍，盯住箭头的改动顺序：新结点总是先接住原来的后继，然后前驱才改指向新结点。顺序反过来会发生什么，是这一篇最要紧的一处，下面「通用范式」那节会把它讲透。

结构定义与三个容易混的概念

typedef struct LNode {
    ElemType data;       // 数据域：存元素本身
    struct LNode *next;  // 指针域：存直接后继结点的地址
} LNode, *LinkList;

LinkList 和 LNode * 是同一个类型的两个名字，用哪个只是为了让代码自我说明：强调"这是一整张表"时写 LinkList，强调"这是某个结点"时写 LNode *。

头指针 → [data|next] → [data|next] → [data|next] → NULL
           结点1          结点2          结点3

带附加头结点的单链表：头指针 first 指向头结点，头结点的数据域不存有效数据（图中画成阴影），它的指针域指向首元结点 a₁；尾结点的指针域为空。空表时头结点仍在，只是它的指针域为空

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 2.9，p59。图中头指针名为 first，本文代码里叫 L，含义相同。

有三个名字长得像、含义完全不同，必须一次分清：

头指针是标识整张表的指针变量，任何链表都必有；
头结点是首元结点之前的附加结点，数据域不存有效数据，可有可无；
首元结点是存 $a_{1}$ 的那个数据结点。

它们的差别在判空条件上直接体现出来：带头结点时空表是 L->next == NULL（L 本身不为空），不带头结点时空表是 L == NULL。 判尾则一律是 p->next == NULL——链表不存 length 字段，这是"到头了"的唯一标志，求表长也因此必须走完全表， $O (n)$ 。

408 的题面若不特别说明，默认带头结点：L 永远指向头结点、不随插删改变。不带头结点时，空表变非空、删掉唯一元素都要改写 L 本身，函数参数被迫写成 LinkList &L。

⚠️ 还有一处口径必须前后一致：遍历用的计数器，带头结点是 p=L, j=0（把头结点看作"第 0 个"），不带头结点是 p=L, j=1。两套混用，找出来的结点就会差一位。

带头结点与不带头结点的两套插入代码对照（想看清头结点到底省了什么就展开）

在第 $i$ 个位置插入的通用做法是"找到第 $i - 1$ 个结点，在它后面插"。不带头结点时 $i = 1$ 没有第 0 个结点可找，只能单独写一段代码：

// 不带头结点：在第 i 个位置插入元素 e —— 注意 i == 1 必须单独处理
bool ListInsertNoHead(LinkList &L, int i, ElemType e) {
    if (i < 1) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    if (i == 1) {              // ← 特殊情况：要动的是头指针 L 本身，而不是某个结点的 next
        s->next = L;
        L = s;
        return true;
    }
    LNode *p = L;              // 不带头结点时，L 就是第 1 个结点
    int j = 1;                 // 所以计数器从 1 起算，而不是从 0
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) { free(s); return false; }
    s->next = p->next;
    p->next = s;
    return true;
}

带头结点后，头结点可以看作"第 0 个结点"， $i = 1$ 时前驱就是它，特判整段消失：

// 带头结点：在第 i 个位置插入元素 e —— 没有任何位置需要特判
bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) return false;
    LNode *p = L;                      // p 指向头结点，视作"第 0 个结点"
    int j = 0;                          // 计数器从 0 起算
    while (p != NULL && j < i - 1) {    // 找第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == NULL) return false;        // 走到表外，说明 i 超过 length+1，非法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = p->next;                  // ① 新结点接住 p 原来的后继
    p->next = s;                        // ② p 改指向新结点
    return true;
}

边界自查（带头结点版，设表长为 $n$ ）：

$i = 1$ ：循环条件 j < 0 不成立，p 停在头结点，在头结点后插入，即插到表头，正确；
$i = n + 1$ ：循环走 $n$ 步，p 停在第 $n$ 个结点（尾结点），在其后插入，正确；
$i = n + 2$ ：循环走到 $j = n$ 时 p 已是尾结点，再走一步 p 变 NULL，循环因 p == NULL 退出，返回 false，正确；
空表插 $i = 1$ ：p = L（头结点），循环不执行，直接插在头结点后，正确。

头结点省掉的是两类特殊情况：一是空表与非空表的判别不统一（不带头结点时头指针本身会变），二是第 1 个位置的操作与其他位置不统一。所以它的作用不是"让链表更规范"，而是把两类边界情况变成普通情况——带头结点的插删代码里，一个 if 特判都不必多写。

建表：头插法与尾插法

	头插法（逆序建表）	尾插法（正序建表）
循环体	`s->next = L->next; L->next = s;`	`r->next = s; r = s;`
建表前 / 后	前：`L->next = NULL`，不能省——第一个插入的结点靠这句拿到 `NULL` 成为尾结点	前：`r = L`（空表时头结点就是"尾"）；后：`r->next = NULL` 封尾
结果	与输入顺序相反	与输入顺序一致
代价	不需要尾指针，代码更短	必须维护尾指针 `r`，否则每插一个都要找尾，退化成 $O (n^{2})$

两法都是 $O (n)$ 。头插法"自带逆序"这一性质本身是有用的——链表逆置就是靠它实现的，见下文。

头插法与尾插法建表的完整代码（要默写建表时展开）

// 头插法（逆序建表）：每次插到头结点之后，最后读入的排在最前
LinkList HeadInsert(LinkList &L) {
    LNode *s; int x;
    L = (LinkList)malloc(sizeof(LNode));   // 建头结点
    L->next = NULL;                        // 先造成一个空表，这一步不能省
    while (scanf("%d", &x) == 1) {         // 读到合法整数就继续
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;                 // 新结点接住原来的第一个结点
        L->next = s;                       // 头结点改指向新结点
    }
    return L;
}

// 尾插法（正序建表）：r 始终指向当前的最后一个结点
LinkList TailInsert(LinkList &L) {
    LNode *s, *r; int x;
    L = (LinkList)malloc(sizeof(LNode));
    r = L;                                 // 尾指针初始指向头结点
    while (scanf("%d", &x) == 1) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;                             // 尾指针跟着后移
    }
    r->next = NULL;                        // 循环结束后统一封尾，比在循环里每次赋值省事
    return L;
}

⚠️ 省掉 L->next = NULL，尾结点的指针域就是野值，遍历会一路走到内存里去。 ⚠️ 省掉尾指针 r，每插一个元素都要从头找一遍表尾，建表就从 $O (n)$ 退化成 $O (n^{2})$ 。

插入与删除的通用范式

整篇最该记住的是这一句，它能推出后面所有指针操作的正确写法：

任何一次指针修改前，先问"这个指针域里现在存着的地址，之后还有没有人需要？"有，就必须先让新结点接住它，再覆盖。

// 后插：在结点 p 之后插入 s
bool InsertNextNode(LNode *p, LNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;    // ① 先让 s 接住 p 的原后继
    p->next = s;          // ② 再让 p 指向 s
    return true;
}

// 按位序删除第 i 个结点，用 e 返回其值（带头结点）
bool ListDelete(LinkList &L, int i, ElemType &e) {
    if (i < 1) return false;
    LNode *p = L; int j = 0;
    while (p != NULL && j < i - 1) { p = p->next; j++; }  // 找第 i-1 个结点（前驱）
    if (p == NULL || p->next == NULL) return false;       // 后半句拦住 i = n+1：前驱是尾结点，无结点可删
    LNode *q = p->next;    // ① q 先记住被删结点，否则地址丢失、free 不掉
    e = q->data;
    p->next = q->next;     // ② 前驱越过被删结点
    free(q);               // ③ 最后才释放：反过来就是读已释放内存
    return true;
}

🔴 后插那两句写反的后果不是"少接一个结点"，而是丢掉整个后半段。原后继的地址全链只此一份，先写 p->next = s 就把它覆盖掉了—— $p$ 之后的所有结点既找不回来，也 free 不掉。

删除也是同一条范式的应用，只是方向反过来：q 必须先记住被删结点（否则 p->next = q->next 一执行，那个地址就没人存了），free(q) 必须最后做（否则就是在读已经释放的内存）。

按位查找和按值查找则体现了链表的另一面：不能算地址，只能一步步走。找第 $i$ 个要走 $i$ 步，等概率下平均 $\frac{1}{n} \sum_{i = 1}^{n} i = \frac{n + 1}{2}$ 步，最坏 $n$ 步。

// 按位查找：返回第 i 个结点的指针；i = 0 时返回头结点
LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    LNode *p = L; int j = 0;
    while (p != NULL && j < i) { p = p->next; j++; }
    return p;          // i 超出表长时 p 为 NULL，调用方据此判失败
}

// 按值查找：平均比较 (n+1)/2 次，O(n)
LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;                    // 从首元结点开始，头结点不存数据
    while (p != NULL && p->data != e) p = p->next;
    return p;                              // 找到返回结点指针，未找到 p 为 NULL
}

⚠️ 注意 p = L->next 而不是 p = L。 带头结点时头结点的数据域没有意义，从 L 开始比较会把头结点里的垃圾值也拿来比。这是"带头结点"口径下最容易犯的一处笔误。

前插与删除自身的两个常数时间技巧（题目只给结点指针、要求就地操作时展开）

按定义，前插和删除自身都需要 $p$ 的前驱，而单链表只能向后走，找前驱 $O (n)$ 。两个技巧都把它降到 $O (1)$ ，原理同源：链表的逻辑次序由指针决定、内容由数据域承载，两者可以分开操作。

// 在 p 之前插入 s：先后插，再交换两个结点的数据域
bool InsertPriorNode(LNode *p, LNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;            // ① 先把 s 后插到 p 之后
    p->next = s;
    ElemType tmp = p->data;       // ② 再交换 p 与 s 的数据域
    p->data = s->data;
    s->data = tmp;
    return true;
}

// 删除结点 p 本身（p 不能是尾结点）
bool DeleteNode(LNode *p) {
    if (p == NULL || p->next == NULL) return false;   // 尾结点用此法删不掉
    LNode *q = p->next;
    p->data = q->data;      // 把后继的值搬到 p 里
    p->next = q->next;      // 再把后继从链上摘掉
    free(q);
    return true;
}

前插为什么对：交换数据域之后， $p$ 这个存储单元里装的是新元素的值、 $s$ 里装的是原来的值，而 $p$ 在链上的位置在 $s$ 之前——于是"新元素排在原元素之前"这个逻辑要求被满足了。

这两个技巧各有死角，而且死角本身就是考点：前插法会让指向原结点的外部指针失效（题目要求"不得改变结点的相对地址"时不能用）；删除自身法对尾结点无效（没有后继可搬，只能找前驱 $O (n)$ ）。后者正是双链表的价值所在——双链表里删除任意结点（含尾结点）都是真正的 $O (1)$ 。

逆置

逆置有两种写法，都是 $O (n)$ 时间、 $O (1)$ 辅助空间，也都是上面那条范式的直接应用。

方法一：头插法逆置。 头插法建表的结果天然是输入的逆序，所以把原链表从头到尾摘下每个结点、依次头插回去，得到的就是逆序表。

void ReverseList(LinkList &L) {
    LNode *p = L->next;    // p 指向第一个数据结点
    LNode *r;              // r 用于暂存 p 的后继
    L->next = NULL;        // ① 头结点断开，此刻起把 L 当作一张空表来头插
    while (p != NULL) {
        r = p->next;       // ② 先存后继，否则下一句就把它覆盖了
        p->next = L->next; // ③ 头插：p 接住当前的第一个结点
        L->next = p;       // ④ 头结点改指向 p
        p = r;             // ⑤ 处理下一个
    }
}

方法二：指针就地反转。 用三个指针 pre、p、r 一起前进，把每个结点的 next 从"指向后继"改成"指向前驱"。

void ReverseList2(LinkList &L) {
    LNode *pre, *p = L->next, *r;
    if (p == NULL) return;      // 空表直接返回
    pre = NULL;                 // 原来的首元结点将成为新的尾结点，其 next 应为 NULL
    while (p != NULL) {
        r = p->next;            // ① 先存后继——下一句就要把它毁掉
        p->next = pre;          // ② 反转指针
        pre = p;                // ③ pre、p 一起后移
        p = r;
    }
    L->next = pre;              // ④ 循环结束时 pre 指向原来的尾结点，让它当新的首元结点
}

方法二的循环不变量是：每轮开始时，pre 指向已反转部分的头，p 指向未反转部分的头，两部分已经断开；循环结束时未反转部分为空，pre 正好指向整条反转链的头。

🔴 两法共同的死穴是 r = p->next——它必须是循环体的第一句，因为紧接着的一句就会覆盖 p->next。这仍然是那条范式：即将被覆盖的地址，此刻还有人需要，就得先存下来。

	头插法逆置	指针就地反转
依赖头结点	依赖，靠 `L->next` 当插入点	不依赖，最后一步才用到 `L`
指针变量数	2 个（`p`、`r`）	3 个（`pre`、`p`、`r`）
时间 / 空间	$O (n)$ / $O (1)$	$O (n)$ / $O (1)$
容易写错的地方	忘了先 `L->next = NULL`	忘了最后 `L->next = pre`

各操作复杂度的完整来历，以及与顺序表的定量对比（想知道每个量级怎么来的、"链表赔了多少"就展开）

操作	时间复杂度	来历
头插法建表	$O (n)$	每个结点插入 $O (1)$ ，共 $n$ 个
尾插法建表	$O (n)$	同上；前提是维护了尾指针，否则每次找尾退化为 $O (n^{2})$
按位查找第 $i$ 个	$O (n)$	走 $i$ 步；等概率下平均 $\frac{n + 1}{2}$ 步，最坏 $n$ 步
按值查找	$O (n)$	平均比较 $\frac{n + 1}{2}$ 次，最坏 $n$ 次
后插（已知 `p`）	$O (1)$	只改 2 个指针，与 $n$ 无关
前插（已知 `p`，用交换数据域法）	$O (1)$	后插 + 交换数据域，均为常数步
前插（已知 `p`，需保持结点地址不变）	$O (n)$	必须从头遍历找前驱
按位序插入第 $i$ 个	$O (n)$	定位前驱 $O (n)$ + 改指针 $O (1)$
删除结点 `p` 自身（`p` 非尾结点）	$O (1)$	搬数据 + 摘后继
删除结点 `p` 自身（`p` 是尾结点）	$O (n)$	无后继可搬，只能找前驱
按位序删除第 $i$ 个	$O (n)$	定位前驱 $O (n)$ + 改指针 $O (1)$
逆置	$O (n)$	每个结点被处理常数次，恰好遍历一遍
求表长	$O (n)$	必须走完全表数数——链表不存 `length` 字段

空间复杂度：上述所有操作都只使用常数个指针变量作为辅助，均为 $O (1)$ 。逆置也是 $O (1)$ ——它是"就地"修改指针，没有开辅助数组。

与顺序表的空间对比（设有 $n$ 个 int 元素，指针与 int 同宽，各 4 字节）

	顺序表	单链表
每个元素占用	4 字节	4（数据） + 4（指针） = 8 字节
$n$ 个元素合计	$4 n$	$8 n$
存储密度	$4 / 4 = 1$	$4 / 8 = 0.5$
空间利用率	100%（不计空闲区）	50%
是否要求连续空间	是，必须一整块	否，结点可散落
空间何时确定	预先按上限分配	按需申请，只受内存总量限制

和顺序表比，赔了多少赚了多少

操作	顺序表	单链表	谁赢
按位查找第 $i$ 个	$O (1)$ （算地址）	$O (n)$ （走 $i$ 步）	顺序表，且是数量级差距
按值查找（无序）	$O (n)$ ，平均比较 $\frac{n + 1}{2}$ 次	$O (n)$ ，平均比较 $\frac{n + 1}{2}$ 次	平手
按位序插入 / 删除	$O (n)$ ，平均移动 $\frac{n}{2}$ / $\frac{n - 1}{2}$ 个元素	$O (n)$ ，平均走 $\frac{n + 1}{2}$ 步后改常数个指针	链表，尤其当元素体积大时
已知位置插入 / 删除	仍是 $O (n)$ ——元素照样得挪	$O (1)$	链表

第三行是最容易含糊的一行：两边都写着 $O (n)$ ，但这两个 $O (n)$ 的常数因子完全不是一回事。顺序表搬的是元素——每个元素多大就搬多少字节；链表走的是指针——每步只读一个地址。当元素是一个 200 字节的结构体时，顺序表要搬约 $200 \times n / 2$ 字节，链表只需读 $n / 2$ 个指针。教材把这件事写成"尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观"。

空间上的账则要看数据域相对指针有多大：数据域是 int 时存储密度只有 0.5，是 100 字节的结构体时约 $\frac{100}{104} \approx 0.96$ ，指针几乎不构成负担。反过来，顺序表若按上限预分配而实际只用了一小半，它的实际空间利用率也可以远低于 50%。所以"链表费空间"是一句有条件的话，条件是数据域小、且顺序表的容量估得准。

考点速记

三条会被反复调用的结论：

链表用一个指针域的空间，买断了"元素必须挨着放"这条约束：赚到插删不搬元素，赔上只能顺序存取。
头结点不是装饰，它把两类边界情况变成了普通情况，带头结点的代码里一个特判都不需要。
指针修改的顺序不是习惯问题，是正确性问题——判据只有一条：即将被覆盖的地址，此刻是否还有别处存着它。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

给一串指针语句，问它干了什么：题面给出四五句形如 q=p->next; p->next=q->next; q->next=h->next; h->next=q; 的代码，要你说出功能。逐句在纸上画箭头是唯一可靠的读法——这段做的是"把 p 的后继摘下来，插到头结点之后"。
给一张存储状态表，问插入后各结点的链接地址：表里逐行列出"地址 / 元素 / 链接地址"，要你把新结点插进逻辑上的某两个元素之间，再回答几个结点的指针值。做法同样是画图，注意题目问的是哪几个结点的链接地址，别把顺序答反。
问某个链表操作的最坏时间复杂度：例如把两个长度为 $m$ 、 $n$ 的升序链表合并成一个降序链表，每个结点只被处理一次，是 $O (m + n)$ ，也就是 $O (max (m, n))$ 。
大题里的链表算法设计：查找倒数第 $k$ 个结点、找两个链表的公共后缀、按绝对值去重、重排链表等，共同要求是 $O (n)$ 时间、 $O (1)$ 辅助空间——本篇的范式和逆置是它们的公共零件。

易错：两句指针赋值写反，丢掉整个后半段。 s->next = p->next 必须在 p->next = s 之前。删除时同理：q 先记住被删结点，free(q) 最后做。

易错："链表插删 $O (1)$ "要看题目给的是什么。 给指针才是 $O (1)$ ；给位序就是 $O (n)$ ，定位那一步跑不掉。

易错：遍历起点写成了 p = L。 带头结点时按值查找必须从 p = L->next 开始，否则会把头结点里的垃圾值拿来比较。

易错："删除结点自身 $O (1)$ "对尾结点无效。 那个技巧是靠"把后继的值搬过来再摘掉后继"实现的，尾结点没有后继可搬，只能老老实实找前驱， $O (n)$ 。

教材出处

结点的构成（数据域 + 指针域）、链式存储"用一组任意的存储单元"存放元素：严蔚敏《数据结构（C 语言版）》（第 2 版），p29–p30，2.5.1 节。
LinkList 与 LNode * 两个名称本质等价的说明，以及首元结点、头结点、头指针 三个概念的逐条辨析、"链表增加头结点的作用"（便于首元结点的处理、便于空表和非空表的统一处理）：同书 p31。
带头结点时判定空表的条件 L->next == NULL，以及"单链表是非随机存取的存储结构，要取得第 $i$ 个数据元素必须从头指针出发顺链进行寻找"：同书 p32。
前插法（头插法）建表 CreateList_H 与后插法（尾插法）建表 CreateList_R，以及两者时间复杂度均为 $O (n)$ ：同书 p37–p38。
顺序表与链表在存储密度（顺序表为 1、整型结点单链表为 0.5）、存取效率、 插入删除效率三方面的对比，含"尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观"：同书 p41，2.6 节。

真题练习

2024Q12分 2019Q4113分 2017Q112分 2016Q12分 2015Q4115分 2013Q12分 2012Q4212分 2009Q4215分

单链表

用一个指针域买断了什么

先看一眼

结构定义与三个容易混的概念

建表：头插法与尾插法

插入与删除的通用范式

逆置

和顺序表比，赔了多少赚了多少

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（8题）

单链表 ​

用一个指针域买断了什么 ​

先看一眼 ​

结构定义与三个容易混的概念 ​

建表：头插法与尾插法 ​

插入与删除的通用范式 ​

逆置 ​

和顺序表比，赔了多少赚了多少 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（8题）

单链表

用一个指针域买断了什么

先看一眼

结构定义与三个容易混的概念

建表：头插法与尾插法

插入与删除的通用范式

逆置

和顺序表比，赔了多少赚了多少

考点速记

相关知识

真题练习