第 3.0 章 线性表

List

线性表引入

很多真实场景会直接使用顺序容器或链式结构：

  • Java ArrayList：底层用连续数组保存元素引用，强调随机访问（random access）和缓存局部性（cache locality）
  • 操作系统 / 运行时的空闲链表（free list）：空闲块经常通过链表连接，便于插入和摘除
  • 最近最少使用（Least Recently Used，LRU）缓存：典型实现用散列表 + 双向链表（doubly linked list），同时支持 \(O(1)\) 查找和移动最近访问节点
  • 智能体对话状态：消息、工具调用和观察结果通常按时间顺序保存在序列中，并按序构造下一轮模型输入

这些例子共同指向一个抽象：元素之间只有顺序关系

学习目标

  • 准确定义线性表抽象数据类型
  • 掌握顺序表（sequential list）的访问、查找、插入、删除
  • 掌握单链表（singly linked list）的节点、遍历、插入、删除
  • 理解头结点（header node）、迭代器（iterator）、双向链表、循环链表（circular linked list）
  • 使用链表解决约瑟夫问题（Josephus problem）、多项式相加、倒数第 k 个结点
  • 从时间、空间、局部性和边界条件多维比较顺序表与链表

本章路线图

线性表
List

抽象数据类型与顺序关系
先定义“是什么、能做什么” 顺序表
连续存储 · O(1) 定位 · 搬移代价 单链表
指针连接 · 顺序访问 · 局部改链 链表变体
头结点 · 双向 · 循环 典型问题
约瑟夫问题 · 多项式 · 倒数第 k 个结点 工程选择
时间 · 空间 · 局部性 · 边界条件

线性表抽象

线性表抽象数据类型

顺序表通常具有更好的缓存局部性；链表插入删除的局部操作快，但指针跳转更容易造成缓存未命中。

线性表的数学定义

线性表是一个有限序列：

\[ L=(e_1,e_2,\ldots,e_n) \]

当 \(n=0\) 时，\(L\) 是空表。

当 \(n>0\) 时：

  • \(e_1\) 是第一个元素
  • \(e_n\) 是最后一个元素
  • \(e_i\) 直接前驱（predecessor）是 \(e_{i-1}\)
  • \(e_i\) 直接后继（successor）是 \(e_{i+1}\)

典型实例

线性表 元素 顺序含义
人员名单 人员记录 登记顺序或编号顺序
考试列表 考试 1、考试 2、考试 3 时间顺序
星期 周一、周二、……、周日 周期中的固定顺序
文本行 字符 字符出现顺序

线性表允许相同元素重复出现，因为位置也是信息的一部分。

抽象数据类型的操作集合

操作 含义 常见返回
Create() 创建空表 表对象
IsEmpty() 判断是否为空 boolean
Length() 返回元素个数 int
Find(k) 返回第 k 个元素 元素或失败
Search(x) 查找元素 x 的位置 下标或失败
Delete(k) 删除第 k 个元素 被删元素或失败
Insert(k, x) 在位置 k 处插入 x 成功或失败

顺序表

顺序表：数组表示

顺序表的定位公式

若每个数组槽位占固定宽度 w，并且数组首地址是 base，则第 \(i\) 个物理单元的位置为：

\[ \operatorname{location}(i)=base+i\times w \]

因此，按下标访问是 \(O(1)\)。

查找元素仍然需要逐个比较，顺序查找最坏为 \(O(n)\)。

顺序查找的平均比较次数

在元素等概率出现在任意位置时，成功查找的平均比较次数为：

\[ ACN=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2} \]

找不到元素时，需要比较全部 \(n\) 个元素。

顺序表插入与删除

删除移动次数

删除下标 \(i\) 的元素时，右侧元素需要左移。

若表长为 \(n\)，删除位置等概率，则平均移动次数为：

\[ \frac{(n-1)+(n-2)+\cdots+1+0}{n}=\frac{n-1}{2} \]

删除的时间复杂度是 \(O(n)\)。

插入移动次数

在下标 \(i\) 处插入时，需要从尾部开始右移。

若允许插入到 \(0,1,\ldots,n\) 共 \(n+1\) 个位置，平均移动次数为：

\[ \frac{n+(n-1)+\cdots+1+0}{n+1}=\frac{n}{2} \]

插入的时间复杂度是 \(O(n)\)。

顺序表的优点与限制

维度 结论
按下标访问 \(O(1)\)，非常快
顺序扫描 内存连续，缓存友好
中间插入 需要移动元素，\(O(n)\)
中间删除 需要移动元素，\(O(n)\)
容量变化 静态数组容量固定；动态数组扩容有额外代价

Java 顺序表

static class SequentialList {
    private static final int DEFAULT_CAPACITY = 8;
    private String[] data;
    private int size;

    SequentialList() {
        data = new String[DEFAULT_CAPACITY];
    }

    int size() {
        return size;
    }

    String get(int index) {
        checkElementIndex(index);
        return data[index];
    }

    void insert(int index, String value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index);
        }
        ensureCapacity(size + 1);
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        size++;
    }

    String remove(int index) {
        checkElementIndex(index);
        String removed = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null;
        return removed;
    }

    private void checkElementIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(index);
        }
    }

    private void ensureCapacity(int required) {
        if (required <= data.length) {
            return;
        }
        int newCapacity = Math.max(required, data.length * 2);
        String[] expanded = new String[newCapacity];
        for (int i = 0; i < size; i++) {
            expanded[i] = data[i];
        }
        data = expanded;
    }
}
SequentialList 用连续数组保存元素，逻辑长度由 size 单独维护。
data.length 是物理容量，size 是当前有效前缀长度；未使用槽位不属于顺序表。
构造器创建初始数组；新顺序表的 size=0，因此此时所有槽位都只是备用容量。
size() 直接返回逻辑元素数，不需要扫描数组。
get 验证下标后直接读取 data[index]，所以随机访问是 O(1)。
insert 在需要时扩容，再把后缀整体右移一格并写入新值；中间插入的主要代价是搬移元素，因此是 O(n)。
remove 保存目标值后把右侧元素左移填洞，并清掉旧尾槽；中间删除同样是 O(n)。
checkElementIndex 保证只有 0..size-1 能作为现有元素下标，不能把备用容量当成数据。
ensureCapacity 只在容量不足时申请更大的数组并复制有效前缀；元素顺序和 size 都保持不变。

单链表

单链表节点

单链表的每个节点包含两个部分：

  • data：元素值
  • next：指向下一个节点
static class Node<T> {
    T data;
    Node<T> next;

    Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }
}
Node 把元素与链接字段放在同一个结点中；结点何时接入主结构由后续链接操作决定。
单链节点只保存“元素 + 后继引用”；链表的顺序不靠下标，而是完全编码在 next 关系里。
Node(…) 构造满足该数据结构初始不变量的对象；后续操作都以这个初始状态为前提。
构造时同时确定数据和后继，节点一创建就具备完整局部链接；后续插入只需改少量引用即可接入主链。

单链表的基本图像

最后一个节点的 next 是 null。

单链表插入：结构变化

void insertAfter(Node<T> before, T value) {
    Objects.requireNonNull(before, "before");
    Node<T> node = new Node<>(value, before.next);
    before.next = node;
}
before 是已经定位好的前驱节点，value 是要插入的新元素；因此这里不需要再从表头搜索位置。
插入必须有真实前驱节点；如果 before 为 null，就没有可改写的 next 字段，因此立即拒绝调用。
创建保存 value 的新节点。此时主链还没有改变，新节点只是先在链外准备好。
先让 node.next 保存旧的 before.next；这样下一步改写前驱链接时，后半段链表不会丢失。
让前驱改为指向新节点，局部结构从 before → oldNext 变成 before → node → oldNext。
只新建一个节点并改写常数个引用；在前驱已知的前提下，单链表插入是 O(1)。

单链表删除：结构变化

boolean eraseAfter(Node<T> before) {
    Objects.requireNonNull(before, "before");
    Node<T> victim = before.next;
    if (victim == null) {
        return false;
    }
    before.next = victim.next;
    victim.next = null;
    return true;
}
before 是待删位置的前驱，因此真正的删除目标就是 before.next。
前驱不能为空，因为删除动作最终要改写它的 next；这和“前驱后面没有节点”是两个不同边界。
先把 before.next 保存为 victim；若它不存在，说明前驱已经在链尾，结构保持不变。
让前驱直接指向 victim 的后继，主链于是绕过待删节点；这次绕接才是真正的结构删除。
清空 victim.next，让被移出的节点不再保留对原链后半段的结构引用。
前驱已知时，删除只改写常数个引用，因此结构操作本身是 O(1)。

链表变体

头结点

头结点是不存放有效数据的哨兵（sentinel）节点。

它的作用是统一边界情况：

  • 空表：header.next == null
  • 首元素插入：等价于在 header 后插入
  • 首元素删除：等价于删除 header 后的节点
  • 迭代器起点：zeroth() 可以返回头结点位置

带头结点的链表类骨架

static class SinglyLinkedList<T> {
    protected final Node<T> header = new Node<>(null, null);
    protected int size;

    int size() {
        return size;
    }

    void addFirst(T value) {
        header.next = new Node<>(value, header.next);
        size++;
    }

    List<T> toList() {
        ArrayList<T> result = new ArrayList<>(size);
        for (Node<T> p = header.next; p != null; p = p.next) {
            result.add(p.data);
        }
        return result;
    }
}
SinglyLinkedList 集中保存这一结构的核心状态；类内操作都必须共同维护同一表示不变量。
header 永远存在但不算元素；把“表头前驱”固定下来后，空表与首节点操作都能用同一套链接规则。
size(…) 只报告当前逻辑规模，不应触发结构遍历或修改。
size 只统计真实节点，哨兵不计入；因此长度可以常数时间读取，而不必每次遍历链表。
addFirst(…) 把新数据纳入当前结构；操作结束时必须恢复该结构原有的不变量。
首插把新节点的后继设为旧首节点，再让 header.next 指向它；已知哨兵时只改常数个引用。
toList(…) 按链上顺序复制元素形成结果列表，不改变原链结构。
导出序列必须从 header.next 沿链逐个访问真实节点；链表没有随机下标跳转，因此完整快照天然是 O(n)。

查找

Node<T> find(T value) {
    for (Node<T> p = super.header.next; p != null; p = p.next) {
        if (Objects.equals(p.data, value)) {
            return p;
        }
    }
    return null;
}
find(…) 根据当前结构的不变量定位目标；未命中时返回失败结果而不破坏结构。
查找只能从首个真实节点沿 next 顺序推进；单链表没有可直接跳到第 i 个节点的地址计算。
一旦命中就返回节点本身，调用者可继续基于这个位置改链；无需为了“找到值”再做一次定位。
走到链尾仍未命中才返回 null；最坏情况下每个节点检查一次，时间为 O(n)。

删除指定值

boolean remove(T value) {
    Node<T> before = super.header;
    while (before.next != null && !Objects.equals(before.next.data, value)) {
        before = before.next;
    }
    if (before.next == null) {
        return false;
    }
    Node<T> victim = before.next;
    before.next = victim.next;
    victim.next = null;
    super.size--;
    return true;
}
remove(…) 从当前结构移除一个目标；操作结束时其余元素仍必须满足原来的表示不变量。
before 始终停在“下一节点尚待判断”的前驱位置；这样找到目标时已经同时拿到了删除所需的前驱。
若搜索走到 before.next==null，说明整条链都没有目标；此时结构必须保持不变并返回失败。
命中后只需让前驱绕过 victim、断开旧链接并同步 size；搜索是 O(n)，真正改链是 O(1)。

双向链表与循环链表

相邻节点之间有两条方向相反、彼此平行的结构边：上方 next 向右，下方 prev 向左。变量指针与结构边分开表示。

双向链表插入：结构变化

boolean insertAfter(DoublyNode<T> before, T value) {
    if (before == null || before.owner != this) {
        return false;
    }
    DoublyNode<T> node = new DoublyNode<>(value);
    node.owner = this;
    node.prev = before;
    node.next = before.next;
    before.next.prev = node;
    before.next = node;
    size++;
    return true;
}
before 是插入位置左边的节点，value 是新元素。插入后必须同时恢复 next 和 prev 两个方向的一致性。
只有属于当前链表的真实节点才能作为插入位置；否则改指针可能把两个不同链表错误地接在一起。
先创建新节点，并记录它属于当前链表。此时还没有改原邻居，所以旧连接仍可安全读取。
新节点左邻居就是 before，先建立 node.prev。
再把原右邻居保存到 node.next；现在新节点知道左右邻居，但邻居还没有反过来指向它。
让原右邻居的 prev 改指向新节点。必须在覆盖 before.next 前做，否则原右邻居会丢失。
最后让左邻居的 next 指向新节点；此时两个方向都经过新节点，局部双向不变量恢复。
插入成功后元素数增加 1，并返回 true。已知位置时只修改常数个引用，因此是 O(1)。

双向链表插入：顺序为什么不能反

先读完仍需使用的旧指针，再覆盖邻居的字段；否则旧后继可能丢失，甚至把新节点错误地连回自己形成自环（self-loop）。

双向链表删除

boolean erase(DoublyNode<T> victim) {
    if (victim == null || victim == header || victim.owner != this) {
        return false;
    }
    victim.prev.next = victim.next;
    victim.next.prev = victim.prev;
    victim.prev = null;
    victim.next = null;
    victim.owner = null;
    size--;
    return true;
}
victim 是已经定位好的待删节点。它自己的 prev、next 直接给出两个邻居，所以不需要从表头寻找前驱。
空引用、哨兵 header 或其他链表的节点都不能删除；继续改指针会破坏当前链表的边界或所有权。
victim.prev 直接给出左邻居；这一阶段先确认正向链接将从左邻居跨过 victim。
victim.next 直接给出右邻居；反向链接也必须跨过 victim，否则从右向左仍会走回被删节点。
把左邻居的 next 接到右邻居，正向链已经不再经过 victim。
把右邻居的 prev 接到左邻居；两条方向都完成后，剩余链表重新满足双向一致性。
清空被删节点的 prev、next 和 owner，把它明确标成已经脱离链表的节点。
元素数减 1 并返回成功。两个邻居都能直接取得，所以已知节点时双向链表删除是 O(1)。

单链表与双向链表

已知条件 单链表 双向链表
只知道待删节点 victim 无法从 victim 直接得到前驱，通常需从头查找 victim.prev 立即给出前驱
指针重连 找到前驱后为 \(O(1)\) 已知 victim 时直接为 \(O(1)\)
代价 每个节点只存 next 每个节点额外存 prev，修改时必须维护双向一致性

若采用带表头结点的循环双向链表，首尾删除也能复用同一组重连语句；前提是哨兵节点与两条方向的不变量始终成立。

典型问题

约瑟夫问题

有 \(n\) 个人围成一圈，编号为 \(1,2,\ldots,n\)。给定报数间隔 \(m\)：

  1. 从当前人开始报数：\(1,2,\ldots,m\)；
  2. 报到 \(m\) 的人出列；
  3. 从出列者的下一位重新从 \(1\) 报数；
  4. 重复，直到圈中只剩最后一个人。

算法要回答两个问题：出列顺序是什么？最后幸存者是谁？

为什么用循环链表

约瑟夫问题的关键是三个操作语义：

  • 顺着后继不断报数：到尾部后必须自然回到头部；
  • 删除当前出列者：只需要把前驱连接到后继；
  • 从后继继续：删除后迭代器应直接落到下一位。

循环链表把“最后一个人的后继是第一个人”直接写进结构不变量，因而适合表达这个问题。

循环链表：约瑟夫问题模拟

约瑟夫问题示例：\(n=8, m=3\)

约瑟夫问题算法

static List<Integer> josephus(int n, int m) {
    if (n <= 0 || m <= 0) {
        throw new IllegalArgumentException("n and m must be positive");
    }
    Node<Integer> tail = new Node<>(n, null);
    tail.next = tail;
    for (int value = n - 1; value >= 1; value--) {
        tail.next = new Node<>(value, tail.next);
    }

    Node<Integer> before = tail;
    int remaining = n;
    ArrayList<Integer> order = new ArrayList<>(n);
    while (remaining > 1) {
        int advances = (m - 1) % remaining;
        for (int step = 0; step < advances; step++) {
            before = before.next;
        }
        Node<Integer> victim = before.next;
        order.add(victim.data);
        before.next = victim.next;
        victim.next = null;
        remaining--;
    }
    order.add(before.data);
    return order;
}
josephus(…) 在循环结构中反复计数并删除命中结点，直到只剩最终幸存者。
先排除无效人数和报数间隔；只有规则有定义，后面的环形模拟才有意义。
把 1..n 连成 1→2→…→n→1；报数因此可以一直沿 next 循环前进。
before 定位待删者前驱，remaining 控制终止，order 保存真实出列顺序。
每轮只走 (m-1)%remaining 步；整圈空转被取模消掉，但淘汰位置不变。
沿环推进到淘汰者前一位；于是 before.next 直接给出本轮目标，不再搜索前驱。
先锁定淘汰者并记录编号，再准备把它从环中摘掉；结果顺序因此与真实淘汰顺序一致。
跨过 victim、清理其链接并减少人数；剩余节点仍成环，直到只剩幸存者。
最后把唯一幸存者追加到末尾并返回；order 完整描述淘汰过程和最终结果。

多项式抽象数据类型

多项式可以用数组表示，也可以用链表表示。

数组适合最高次数不大且稠密的多项式：

\[ p(x)=3x^8-5x^3+3x-1 \]

链表适合最高次数很大但非零项很少的多项式：

\[ p(x)=10x^{1000}+5x^{14}+1 \]

多项式链表表示

每个节点保存一个非零项：

static class Term {
    final int coefficient;
    final int exponent;
    Term next;

    Term(int coefficient, int exponent) {
        this.coefficient = coefficient;
        this.exponent = exponent;
    }
}
Term 把多项式的一项系数与指数绑定在一起；链表顺序由指数决定。
每个节点只表示一个非零项：系数给出该项的权重，指数既决定数学次数，也作为链表按降序归并时的排序键；next 只负责串联下一项。
Term(…) 构造满足该数据结构初始不变量的对象；后续操作都以这个初始状态为前提。
构造器只固定这一项的系数和指数；节点位置由之后的 next 链接决定，因此“项内容”和“链表结构”可以分开维护。

多项式相加

多项式相加代码

static Term addPolynomial(Term a, Term b) {
    Term header = new Term(0, -1);
    Term tail = header;
    while (a != null && b != null) {
        if (a.exponent == b.exponent) {
            int sum = a.coefficient + b.coefficient;
            if (sum != 0) {
                tail.next = new Term(sum, a.exponent);
                tail = tail.next;
            }
            a = a.next;
            b = b.next;
        } else if (a.exponent > b.exponent) {
            tail.next = new Term(a.coefficient, a.exponent);
            tail = tail.next;
            a = a.next;
        } else {
            tail.next = new Term(b.coefficient, b.exponent);
            tail = tail.next;
            b = b.next;
        }
    }
    for (Term p = a != null ? a : b; p != null; p = p.next) {
        tail.next = new Term(p.coefficient, p.exponent);
        tail = tail.next;
    }
    return header.next;
}
addPolynomial(…) 按指数合并两个有序项链表；相同指数合并系数，不同指数保持顺序。
哑元（dummy）头结点统一第一次和后续追加；tail 始终指向结果链最后一项，使每次输出都能直接接到尾部。
两条链都未耗尽时按指数归并；指数相同就合并同类项，系数和为 0 则直接省略，并同时推进两条输入链。
若 a 的指数更大，它必然是当前尚未输出项中的最高次项；复制后只推进 a，保持结果指数递减。
若 b 的指数更大则完全对称：先输出 b 当前项，再只推进 b。
主归并结束后只可能剩一条已按指数降序的链；逐项复制即可，无需继续比较，同时 tail 保持 O(1) 追加。
返回 header.next 跳过哑元头结点；若所有同类项都抵消，真实结果头自然就是 null。

多项式相加复杂度

设两个多项式分别有 \(m\) 项和 \(n\) 项。

每一步至少推进 a 或 b 中的一个指针，因此总步数不超过 \(m+n\)。

\[ T(m,n)=O(m+n) \]

最坏情况是两个多项式指数交错，例如：

\[ A=a_5x^5+a_3x^3+a_1x+a_0 \]

\[ B=b_4x^4+b_2x^2+b_0 \]

习题：倒数第 k 个结点

给定一个单链表和正整数 k，要求找到倒数第 k 个结点。例如链表为 10 → 20 → 30 → 40 → 50 → 60，当 k=3 时，答案是 40。

思路：快慢两个指针。让 fast 先走 k 步，再让 fast 和 slow 同时前进。两者始终相差 k 个结点；当 fast 到达表尾时，slow 正好指向倒数第 k 个结点。

倒数第 k 个结点代码

static <T> Optional<Node<T>> kthFromEnd(Node<T> header, int k) {
    if (header == null || k <= 0) {
        return Optional.empty();
    }
    Node<T> lead = header.next;
    for (int i = 0; i < k; i++) {
        if (lead == null) {
            return Optional.empty();
        }
        lead = lead.next;
    }
    Node<T> follow = header.next;
    while (lead != null) {
        lead = lead.next;
        follow = follow.next;
    }
    return Optional.of(follow);
}
kthFromEnd(…) 用两个相距 k 的指针一次扫描定位倒数第 k 个结点。
空表头或非正 k 没有合法答案；通过检查后，才从首个真实节点开始建立双指针间距。
先让 lead 前进 k 步；若途中到达表尾，说明链长不足 k。
之后两指针同步前进，始终保持 k 个节点的间距；lead 到表尾时，follow 正好落在倒数第 k 个节点。
返回已经定位好的节点；前后两次线性扫描都只向前，因此总时间是 O(n)、额外空间是 O(1)。

游标链表（cursor list）

header 和 free 是两个独立入口：前者串起当前逻辑数据，后者串起尚未使用的数组槽位。同一个固定数组因此同时包含“逻辑链成员”和“可复用槽位”两类状态。

游标链表：初始化、分配与释放

观察同一个数组槽位怎样在 free 链与逻辑链之间切换身份：分配时从空闲链摘下，释放时再接回空闲链。

游标链表：分配与释放代码

int allocate() {
    if (freeHead == NULL) {
        throw new NoSuchElementException("cursor space is full");
    }
    int index = freeHead;
    CursorNode node = space[index];
    freeHead = node.next;
    node.next = NULL;
    node.allocated = true;
    return index;
}

void free(int index) {
    if (index < 0 || index >= space.length) {
        throw new IndexOutOfBoundsException(index);
    }
    CursorNode node = space[index];
    if (!node.allocated) {
        throw new IllegalStateException("cursor slot is not allocated");
    }
    node.data = null;
    node.allocated = false;
    node.next = freeHead;
    freeHead = index;
}
allocate(…) 从空闲链取走一个槽位；被分配槽不再属于空闲链，且新的空闲链入口必须保持可达。
空闲链表为空时没有可分配槽位；这个检查保护 freeHead 不会被当成一个不存在的数组下标。
分配只从空闲链表表头摘下一个槽位：推进 freeHead、断开旧空闲链接并标记为已分配，因此整个操作是 O(1)。
free(…) 从当前结构移除一个目标；操作结束时其余元素仍必须满足原来的表示不变量。
释放前先验证数组下标；游标就是“用整数模拟指针”，越界值从一开始就不能代表合法节点。
合法下标还必须处于已分配状态；拒绝重复释放，才能避免同一槽位被两次挂入空闲链表而形成结构错误。
清空数据后把槽位重新压到空闲链表表头；下次 allocate() 可直接复用它，回收同样只修改常数个字段。

问题：几十万考生的高考分数如何排序

假设某省有大量考生，每位考生都有一条 Student 记录；总分范围是 \([0,750]\)，并且最小计分单位是 \(0.5\) 分。

例如某一小段数据是：

600.5, 599.0, 601.0, 600.5, 598.5, 601.5, 599.5, 600.0, 601.0, 599.0, 600.0, 600.5

目标是把所有考生记录按总分从高到低排列。

如果有几十万条记录，直接让所有考生彼此比较有些低效。这里有一个很强的先验条件：

分数的可能取值只有 \(0,0.5,1.0,\ldots,750\)，一共 1501 种。

思路：一个可能分数对应一个桶（bucket）

把分数乘以 2，就可以把所有合法分数映射成整数桶编号：\(2\times score\)。

例如：

  • 598.5 → 桶 1197
  • 600.0 → 桶 1200
  • 600.5 → 桶 1201
  • 601.0 → 桶 1202

因此整个算法只有三步：

  1. 建立 1501 个桶；
  2. 扫描所有考生，把记录放入自己的分数桶；
  3. 从桶 1500 到桶 0 依次取出记录。

此时不需要再对桶内部按分数排序：同一桶中的考生本来就是同分。

为什么这个问题特别适合分桶

设考生人数为 \(n\)，合法分数种类数为 \(S=1501\)。

分桶与收集的成本约为 \(O(n+S)=O(n+1501)\approx O(n)\)。

关键不是“桶排序（bucket sort）永远是线性的”，而是这个问题同时满足：

  • 值域固定且很小：只有 1501 个可能分数；
  • 数据量很大：\(n\) 远大于 1501；
  • 分数天然离散：每 0.5 分正好对应一个桶。

如果只需要“每个分数有多少人”，一个计数数组就足够；如果需要保留完整 Student 记录，每个桶可以保存一个动态序列或链表。

图解：分桶，再按高分到低分收集

桶排序：分桶、扫描与收集

static List<Student> bucketSortByHalfPointScore(List<Student> students) {
    final int maxScore = 1500;
    List<LinkedList<Student>> buckets = new ArrayList<>(maxScore + 1);
    for (int score = 0; score <= maxScore; score++) {
        buckets.add(new LinkedList<>());
    }
    for (Student student : students) {
        if (student.scoreTimesTwo() < 0 || student.scoreTimesTwo() > maxScore) {
            throw new IllegalArgumentException("score out of range");
        }
        buckets.get(student.scoreTimesTwo()).addLast(student);
    }
    ArrayList<Student> result = new ArrayList<>(students.size());
    for (int score = maxScore; score >= 0; score--) {
        result.addAll(buckets.get(score));
    }
    return result;
}
bucketSortByHalfPointScore(…) 按有限分值域分桶计数，再按桶序稳定收集结果。
输入是完整考生记录。分数以 0.5 为最小单位，乘 2 后只有 0..1500 共 1501 个可能值；先按这个固定值域准备桶。
逐个读取考生，并用 scoreTimesTwo() 把成绩精确映射为整数桶编号；先检查 0..1500，防止非法成绩访问不存在的桶。
把考生追加到对应分数链表的尾部。每人只入桶一次；addLast 是 O(1)，并保留同分考生原来的相对顺序。
结果数组按考生人数一次预分配容量，避免收集阶段反复扩容；接下来只按高分到低分接收记录。
从 1500 向 0 扫描各桶，不需要成绩比较就天然得到降序输出；固定扫描 1501 个桶的成本与考生人数无关。
把当前分数桶中的整组同分考生追加到结果。桶内无需再次排序，因为进入同一桶已经证明这些记录分数相同。
返回按总分降序、同分稳定的记录序列。总工作量是每人入桶/出桶一次再扫描 1501 个桶，即 O(n+1501)。

顺序表与链表的多维比较

维度 顺序表 单链表
按下标访问 \(O(1)\) \(O(n)\)
查找某值 \(O(n)\) \(O(n)\)
已知位置后插入 平均移动 \(n/2\) 改两条指针，\(O(1)\)
已知前驱后删除 平均移动 \((n-1)/2\) 改一条指针，\(O(1)\)
空间局部性 好 较差
额外空间 少 每个节点多一个或多个指针
扩容 动态数组可能整体搬迁 单个节点动态分配

选择结构的判断方法

场景 更合适的结构 原因
频繁按下标访问 顺序表 \(O(1)\) 定位
频繁中间插入删除且位置已知 链表 不需要移动大量元素
需要缓存友好扫描 顺序表 连续内存
容量变化剧烈且不需要随机访问 链表 节点按需分配
需要从当前节点访问前驱 双向链表 有 prev 指针
需要循环报数或轮转 循环链表 末尾自然回到开头

本章小结

  • 线性表抽象数据类型描述有限有序序列及其查找、访问、插入、删除等操作语义，不限定存储方式。
  • 顺序表依靠连续数组获得 \(O(1)\) 下标访问和良好的缓存局部性，但中间插入删除必须移动元素。
  • 单链表通过节点和 next 指针组织顺序，遍历、插入和删除的关键是维护当前位置及其前驱。
  • 头结点统一空表和表头操作；迭代器、双向链表、循环链表分别服务遍历、前驱访问和循环处理。
  • 约瑟夫问题、多项式相加、倒数第 \(k\) 个结点都要求把问题状态映射到指针移动和节点重连。
  • 比较顺序表与链表时，不能只看时间复杂度，还要同时检查空间开销、局部性和边界条件。

下载本章完整 Gradle 工程

本章习题

  • 习题 1：顺序表删除移动次数：长度为 \(8\) 的顺序表删除下标 \(2\) 的元素。
  • 习题 2：单链表删除：已知 before 指向待删除节点的前驱，删除 before.next。
  • 习题 3：多项式相加：给定： \(A(x)=2x^{100}+3x^{14}+2x^8+1\) \(B(x)=-2x^{100}+8x^{14}-3x^{10}+10x^6-x\)
  • 习题 4：反转单链表：反转单链表

致谢

谢谢
sqlite@nju.edu.cn
https://slab-nju.cn
石守谦
二维码