第 02 讲

线性表:顺序表与链表

一排有先后顺序的数据,在内存里有两种存法:挨着放进一个数组(顺序表), 或者各放各的、用指针串起来(链表)。这一讲把两种存法讲清楚,并写出能直接拿去做题的代码。

预计 90 分钟 前置:C++ 数组、结构体、指针 关键词:顺序表 · 单链表 · 头结点 · 双向链表 · 循环链表
本章导读
  • 线性表:一排有先后顺序的元素。它有两种存法——顺序表和链表。
  • 一句话对比:顺序表「找得快、改得慢」,链表「改得快、找得慢」。整讲都在解释这句话。
  • 学完要会写:顺序表的插入删除、单链表的插入删除、反转链表,以及做题常用的数组模拟链表。
  • 学习建议:先看动画把每一步看懂,再合上讲义自己把代码敲一遍。配套练习见第 12 讲 12.2。

2.1 线性表:一排有先后的元素

排队的人、歌单里的歌、一行文字里的字,都有一个共同点:元素排成一排,有明确的先后顺序。 这样的一组数据就叫线性表 linear list,记作

L = (a1, a2, …, an)

n 是表长,n = 0 时叫空表。 「一排」的意思是:第一个元素前面没有元素,最后一个元素后面没有元素, 其余每个元素前面恰好一个、后面恰好一个。

线性表的逻辑结构:一条有头有尾、不分叉的「线」 a1 a2 a3 …… a(i-1) a(i) a(i+1) an 唯一直接前驱 a(i-1) 唯一直接后继 a(i+1) 位序 1 位序 2 位序 3 位序 i 位序 n 首元素:无前驱 尾元素:无后继 中间元素:一前一后,各唯一 表长 n 可变:插入使 n 加 1,删除使 n 减 1;n = 0 时称为空表。注意位序从 1 开始计数,而数组下标从 0 开始。
图 2-1 线性表的逻辑结构:首元素唯一无前驱、尾元素唯一无后继,中间元素前驱后继各唯一
先记住一个约定:位序从 1 开始,下标从 0 开始 我们说「第 i 个元素」时,i 从 1 开始数(叫位序);而 C++ 数组的下标从 0 开始。 所以第 i 个元素存在 a[i-1]。本讲后面的越界错误,几乎都来自把这两个数混用。

线性表只规定了「谁在谁前面」,没规定在内存里怎么放。放法有两种,也就是本讲的两大块: 顺序表(2.2 节)和链表(2.3 节起)。

常考 线性表是逻辑结构;顺序表、链表是它的两种存储结构。 「线性表必须存放在连续的内存里」是错的——连续存放只是顺序表的特点。

2.2 顺序表:挨着放在一个数组里

2.2.1 怎么存:一个数组 + 一个表长

最直接的办法:开一个数组,把元素从头开始挨个放进去,再用一个变量 len 记住现在有几个元素。 这就是顺序表 sequential list。

顺序表的内存布局:一段连续地址,元素等距排列 下标 21 32 45 58 66 79 [0] [1] [2] [3] [4] [5] 1000 1004 1008 1012 1016 1020 ← 字节地址 连续的一段内存,相邻元素地址差恒为 L 字节(这里 int 的 L = 4) LOC(a_i) = LOC(a_1) + (i − 1) × L 例:要求位序 4 的元素(下标 3),LOC = 1000 + (4 − 1) × 4 = 1012,一步算出,与表长 n 无关。 若用下标记(从 0 开始):LOC(a[k]) = base + k × L。位序 i 与下标 k 的关系是 k = i − 1,别混用。
图 2-2 顺序表的连续内存布局与地址公式:一次乘加即可定位任意元素,这就是 O(1) 随机存取的来源

因为元素是挨着放的,第 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 的元素:后面的元素整体前移一格 删除前(len = 6): 21 32 45 58 66 79 空 [0] [1] [2] [3] [4] [5] [6] ← 被删元素(由 e 带回) 删除后(len = 5): 21 45 58 66 79 空 空 [0] [1] [2] [3] [4] [5] [6] ← 空位已不属于逻辑表尾 移动次数 = n − i = 6 − 2 = 4;一般式 n − i,平均 (1/n)·Σ(n−i) = (n−1)/2。
图 2-3 顺序表删除:元素自前往后前移,平均移动 (n−1)/2 个元素

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;
}
两个最容易写错的地方
  1. 合法位置不一样:插入时 i 可以是 len + 1(插到最后),删除时 i 最大只能是 len。
  2. 挪动方向相反:插入从后往前挪,删除从前往后挪。写反了就会覆盖掉还没挪的元素。
常考 顺序表按位取值 O(1),按值查找 O(n),插入、删除 O(n)。 在长度为 n 的顺序表里,等概率插入平均移动 n/2 个元素,等概率删除平均移动 (n−1)/2 个元素。

2.3 单链表:用指针串起来

顺序表插入、删除都要挪一大片元素,因为元素必须挨着放。换个思路:元素不挨着放了,各放各的, 每个元素自己记住「下一个在哪」。就像寻宝游戏,每张纸条上写着下一张纸条藏在哪。 这就是链表 linked list。

2.3.1 结点和头结点

链表里的每个元素叫一个结点 node,它装两样东西:数据 data, 和一个指向下一个结点的指针 next。用结构体写就是 struct Node { int data; Node* next; };。 最后一个结点后面没有结点了,它的 next 是 nullptr(空指针)。

我们通常在第一个元素前面再放一个头结点:它不存数据,只是站在最前面。 有了它,「在第 1 个位置插入」「删除第 1 个元素」和别的位置写法完全一样,空表时 head 也不是空指针。 本讲的代码都带头结点。

头指针(变量)≠ 头结点(真实结点)≠ 首元结点(存 a1 的结点) (a) 带头结点的非空链表 head ∅ 12 34 56 NULL 头指针变量 头结点(哑结点) 首元结点 = head->next ← 尾结点的 next 为 NULL (b) 带头结点的空表:head 不为空,但 head->next == NULL head ∅ NULL 这就是空表:没有首元结点,但「表」这个对象依然存在,head 依然有效。 (c) 不带头结点的链表:head 直接指向首元结点 head 12 34 NULL 空表时 head == NULL;在表头插入 / 删除首元结点必须特判, 因为「改 head 本身」与「改 head->next」是两种不同的代码, 所以本章统一采用带头结点的写法。
图 2-4 头指针、头结点、首元结点的区别;以及带头结点 / 不带头结点两种风格下空表的样子

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,然后只改两根指针:

  1. s->next = p->next; 新结点先指向 p 原来的下一个;
  2. p->next = s; p 再指向新结点。

口诀是「先连后断」:新结点先接上后面的链,p 再改过来。这两行不能反过来—— 如果先执行 p->next = s,p 原来的下一个就找不到了,后面整段链表全部丢失。 动画的最后几帧专门演示了写反的后果:

2.3.4 删除:找到前一个,跨过去

删除第 i 个结点,同样先走到它的前一个结点 p,然后:

  1. q = p->next; 用 q 记住要删的结点;
  2. p->next = q->next; 让 p 直接跨过 q;
  3. 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;
}
三个最容易写错的地方
  1. 插入的两行写反:必须先 s->next = p->next,再 p->next = s。
  2. 找错了结点:插入、删除第 i 个,都要先找到第 i−1 个(前一个)结点。
  3. 先 delete 再用:delete q 之后就不能再访问 q->next 了,所以要先改指针、最后再 delete。

2.3.6 练手:反转链表

把 1 → 2 → 3 → 4 → 5 变成 5 → 4 → 3 → 2 → 1。思路是从前往后,把每个结点的 next 掉个头。 用三个指针:pre 是已经反转好的那一段的开头,cur 是当前要处理的结点, nxt 用来先记住 cur 的下一个。每一轮做四件事:

  1. nxt = cur->next; 先记住下一个(不然第 2 步一改就找不到了);
  2. cur->next = pre; 掉头;
  3. pre = cur; pre 往后走一步;
  4. 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;
}
常考 链表不能随机存取,按位查找、按值查找都是 O(n);已知前一个结点时插入、删除是 O(1)。 头结点的作用:让在第 1 个位置插入、删除和其他位置写法统一,空表和非空表的处理也统一。

2.4 做题常用写法:用数组模拟链表

上面的指针写法适合理解原理,做题时却有几个麻烦:new 比较慢,delete 容易忘, 指针出错时程序直接崩溃、很难调试。所以做题时更常用两个数组代替结点: 给每个结点一个编号 k,val[k] 存它的值,nxt[k] 存下一个结点的编号。 这也叫静态链表。

指针写法数组写法
结点的地址 p结点的编号 k
p->dataval[k]
p->nextnxt[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 里存的是下一个结点的编号(0 表示后面没有了) 编号 k val[k] nxt[k] 0 1 2 3 头 21 45 32 1 3 0 2 依次执行三次插入之后: InsertAfter(0, 21) → 领到编号 1 InsertAfter(1, 45) → 领到编号 2 InsertAfter(1, 32) → 领到编号 3 头 21 32 45 0(后面没有了) 结点 0 结点 1 结点 3 结点 2 顺着 nxt 走:0 → 1 → 3 → 2 → 0 停。逻辑顺序是 21 → 32 → 45,和结点编号的大小没有关系。
图 2-5 数组模拟链表:执行上面三次插入之后 val、nxt 两个数组的样子,以及它们表示的链表
做题小技巧 如果题目保证每个元素的值都不相同、而且不大(比如不超过 106),可以直接拿值当编号: nxt[x] 就表示 x 后面是谁,连 val 数组都省了。第 12 讲里的 B3631 单向链表就适合这么写。

2.5 双向链表

单链表有两个常见的变形,各自解决一个问题。

2.5.1 双向链表:还能往回走

单链表只能往后走,想找前一个结点就得从头再来。双向链表给每个结点多加一个指针 prior, 指向前一个结点,这样前后都能走;代价是每个结点多占一个指针的空间。

在 p 后面插入 s,要改四根指针,其中第 ③ 步必须在第 ④ 步前面, 因为 ③ 要用到 p 原来的下一个,④ 一执行它就丢了:

(a) 双向链表结点:prior + data + next 三个域 prior 21 next ← 每个结点 3 个域,比单链表多一个指针(64 位平台上多 8 字节) (b) 在 p(值为 34)之后插入 s(值为 99):四条指针的修改顺序 head 12 34 p 99 s(新结点) 56 next → ← prior 四步(③ 必须在 ④ 之前): ① s->prior = p;     ② s->next = p->next; ③ p->next->prior = s;  ← 用到了「旧的 p->next」,所以不能放在 ④ 后面;p 是尾结点时要判空 ④ p->next = s;     ← 一旦执行,旧的 p->next 就永久丢失 删除 q 只需两条:q->prior->next = q->next; q->next->prior = q->prior; (q 是尾结点时后者要判空)
图 2-6 双向链表的结点结构与插入时的四条指针:先安顿新结点,再改两位邻居,最后断开旧链

做题时同样用数组写: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); 只有题目需要频繁在中间插入、删除时,才换成链表。