线性表:顺序表与链表
一排有先后顺序的数据,在内存里有两种存法:挨着放进一个数组(顺序表), 或者各放各的、用指针串起来(链表)。这一讲把两种存法讲清楚,并写出能直接拿去做题的代码。
- 线性表:一排有先后顺序的元素。它有两种存法——顺序表和链表。
- 一句话对比:顺序表「找得快、改得慢」,链表「改得快、找得慢」。整讲都在解释这句话。
- 学完要会写:顺序表的插入删除、单链表的插入删除、反转链表,以及做题常用的数组模拟链表。
- 学习建议:先看动画把每一步看懂,再合上讲义自己把代码敲一遍。配套练习见第 12 讲 12.2。
2.1 线性表:一排有先后的元素
排队的人、歌单里的歌、一行文字里的字,都有一个共同点:元素排成一排,有明确的先后顺序。 这样的一组数据就叫线性表 linear list,记作
n 是表长,n = 0 时叫空表。
「一排」的意思是:第一个元素前面没有元素,最后一个元素后面没有元素,
其余每个元素前面恰好一个、后面恰好一个。
a[i-1]。本讲后面的越界错误,几乎都来自把这两个数混用。
线性表只规定了「谁在谁前面」,没规定在内存里怎么放。放法有两种,也就是本讲的两大块: 顺序表(2.2 节)和链表(2.3 节起)。
2.2 顺序表:挨着放在一个数组里
2.2.1 怎么存:一个数组 + 一个表长
最直接的办法:开一个数组,把元素从头开始挨个放进去,再用一个变量 len 记住现在有几个元素。
这就是顺序表 sequential list。
因为元素是挨着放的,第 i 个元素的地址可以直接算出来,取它只要一步:a[i-1]。
不管表有多长,取第 i 个元素都是 O(1),这叫随机存取。这是顺序表最大的优点。
2.2.2 插入:后面的元素往后挪
要在第 i 个位置插入一个新元素,得先把第 i 个位置空出来:
从第 i 个元素到最后一个元素,全部往后挪一格,再把新元素放进空位,最后 len 加一。
挪的时候必须从最后一个开始往前挪。如果从前往后挪,前一个元素会把后一个元素直接覆盖掉。 下面的动画在第 4 个位置插入 50,可以单步看每一次挪动:
挪动次数取决于插在哪:插到表尾一次都不用挪,插到表头要把 n 个元素全挪一遍。 平均下来要挪大约一半,所以插入是 O(n)。
2.2.3 删除:后面的元素往前挪
删除第 i 个元素正好反过来:把它后面的元素依次往前挪一格,把它覆盖掉,再让 len 减一。
这回要从前往后挪。删除同样是 O(n)。
2.2.4 完整代码
按第 01 讲 1.5.2 那张操作表,把顺序表的全部基本操作写成一个完整程序(函数名和表里一一对应):
#include <bits/stdc++.h>
using namespace std;
/* 顺序表 = 一个数组 + 一个表长
约定:位序从 1 开始,第 i 个元素存在 a[i-1] */
const int MAXN = 100; // 数组最多能装多少个元素
int a[MAXN]; // 元素依次放在 a[0], a[1], ..., a[len-1]
int len = 0; // 表长:现在有几个元素
// 初始化:空表
void InitList() {
len = 0;
}
// 求表长,O(1)
int ListLength() {
return len;
}
// 取第 i 个元素:直接算出下标,O(1)(调用前保证 1 <= i <= len)
int GetElem(int i) {
return a[i - 1];
}
// 找第一个值等于 x 的元素,返回它的位序;找不到返回 0。O(n)
int LocateElem(int x) {
for (int k = 0; k < len; k++)
if (a[k] == x) return k + 1;
return 0;
}
// 在第 i 个位置插入 x,合法范围 1 <= i <= len+1。O(n)
bool ListInsert(int i, int x) {
if (i < 1 || i > len + 1) return false; // 位置不合法
if (len == MAXN) return false; // 数组已经装满
for (int k = len - 1; k >= i - 1; k--) // 从最后一个开始,逐个往后挪一格
a[k + 1] = a[k];
a[i - 1] = x; // 空出来的位置放 x
len++;
return true;
}
// 删除第 i 个元素,合法范围 1 <= i <= len。O(n)
bool ListDelete(int i) {
if (i < 1 || i > len) return false;
for (int k = i; k < len; k++) // 后面的元素从前往后,逐个往前挪一格
a[k - 1] = a[k];
len--;
return true;
}
void PrintList() {
for (int k = 0; k < len; k++) cout << a[k] << ' ';
cout << '\n';
}
int main() {
InitList();
int v[] = {21, 32, 45, 58, 66, 79};
for (int k = 0; k < 6; k++) ListInsert(len + 1, v[k]); // 依次插到表尾
PrintList(); // 21 32 45 58 66 79
ListInsert(4, 50); // 在第 4 个位置插入 50
PrintList(); // 21 32 45 50 58 66 79
ListDelete(2); // 删除第 2 个元素(32)
PrintList(); // 21 45 50 58 66 79
cout << GetElem(3) << ' ' << LocateElem(58) << ' ' << ListLength() << '\n'; // 50 4 6
return 0;
}
- 合法位置不一样:插入时 i 可以是
len + 1(插到最后),删除时 i 最大只能是len。 - 挪动方向相反:插入从后往前挪,删除从前往后挪。写反了就会覆盖掉还没挪的元素。
2.3 单链表:用指针串起来
顺序表插入、删除都要挪一大片元素,因为元素必须挨着放。换个思路:元素不挨着放了,各放各的, 每个元素自己记住「下一个在哪」。就像寻宝游戏,每张纸条上写着下一张纸条藏在哪。 这就是链表 linked list。
2.3.1 结点和头结点
链表里的每个元素叫一个结点 node,它装两样东西:数据 data,
和一个指向下一个结点的指针 next。用结构体写就是
struct Node { int data; Node* next; };。
最后一个结点后面没有结点了,它的 next 是 nullptr(空指针)。
我们通常在第一个元素前面再放一个头结点:它不存数据,只是站在最前面。
有了它,「在第 1 个位置插入」「删除第 1 个元素」和别的位置写法完全一样,空表时 head 也不是空指针。
本讲的代码都带头结点。
2.3.2 遍历:顺着 next 一个个走
链表只能从头结点出发,顺着 next 一个一个往后走:
for (Node* p = head->next; p != nullptr; p = p->next) { … }要找第 i 个结点,就得从头走 i 步——链表没有随机存取,按位查找、按值查找都是 O(n)。 这是链表最大的缺点。
2.3.3 插入:先连后断
要在第 i 个位置插入新结点 s,先从头走到第 i−1 个结点 p,然后只改两根指针:
s->next = p->next;新结点先指向 p 原来的下一个;p->next = s;p 再指向新结点。
口诀是「先连后断」:新结点先接上后面的链,p 再改过来。这两行不能反过来——
如果先执行 p->next = s,p 原来的下一个就找不到了,后面整段链表全部丢失。
动画的最后几帧专门演示了写反的后果:
2.3.4 删除:找到前一个,跨过去
删除第 i 个结点,同样先走到它的前一个结点 p,然后:
q = p->next;用 q 记住要删的结点;p->next = q->next;让 p 直接跨过 q;delete q;把 q 占的内存还回去。
可以看到,插入和删除本身只改一两根指针,不用挪任何元素,这是链表比顺序表强的地方; 但前面「走到第 i−1 个结点」这一步要 O(n),所以按位置插入、删除整体还是 O(n)。 如果手里已经有了前一个结点,插入、删除就是 O(1)。
2.3.5 完整代码
单链表也按 1.5.2 的同一张操作表实现,函数名、参数都和顺序表一样,调用方换用哪一种都不用改代码。
多出来的 GetNode 只是内部用来「从头走到第 i 个结点」的辅助函数。
#include <bits/stdc++.h>
using namespace std;
/* 单链表(带头结点)
每个结点 = 数据 data + 指向下一个结点的指针 next */
struct Node {
int data;
Node* next;
};
Node* head; // 头指针:指向头结点。头结点不存数据,只是让插入、删除的代码不用分情况
void InitList() {
head = new Node; // 造一个头结点
head->next = nullptr; // 空表:头结点后面什么都没有
}
// 从头结点出发走 i 步,得到第 i 个结点(i = 0 就是头结点);走到头了返回 nullptr。O(n)
Node* GetNode(int i) {
Node* p = head;
for (int k = 0; k < i && p != nullptr; k++) p = p->next;
return p;
}
// 求表长:从头数到尾,O(n)
int ListLength() {
int n = 0;
for (Node* p = head->next; p != nullptr; p = p->next) n++;
return n;
}
// 取第 i 个元素:走 i 步,O(n)(调用前保证 1 <= i <= 表长)
int GetElem(int i) {
return GetNode(i)->data;
}
// 找第一个值等于 x 的结点,返回它的位序;找不到返回 0。O(n)
int LocateElem(int x) {
int k = 1;
for (Node* p = head->next; p != nullptr; p = p->next, k++)
if (p->data == x) return k;
return 0;
}
// 在第 i 个位置插入 x:先找到第 i-1 个结点 p,再把新结点接在 p 后面
bool ListInsert(int i, int x) {
if (i < 1) return false;
Node* p = GetNode(i - 1);
if (p == nullptr) return false; // 位置超过了表尾
Node* s = new Node;
s->data = x;
s->next = p->next; // ① 新结点先指向 p 原来的后继
p->next = s; // ② p 再指向新结点(这两行不能反过来)
return true;
}
// 删除第 i 个结点:先找到它的前一个结点 p,让 p 跨过它
bool ListDelete(int i) {
if (i < 1) return false;
Node* p = GetNode(i - 1);
if (p == nullptr || p->next == nullptr) return false; // 第 i 个结点不存在
Node* q = p->next; // q 是要删的结点
p->next = q->next; // p 跨过 q
delete q; // 把 q 占的内存还回去
return true;
}
void PrintList() {
for (Node* p = head->next; p != nullptr; p = p->next) cout << p->data << ' ';
cout << '\n';
}
int main() {
InitList();
int v[] = {12, 34, 56, 78};
for (int k = 0; k < 4; k++) ListInsert(k + 1, v[k]); // 依次接到末尾
PrintList(); // 12 34 56 78
ListInsert(3, 99); // 在第 3 个位置插入 99
PrintList(); // 12 34 99 56 78
ListDelete(4); // 删除第 4 个结点(56)
PrintList(); // 12 34 99 78
cout << GetElem(2) << ' ' << LocateElem(99) << ' ' << ListLength() << '\n'; // 34 3 4
return 0;
}
- 插入的两行写反:必须先
s->next = p->next,再p->next = s。 - 找错了结点:插入、删除第 i 个,都要先找到第 i−1 个(前一个)结点。
- 先 delete 再用:
delete q之后就不能再访问q->next了,所以要先改指针、最后再 delete。
2.3.6 练手:反转链表
把 1 → 2 → 3 → 4 → 5 变成 5 → 4 → 3 → 2 → 1。思路是从前往后,把每个结点的 next 掉个头。
用三个指针:pre 是已经反转好的那一段的开头,cur 是当前要处理的结点,
nxt 用来先记住 cur 的下一个。每一轮做四件事:
nxt = cur->next;先记住下一个(不然第 2 步一改就找不到了);cur->next = pre;掉头;pre = cur;pre 往后走一步;cur = nxt;cur 往后走一步。
动画里为了看得清楚没有画头结点。代码里有头结点,最后要让 head->next 指向新的第一个结点。
代码里还顺便用了尾插法建表:用 tail 记住最后一个结点,新结点总是接在它后面。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head; // 头结点
// 反转链表:把每个结点的 next 掉个头
void Reverse() {
Node* pre = nullptr; // 已经反转好的那一段的第一个结点
Node* cur = head->next; // 还没反转的那一段的第一个结点
while (cur != nullptr) {
Node* nxt = cur->next; // ① 先记住下一个,不然改完 cur->next 就找不到它了
cur->next = pre; // ② 掉头:指向前一个
pre = cur; // ③ pre 往前走一步
cur = nxt; // ④ cur 往前走一步
}
head->next = pre; // 头结点指向新的第一个结点(原来的最后一个)
}
void PrintList() {
for (Node* p = head->next; p != nullptr; p = p->next) cout << p->data << ' ';
cout << '\n';
}
int main() {
head = new Node{0, nullptr};
Node* tail = head; // tail 始终指向最后一个结点
for (int x = 1; x <= 5; x++) { // 尾插法:新结点总是接在 tail 后面
tail->next = new Node{x, nullptr};
tail = tail->next;
}
PrintList(); // 1 2 3 4 5
Reverse();
PrintList(); // 5 4 3 2 1
return 0;
}
2.4 做题常用写法:用数组模拟链表
上面的指针写法适合理解原理,做题时却有几个麻烦:new 比较慢,delete 容易忘,
指针出错时程序直接崩溃、很难调试。所以做题时更常用两个数组代替结点:
给每个结点一个编号 k,val[k] 存它的值,nxt[k] 存下一个结点的编号。
这也叫静态链表。
| 指针写法 | 数组写法 |
|---|---|
结点的地址 p | 结点的编号 k |
p->data | val[k] |
p->next | nxt[k] |
nullptr(后面没有了) | 0(0 号留给头结点,不会是真正的元素) |
new Node | ++idx,领一个新编号 |
插入、删除的写法和指针版一模一样,只是把 p->next 换成了 nxt[k]:
#include <bits/stdc++.h>
using namespace std;
/* 用数组模拟单链表(做题时最常用的写法)
结点不再 new 出来,而是数组里的一个「编号」:
val[k] = 结点 k 存的值
nxt[k] = 结点 k 的下一个结点的编号
约定:0 号结点当头结点;nxt[k] == 0 表示 k 后面没有结点了 */
const int N = 100005;
int val[N], nxt[N];
int idx = 0; // 已经用掉了几个编号;新结点的编号是 ++idx
// 在结点 k 后面插入一个值为 x 的新结点(k = 0 就是插到最前面)
void InsertAfter(int k, int x) {
idx++; // 领一个新编号
val[idx] = x;
nxt[idx] = nxt[k]; // ① 新结点先指向 k 原来的后继
nxt[k] = idx; // ② k 再指向新结点 —— 和指针版的两行一模一样
}
// 删除结点 k 后面的那个结点
void DeleteAfter(int k) {
nxt[k] = nxt[nxt[k]]; // k 直接跨过它(数组版不用 delete)
}
void PrintList() {
for (int p = nxt[0]; p != 0; p = nxt[p]) cout << val[p] << ' ';
cout << '\n';
}
int main() {
InsertAfter(0, 21); // 结点 1 存 21,链表:21
InsertAfter(1, 45); // 结点 2 存 45,链表:21 45
InsertAfter(1, 32); // 结点 3 存 32,插在结点 1 后面,链表:21 32 45
PrintList(); // 21 32 45
DeleteAfter(1); // 删掉结点 1(21)后面的那个结点
PrintList(); // 21 45
return 0;
}
nxt[x] 就表示 x 后面是谁,连 val 数组都省了。第 12 讲里的 B3631 单向链表就适合这么写。
2.5 双向链表
单链表有两个常见的变形,各自解决一个问题。
2.5.1 双向链表:还能往回走
单链表只能往后走,想找前一个结点就得从头再来。双向链表给每个结点多加一个指针 prior,
指向前一个结点,这样前后都能走;代价是每个结点多占一个指针的空间。
在 p 后面插入 s,要改四根指针,其中第 ③ 步必须在第 ④ 步前面, 因为 ③ 要用到 p 原来的下一个,④ 一执行它就丢了:
做题时同样用数组写:l[k] 是 k 左边的结点,r[k] 是 k 右边的结点。
把 0 号当成哨兵,同时充当表头和表尾,这样插在最左边、最右边都不用特殊处理:
#include <bits/stdc++.h>
using namespace std;
/* 用数组模拟双向链表:l[k] 是结点 k 左边的结点,r[k] 是右边的结点
约定:0 号结点是「哨兵」,同时当表头和表尾用 ——
r[0] 是最左边的结点,l[0] 是最右边的结点;空表时 l[0] = r[0] = 0 */
const int N = 100005;
int l[N], r[N];
// 把结点 x 插到结点 k 的右边(四步,和图 2-6 的指针版一一对应)
void InsertRight(int k, int x) {
l[x] = k; // ① x 的左边是 k
r[x] = r[k]; // ② x 的右边是 k 原来的右边
l[r[k]] = x; // ③ k 原来的右边,把它的左边改成 x
r[k] = x; // ④ 最后才改 k 的右边(③ 要用到旧的 r[k],所以必须在 ④ 前面)
}
// 把结点 x 插到结点 k 的左边:等于插到「k 左边那个结点」的右边
void InsertLeft(int k, int x) {
InsertRight(l[k], x);
}
// 删除结点 x:让它左右两边的结点直接互相指
void RemoveNode(int x) {
r[l[x]] = r[x];
l[r[x]] = l[x];
}
int main() {
l[0] = r[0] = 0; // 空表
InsertRight(0, 1); // 1
InsertRight(1, 2); // 1 2
InsertLeft(1, 3); // 3 1 2
InsertRight(3, 4); // 3 4 1 2
RemoveNode(1); // 3 4 2
for (int p = r[0]; p != 0; p = r[p]) cout << p << ' '; // 从左往右:3 4 2
cout << '\n';
for (int p = l[0]; p != 0; p = l[p]) cout << p << ' '; // 从右往左:2 4 3
cout << '\n';
return 0;
}
第 12 讲里的 P1160 队列安排,就是「在某人左边或右边插入、删除某人」,正好用这套写法。
2.6 顺序表和链表怎么选
| 顺序表 | 链表 | |
|---|---|---|
| 怎么存 | 挨着放在一个数组里 | 各放各的,用指针(或编号)串起来 |
| 取第 i 个 | O(1),直接算下标 | O(n),要从头走 |
| 插入、删除 | O(n),要挪元素 | 找到位置后 O(1),只改指针 |
| 额外空间 | 没有 | 每个结点多一个指针 |
| 适合 | 经常按位置取、很少在中间插删 | 经常在中间插删、很少按位置取 |
平时写程序,拿不准就先用顺序表(C++ 里的 vector);
只有题目需要频繁在中间插入、删除时,才换成链表。