前言

线性表是数据结构中第一个真正进入“存储结构与算法实现”的章节，也是后续栈、队列、树、图等内容的基础。

按照408考试大纲，本章需要掌握：

1. 线性表的基本概念；

2. 线性表的顺序存储；

3. 线性表的链式存储；

4. 线性表的典型应用。

从历年真题看，线性表并不是只考“定义”的小章节。2009—2026年间，顺序表相关内容在8个年份出现，共涉及10道选择题或综合题；链表相关内容在10个年份出现，共涉及12道选择题或综合题。

命题形式主要有四类：

• 判断顺序表各种操作的时间复杂度和元素移动次数；

• 补全单链表、双链表或循环链表的指针语句；

• 分析头结点、尾指针、空表和单结点表等边界情况；

• 设计时间和空间尽可能高效的链表综合算法。

本章的学习目标不是把代码背下来，而是做到：

看到局部链表结构时，能够画出指针关系；看到算法要求时，能够选择合适的存储结构并分析复杂度。

---

一、本章知识框架

本章可以分为五部分：

1. 线性表的逻辑结构与基本操作；

2. 顺序表的存储、访问、插入和删除；

3. 单链表的结点、查找、插入和删除；

4. 双链表、循环链表与静态链表；

5. 线性表综合算法及复杂度分析。

其中：

• 顺序表重点考“随机访问、元素移动和复杂度”；

• 链表重点考“指针修改、边界条件和综合算法”。

---

二、线性表的基本概念

1. 线性表的定义

线性表是由n个具有相同数据类型的数据元素组成的有限序列，通常记为：

L = (a1, a2, a3, …, an)

其中：

• n为表长；

• n = 0时称为空表；

• a1称为表头元素；

• an称为表尾元素。

在线性表中：

• 除第一个元素外，每个元素有且仅有一个直接前驱；

• 除最后一个元素外，每个元素有且仅有一个直接后继。

这里描述的是元素之间的逻辑关系，并没有规定元素必须如何存放。

2. 线性表是逻辑结构

线性表属于线性逻辑结构，可以采用不同的存储方式实现：

• 使用连续存储单元实现，得到顺序表；

• 使用结点和指针实现，得到链表。

因此：

线性表是逻辑结构；顺序表和链表是线性表的两种存储实现。

3. 线性表的常见基本操作

常见操作包括：

• InitList：初始化；

• Length：求表长；

• LocateElem：按值查找；

• GetElem：按位序查找；

• ListInsert：插入元素；

• ListDelete：删除元素；

• Empty：判断是否为空；

• DestroyList：销毁线性表。

考试经常不直接问函数名，而是问某个操作采用顺序表或链表实现时的复杂度。

---

三、顺序表

1. 顺序表的存储特点

顺序表使用一组地址连续的存储单元，依次存放线性表中的元素。

若第一个元素的地址为LOC(a1)，每个元素占用L个字节，则第i个元素的地址为：

LOC(ai) = LOC(a1) + (i - 1) × L

因此，只要知道起始地址和元素位序，就能直接计算目标地址。

这就是顺序表支持随机访问的原因。

2. 顺序表的基本定义

静态分配示例：

#define MaxSize 100

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

动态分配示例：

typedef struct {
    int *data;
    int maxSize;
    int length;
} SeqList;

动态分配只是允许存储空间在运行时申请或扩容，并不会改变顺序表地址连续、支持随机访问的基本特征。

3. 顺序表的随机访问

访问第i个元素：

x = L.data[i - 1];

只需要一次地址计算，因此时间复杂度为O(1)。

注意：

随机访问指按位序直接访问，不代表按值查找也是O(1)。

若要查找值等于x的元素，通常需要从头扫描，时间复杂度为O(n)。

4. 顺序表插入

在长度为n的顺序表中，将新元素插入第i个位置，其中1 ≤ i ≤ n + 1。

为了保持原有元素的相对次序，需要将第i个元素及其后的元素依次后移。

需要移动的元素个数为：

n - i + 1

典型代码：

bool ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) {
        return false;
    }
    if (L->length >= MaxSize) {
        return false;
    }

    for (int j = L->length; j >= i; --j) {
        L->data[j] = L->data[j - 1];
    }

    L->data[i - 1] = e;
    L->length++;
    return true;
}

不同位置的移动次数：

• 表头插入：移动n个元素；

• 表中插入：移动若干元素；

• 表尾插入：移动0个元素。

若各插入位置等概率，平均移动次数约为n / 2，因此平均时间复杂度为O(n)。

5. 顺序表删除

删除第i个元素，其中1 ≤ i ≤ n。

删除后，为了填补空缺，需要将第i + 1个元素及其后的元素依次前移。

需要移动的元素个数为：

n - i

典型代码：

bool ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) {
        return false;
    }

    *e = L->data[i - 1];

    for (int j = i; j < L->length; ++j) {
        L->data[j - 1] = L->data[j];
    }

    L->length--;
    return true;
}

不同位置的移动次数：

• 表头删除：移动n - 1个元素；

• 表中删除：移动若干元素；

• 表尾删除：移动0个元素。

平均移动次数约为(n - 1) / 2，平均时间复杂度为O(n)。

6. 顺序表常见操作复杂度

操作	时间复杂度	原因
按位序访问第i个元素	O(1)	可直接计算地址
按值查找	O(n)	最坏需要扫描整个表
表头插入	O(n)	原有元素全部后移
表尾插入	O(1)	空间足够时无需移动元素
表头删除	O(n)	后续元素全部前移
表尾删除	O(1)	无需移动其他元素
已知位置修改元素	O(1)	可直接定位

必须注意题目的前提：

若题目已经说明存储空间足够，则不考虑扩容成本；若动态数组需要扩容，单次尾插可能达到O(n)，但采用倍增扩容时，连续尾插的均摊复杂度仍可达到O(1)。

7. 顺序表的优缺点

优点：

• 支持随机访问；

• 存储密度高，不需要额外指针域；

• 内存连续，缓存局部性较好。

缺点：

• 插入和删除通常需要移动元素；

• 静态分配时容量固定；

• 动态扩容可能需要重新申请空间并复制全部元素；

• 需要较大连续存储空间。

---

四、单链表

1. 单链表的结点结构

单链表的每个结点通常包含：

• 数据域data；

• 指针域next。

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

链表中的结点不必连续存放，逻辑上的相邻关系由next指针表示。

2. 带头结点与不带头结点

不带头结点：

• 头指针直接指向第一个数据结点；

• 空表时头指针为NULL；

• 对第一个结点进行插入和删除时，需要单独处理。

带头结点：

• 头指针指向一个额外的头结点；

• 头结点通常不存放有效数据；

• 空表时头结点的next为NULL；

• 第一个数据结点的操作可以和其他位置统一处理。

考试中必须区分：

• 头指针：指向链表起始位置的指针变量；

• 头结点：链表中额外设置的第一个结点；

• 首元结点：存放第一个有效数据元素的结点。

3. 单链表不支持随机访问

要访问第i个结点，只能从头开始沿next指针逐个查找。

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;
}

因此：

• 按位序查找的时间复杂度为O(n)；

• 按值查找的时间复杂度也为O(n)。

4. 在已知结点p之后插入结点s

正确操作：

s->next = p->next;
p->next = s;

执行顺序不能随意交换。

若先执行：

p->next = s;

那么p原来的后继地址就可能丢失。此时再执行s->next = p->next，会使s指向自己，形成错误结构。

核心原则：

修改链条之前，先保存原来的后继关系。

5. 在第i个位置插入元素

若使用带头结点的单链表，应先找到第i - 1个结点，即插入位置的前驱结点p，再在p后插入新结点。

查找前驱需要O(n)，修改指针需要O(1)，所以总时间复杂度为O(n)。

高频陷阱：

“链表插入是O(1)”只有在已经得到插入位置前驱结点的条件下才成立。若还要从头查找位置，总复杂度仍是O(n)。

6. 删除p之后的结点q

LNode *q = p->next;
p->next = q->next;
free(q);

同样需要先用q保存待删除结点，否则修改p->next后就可能失去该结点地址，造成内存泄漏。

7. 已知结点p，能否O(1)删除p

若p不是尾结点，可以把p的直接后继q的数据复制到p中，再删除q：

LNode *q = p->next;
p->data = q->data;
p->next = q->next;
free(q);

这样从逻辑效果上看，相当于删除了原来p表示的数据元素。

但是：

• p必须存在直接后继；

• p是尾结点时不能使用该方法；

• 若外部程序依赖结点身份而不只是数据值，也要谨慎使用。

8. 已知结点p，在p之前插入新元素

普通做法需要找到p的前驱，时间复杂度为O(n)。

若只要求插入一个数据元素，并且允许交换数据，可以采用技巧：

1. 在p之后插入新结点s；

2. 将p原来的数据复制到s；

3. 将待插入数据写入p。

s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;

这样可在O(1)时间内实现“逻辑上的前插”。

9. 头插法建立单链表

每次将新结点插入头结点之后：

LinkList ListHeadInsert(int n) {
    LinkList L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;

    for (int i = 0; i < n; ++i) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &s->data);
        s->next = L->next;
        L->next = s;
    }

    return L;
}

头插法最终得到的结点次序与输入次序相反。

10. 尾插法建立单链表

使用尾指针r始终指向当前尾结点：

LinkList ListTailInsert(int n) {
    LinkList L = (LNode *)malloc(sizeof(LNode));
    LNode *r = L;

    for (int i = 0; i < n; ++i) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &s->data);
        r->next = s;
        r = s;
    }

    r->next = NULL;
    return L;
}

尾插法得到的结点次序与输入次序相同。

11. 单链表逆置

头插法逆置：

void Reverse(LinkList L) {
    LNode *p = L->next;
    L->next = NULL;

    while (p != NULL) {
        LNode *q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

每个结点只处理一次：

• 时间复杂度为O(n)；

• 只使用固定数量的指针，空间复杂度为O(1)。

逆置题的关键不是背代码，而是明确每轮必须先保存p->next，否则剩余链表会丢失。

---

五、双链表

1. 双链表结点

双链表的结点同时保存前驱和后继指针：

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode, *DLinkList;

双链表可以从一个结点向前或向后移动，但每个结点需要额外保存一个指针域。

2. 在结点p之后插入结点s

设p不是尾结点，局部结构原来为：

p <-> q

插入后应为：

p <-> s <-> q

完整操作可以写成：

s->next = p->next;
s->prev = p;
p->next->prev = s;
p->next = s;

这四条语句分别建立：

• s指向原后继；

• s指向前驱p；

• 原后继指向s；

• p指向s。

必须留意赋值顺序。若提前改写p->next，后续表达式中p->next的含义就会发生变化。

3. 删除p之后的结点q

DNode *q = p->next;
p->next = q->next;
q->next->prev = p;
free(q);

若q可能是尾结点，就必须先判断q->next是否为NULL；如果使用带头尾哨兵结点的双链表，可以减少这种特殊判断。

4. 双链表为什么仍不支持随机访问

双链表可以向前和向后遍历，但仍然无法根据位序直接计算结点地址。

因此：

• 已知结点时，找前驱或后继为O(1)；

• 按第i个位置查找仍为O(n)。

“能够双向访问”和“能够随机访问”不是同一概念。

---

六、循环链表

1. 循环单链表

循环单链表的最后一个结点不再指向NULL，而是指向头结点或首元结点。

带头结点时：

• 空表条件：L->next == L；

• 尾结点条件：p->next == L。

普通单链表的尾结点判断条件是p->next == NULL，两者不能混淆。

2. 只设尾指针的循环单链表

设尾指针为rear，则：

• 尾结点为rear；

• 头结点为rear->next；

• 第一个数据结点通常为rear->next->next。

这种结构的优势是：

• 访问尾结点为O(1)；

• 访问头结点或首元结点也为O(1)；

• 适合实现需要频繁访问队头和队尾的结构。

3. 删除第一个数据结点的边界情况

设链表带头结点，尾指针为rear，头结点为head = rear->next，第一个数据结点为q = head->next。

如果表中有多个数据结点：

head->next = q->next;
free(q);

如果表中只有一个数据结点，q同时也是rear：

head->next = head;
rear = head;
free(q);

高频陷阱：

删除唯一数据结点后，不仅要让头结点重新指向自己，还要把尾指针重新指向头结点。

4. 循环双链表

带头结点的循环双链表中：

• 空表时，头结点的next和prev都指向自身；

• 首元结点为head->next；

• 尾结点为head->prev。

这种结构能在O(1)时间内得到表头和表尾，但仍不支持按位序随机访问。

---

七、静态链表

静态链表使用数组模拟链表。每个数组元素包含：

• 数据域；

• 游标或下标域。

游标保存下一个元素在数组中的下标，而不是内存地址。

静态链表适用于不支持指针的环境，但在408中考频远低于顺序表、单链表和双链表。复习时应掌握其基本思想，不需要投入过多时间。

---

八、顺序表与链表的综合比较

对比项目	顺序表	单链表	双链表
存储空间	地址连续	结点可分散	结点可分散
随机访问	支持，O(1)	不支持，O(n)	不支持，O(n)
按值查找	O(n)	O(n)	O(n)
已知位置插入删除	通常需移动元素	已知前驱时O(1)	已知结点时通常O(1)
额外空间	无指针域	每结点一个指针域	每结点两个指针域
扩容	可能重新分配连续空间	逐结点动态申请	逐结点动态申请
反向遍历	不需要指针即可按下标访问	不方便	支持
缓存局部性	较好	较差	较差

选择存储结构时，应根据操作特点判断：

• 频繁按位序访问：优先考虑顺序表；

• 表长变化大、频繁插入删除：考虑链表；

• 需要从当前结点快速找到前驱：考虑双链表；

• 需要首尾循环连接：考虑循环链表。

不能简单地说“链表一定比顺序表快”或“顺序表一定比链表好”。

---

九、线性表综合算法的常见模型

1. 合并两个有序顺序表

两个升序顺序表A和B，合并为新的升序表C。

核心方法是双指针：

1. 指针i扫描A；

2. 指针j扫描B；

3. 每次把较小元素放入C；

4. 某一表结束后，将另一表剩余元素复制到C。

时间复杂度为O(m + n)，空间复杂度取决于是否另开结果数组。

2. 合并两个有序链表

两个升序单链表长度分别为m和n，可以在不申请新数据结点的情况下，通过修改指针进行合并。

若要求合并后仍为升序，通常使用尾插法。

若要求合并后为降序，可以每次取较小结点并使用头插法。

每个结点最多处理一次，因此时间复杂度为O(m + n)。

3. 删除重复元素

有序表中删除重复值：

• 顺序表：扫描并覆盖，时间O(n)；

• 有序链表：比较相邻结点并删除重复结点，时间O(n)。

无序表中删除重复值：

• 朴素双重扫描：时间O(n²)；

• 若元素值域较小，可使用辅助数组或散列表记录是否出现，将时间降低到O(n)，但需要额外空间。

综合题中必须根据题目给出的值域、空间限制和稳定性要求选方法。

4. 查找链表倒数第k个结点

使用快慢指针：

1. 快指针先走k步；

2. 快慢指针同时移动；

3. 快指针到达表尾时，慢指针指向倒数第k个结点。

时间复杂度为O(n)，空间复杂度为O(1)。

5. 查找链表中间结点

设置快慢指针：

• slow每次走一步；

• fast每次走两步。

当fast到达表尾时，slow位于中间位置。

这是链表综合题中非常常用的技巧。

6. 重新排列链表为a1、an、a2、an-1……

典型步骤分为三阶段：

1. 使用快慢指针找到链表中点，将链表分成前后两部分；

2. 原地逆置后半部分；

3. 将前半部分和逆置后的后半部分交替合并。

每个阶段都是O(n)，总时间复杂度仍为O(n)；只使用固定数量的指针，空间复杂度为O(1)。

这类综合题重点考察：

• 能否把大问题拆成多个基础链表操作；

• 能否原地完成而不申请与n相关的辅助空间；

• 能否正确处理奇数个结点和偶数个结点。

7. 按绝对值去重

若单链表结点data满足|data| ≤ n，要求只保留绝对值第一次出现的结点，可以申请长度为n + 1的辅助数组flag：

• flag[k] = 0表示绝对值k尚未出现；

• flag[k] = 1表示已经出现；

• 扫描链表，首次出现时保留，重复出现时删除。

时间复杂度为O(m)，其中m为链表长度；辅助空间复杂度为O(n)。

这类题体现了一个重要原则：

当关键字值域有限时，可以用空间换时间。

---

十、408通常怎么考

1. 顺序表元素移动次数

常见问法：

• 表头插入是否需要移动元素？

• 表尾插入是否必然移动元素？

• 删除第i个元素需要移动多少个元素？

• 哪些操作在存储空间足够时仍必然产生移动？

固定结论：

• 第i位插入：移动n - i + 1个元素；

• 删除第i位：移动n - i个元素；

• 表头插入和表头删除移动最多；

• 表尾插入和表尾删除通常不需要移动元素。

2. 复杂度辨析

常见陷阱：

• 把按位序访问和按值查找混为一谈；

• 认为链表插入删除一定是O(1)；

• 认为双链表支持随机访问；

• 忽略寻找前驱或目标位置的时间。

答题时必须把“定位”和“修改”分开分析。

3. 指针语句补全与执行顺序

常见形式：

• 给出局部链表图，补全插入或删除语句；

• 已经执行部分指针赋值，判断剩余操作；

• 判断几条语句能否交换顺序；

• 根据代码判断最终链表结构。

解题时不要只在脑中想，应该画出局部结构：

前驱p -> 当前结点q -> 后继r

每执行一条语句，就更新一次箭头。

4. 循环链表边界

重点边界包括：

• 空表；

• 只有一个数据结点；

• 删除首元结点；

• 删除尾结点；

• 尾指针是否需要更新。

只写一般情况而遗漏单结点情况，综合题会失分。

5. 综合算法题

综合题通常要求：

1. 给出基本设计思想；

2. 写出C或C++算法；

3. 说明时间复杂度；

4. 说明空间复杂度。

高分答案必须先说明算法结构，再写代码，不能直接堆出一段难以验证的指针操作。

---

十一、指针题的固定解题方法

第一步：只画局部结构

通常只需要画前驱、当前结点和后继：

p -> q -> r

双链表则同时画双向箭头。

第二步：明确最终目标

例如在p和q之间插入s，目标是：

p -> s -> q

第三步：先保存可能丢失的地址

若某条语句将覆盖唯一指向剩余链表的指针，必须先保存原地址。

常见安全模式：

q = p->next;
p->next = ...;

第四步：逐条更新箭头

不能凭印象判断代码。每执行一条赋值，都重新判断变量当前指向哪里。

第五步：检查边界条件

至少检查：

• 空表；

• 首元结点；

• 尾结点；

• 单结点表；

• 奇数长度和偶数长度。

---

十二、本章高频易错点

1. 把线性表当成存储结构，而不是逻辑结构。

2. 认为顺序表按值查找是O(1)。

3. 认为链表按位序访问也是随机访问。

4. 认为链表任何插入和删除操作都是O(1)。

5. 忽略寻找插入位置前驱结点的时间。

6. 先修改p->next，导致原后继链丢失。

7. 删除结点后忘记free，造成内存泄漏。

8. free之后继续访问已经释放的结点。

9. 混淆头指针、头结点和首元结点。

10. 混淆循环链表的表尾条件与普通链表的表尾条件。

11. 删除循环链表唯一数据结点后忘记修改尾指针。

12. 认为双链表能够双向遍历，因此支持随机访问。

13. 头插法建表后忘记元素次序会逆转。

14. 综合题只写代码，不说明设计思想和复杂度。

15. 只分析一般情况，不处理空表、单结点表和尾结点。

---

十三、必须能够快速回答的结论

• 线性表是逻辑结构，顺序表和链表是存储实现。

• 顺序表支持按位序随机访问，时间复杂度为O(1)。

• 顺序表按值查找通常为O(n)。

• 顺序表第i位插入需要移动n - i + 1个元素。

• 顺序表删除第i位需要移动n - i个元素。

• 单链表按位序查找和按值查找都为O(n)。

• 已知前驱结点时，单链表插入和删除主要修改指针，时间为O(1)。

• 双链表可以O(1)找到当前结点的直接前驱，但仍不支持随机访问。

• 带头结点的普通单链表空表条件通常为head->next == NULL。

• 带头结点的循环单链表空表条件通常为head->next == head。

• 修改链表前必须先保存可能丢失的后继地址。

• 链表逆置可以做到时间O(n)、额外空间O(1)。

• 两个有序链表合并的时间复杂度为O(m + n)。

• 快慢指针常用于找中点、找倒数第k个结点和分割链表。

---

十四、自测清单

完成本章后，应能够不看资料回答：

• 线性表、顺序表和链表分别属于什么概念？

• 为什么顺序表能够随机访问？

• 顺序表第i位插入和删除分别移动多少个元素？

• 为什么链表插入和删除不一定是O(1)？

• 头指针、头结点和首元结点有什么区别？

• 在p后插入s时，为什么必须先执行s->next = p->next？

• 如何删除单链表中p之后的结点？

• 如何在O(1)时间内删除一个非尾结点p？

• 双链表插入一个结点需要维护哪四条指针关系？

• 普通单链表与循环单链表如何判断表尾？

• 只有一个数据结点的循环链表删除后，尾指针应指向哪里？

• 如何用O(n)时间、O(1)额外空间逆置单链表？

• 如何将链表重排为a1、an、a2、an-1……？

• 如何规范说明链表综合算法的时间复杂度和空间复杂度？

能够独立画图并解释以上问题，才算真正掌握线性表。