返回：0300 数据结构总目录 · 上一章：0302 Chap2 向量 · 下一章：0304 Chap4 栈与队列

1、学习目标

列表是线性结构的链式实现。它牺牲按秩随机访问，换来局部插入、删除时不需要整体搬移元素。复盘时要反复比较：向量适合按秩访问，列表适合频繁插入删除和稳定节点位置。

模块 要掌握的内容
节点 前驱、后继、数据域
哨兵 header、trailer 简化边界
ADT 插入、删除、查找、去重、遍历
无序列表 顺序查找、去重
有序列表 有序查找、唯一化
排序 选择排序、插入排序、归并排序

2、资料范围

PDF 课件 内容
03.List.A.interface_Implementation.pdf 列表接口与实现
03.List.B.Unsorted_list.pdf 无序列表
03.List.C.Sorted_list.pdf 有序列表
03.List.D.Selectionsort.pdf 选择排序
03.List.E.Insertionsort.pdf 插入排序
03.List.F.Mergesort.pdf 归并排序
03.List.X1-X3 游标、Java 序列、Python List

3、节点与列表结构

典型双向链表节点：

1
2
3
4
5
6
7
8
9
10
template <typename T>
struct ListNode {
    T data;
    ListNode<T>* pred;
    ListNode<T>* succ;

    ListNode() = default;
    ListNode(T e, ListNode<T>* p = nullptr, ListNode<T>* s = nullptr)
        : data(e), pred(p), succ(s) {}
};

列表通常使用两个哨兵：

1
header <-> first <-> ... <-> last <-> trailer

哨兵的价值是统一边界情况：

  1. 空表时 header->succ == trailer。
  2. 首元素也有前驱，末元素也有后继。
  3. 插入删除时不用单独判断头尾。

4、插入与删除

在节点 p 前插入：

1
2
3
4
5
6
7
ListNode<T>* insertBefore(ListNode<T>* p, const T& e) {
    auto* x = new ListNode<T>(e, p->pred, p);
    p->pred->succ = x;
    p->pred = x;
    ++_size;
    return x;
}

删除节点：

1
2
3
4
5
6
7
8
T remove(ListNode<T>* p) {
    T e = p->data;
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    --_size;
    return e;
}

如果已经定位到节点，插入和删除都是 O(1)。但“定位”通常需要从头或尾扫描，所以整体操作不一定是常数时间。

5、无序列表

无序列表查找只能线性扫描：

1
2
3
4
5
6
ListNode<T>* find(const T& e, int n, ListNode<T>* p) const {
    while (0 < n--) {
        if (e == (p = p->pred)->data) return p;
    }
    return nullptr;
}

去重思路：

1
2
3
4
5
6
7
8
9
10
11
12
int deduplicate() {
    int oldSize = _size;
    auto* p = first();
    int r = 0;
    while (p != trailer) {
        auto* q = find(p->data, r, p);
        if (q) remove(q);
        else ++r;
        p = p->succ;
    }
    return oldSize - _size;
}

复杂度 O(n^2)。

6、有序列表

有序列表中相同元素相邻，可以线性唯一化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int uniquify() {
    if (_size < 2) return 0;
    int oldSize = _size;
    auto* p = first();
    auto* q = p->succ;
    while (q != trailer) {
        if (p->data != q->data) {
            p = q;
            q = q->succ;
        } else {
            q = q->succ;
            remove(q->pred);
        }
    }
    return oldSize - _size;
}

复杂度 O(n)。

7、列表排序

7.1 选择排序

选择排序适合列表的原因：找到最大元素后，把它移动到有序区前端，只改指针或节点数据即可。

过程：

1
在未排序区间中找最大节点，将其放到后端有序区间前面。

复杂度 O(n^2)，不稳定。

7.2 插入排序

插入排序适合接近有序的数据：

1
从前往后扫描，将当前元素插入到前面已排序区间的合适位置。

复杂度：

情况 复杂度
最好 O(n)
最坏 O(n^2)
稳定性 稳定

7.3 归并排序

链表归并排序不需要像向量那样大量移动元素，合并时可以通过改指针连接节点。

1
拆成两半 -> 分别排序 -> 合并两个有序链表

复杂度 O(n log n)，稳定。

8、向量与列表对比

操作 向量 列表
按秩访问 O(1) O(n)
已定位插入 O(n) O(1)
已定位删除 O(n) O(1)
查找 O(n) O(n)
缓存友好 好 较差
空间额外开销 容量冗余 前驱/后继指针

不要简单说“链表插入删除更快”。准确说法是：如果已经拿到节点位置，列表插入删除是常数时间；如果还要查找位置，仍然可能是线性时间。

9、易错点

易错点 修正
删除节点后继续访问它 删除前先保存后继
忘记维护双向指针 前驱的后继、后继的前驱都要改
不用哨兵导致边界代码复杂 用 header/trailer 统一空表、头尾插入删除
把列表当数组用 列表不适合频繁按秩随机访问

10、复盘清单

检查项 状态
能画出带哨兵的双向链表 待复盘
能写出 insertBefore/remove 指针修改顺序 待复盘
能解释列表插入删除的真实复杂度 待复盘
能比较无序去重和有序唯一化 待复盘
能说明选择排序、插入排序、归并排序在列表上的特点 待复盘