list 链表

读完能做什么

• 能创建 list，用迭代器从头到尾遍历它，并说出为什么 l[0]、l.begin() + 1 都用不了。
• 能先把游标移动到某个位置，再用 insert、erase 在那个位置插入、删除元素，并说出每一步之后容器里剩哪些元素。
• 能用成员函数 l.sort() 给 list 排序，并解释为什么 std::sort 对 list 不能用。
• 能分清“已知位置的插入删除是 O(1)”和“找到那个位置仍要 O(n)”这两件事。

为什么需要它

vector 的元素挤在一整块连续内存里。在中间插入一个元素，后面的元素都要整体后移一格：

元素一多，这种“整体搬家”就很贵。可有些任务偏偏是“经常在中间插人、删人”：名单里插入一个新同学，或者把已经离开的人从中间删掉。

list 换了一种组织方式：每个元素单独放在一个节点里，节点之间用链接连起来。插入和删除只要改几根链接，不用搬动元素。

它是什么

一句话：list 是双向链表，元素分散在各自的节点里，节点之间靠链接串成一条序列。

直观模型是每个节点装一个元素，并且记住“前一个节点”和“后一个节点”在哪里。下图用箭头表示节点之间的链接：

graph LR
    a["节点 10"] --> b["节点 30"] --> c["节点 40"]
    b --> a
    c --> b

节点与链接。 节点像链表的“车厢”，链接是车厢之间的挂钩。每个节点都记着前后邻居在哪里，所以从任意一个节点出发都能往两个方向走。

迭代器与位置。 list 没有连续下标，位置只能用迭代器表示。迭代器是“指向某个位置的游标”：l.begin() 停在第一个节点上，l.end() 停在最后一个节点后面的位置（尾后位置，那里没有元素）。*it 取出游标当前指向的元素。

双向移动，不能跳格。 list 的迭代器支持 ++it（往后一格）、--it（往前一格），但不支持 it + n、it2 - it1 和 it < it2。原因就是节点不连续：从 10 出发没有“直接跳到第 3 个节点”的办法，只能沿着链接一格一格走。这层区别在容器、迭代器与区间里讲过：vector、deque、string 的迭代器是随机访问迭代器，list、set、map 的迭代器是双向迭代器。

不支持下标。 因为节点不连续，l[0] 这种写法不存在，l.begin() + 1 也编译不过。想知道“第几个元素”，只能从头数着走。

模板尖括号。 list<int> 里的 <int> 表示每个节点里放什么类型的数据，list<string> 就是存字符串的链表。

使用时要 #include <list>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 30, 40};

    cout << "size = " << l.size() << '\n';
    cout << "front = " << l.front() << ", back = " << l.back() << '\n';

    cout << "从头到尾：";
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << ' ';
    }
    cout << '\n';
    return 0;
}

输出：

size = 3
front = 10, back = 40
从头到尾：10 30 40 

逐行看：

• list<int> l = {10, 30, 40}; 创建一条链表，依次接上三个节点。
• l.size() 返回节点个数；l.front()、l.back() 分别读第一个和最后一个节点里的值。
• for (list<int>::iterator it = l.begin(); it != l.end(); ++it) 是遍历 list 的标准写法：从第一个位置出发，每轮 ++it 往后挪一格，走到尾后位置 l.end() 就停。这里写 ++it 而不是 it++，两者结果一样，++it 更常用。
• *it 取出当前节点里的值，所以输出是 10 30 40。

一步步看变化

沿数据 [10, 30, 40] 走三步：把游标移到 30 的位置，在它前面插入 20，再删掉 30。

第 1、2 步：移动到 30，在它前面插入 20

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 30, 40};

    list<int>::iterator it = l.begin();       // 游标先停在 10 上
    ++it;                                     // 后移一格，指向 30
    cout << "游标停在 " << *it << " 上\n";

    l.insert(it, 20);                         // 在 30 之前插入 20

    cout << "插入 20 后：";
    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';
    cout << "游标还停在 " << *it << " 上\n";
    return 0;
}

输出：

游标停在 30 上
插入 20 后：10 20 30 40  size = 4
游标还停在 30 上

insert(it, 20) 的含义是“把 20 插到游标 it 指向的节点之前”。新的 20 节点被接到 10 和 30 之间，原来两个节点之间的链接断掉、换成两根新链接：

插入前：
          it
          ↓
[10] <-> [30] <-> [40]

l.insert(it, 20)   ← 在 it 指向的节点之前接上一个新节点

插入后：
                   it
                   ↓
[10] <-> [20] <-> [30] <-> [40]

注意最后一行的输出：插入之后 it 仍然停在 30 上。list 的插入不搬动任何已有节点，所以指向其他节点的迭代器不会失效——这一点和 vector 不同（vector 中间插入会让后面的位置全部错位，旧迭代器不能再盲用）。

第 3 步：删除 30，并用返回的位置继续

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 30, 40};

    list<int>::iterator it = l.begin();
    ++it;                                     // 指向 30
    l.insert(it, 20);                         // 在 30 之前插入 20，it 仍然指向 30

    cout << "删除前：";
    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';

    it = l.erase(it);                         // 删除 30，返回它后面一个位置

    cout << "删除 30 后：";
    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';
    cout << "erase 返回的位置上是 " << *it << '\n';
    return 0;
}

输出：

删除前：10 20 30 40  size = 4
删除 30 后：10 20 40  size = 3
erase 返回的位置上是 40

erase(it) 删掉 it 指向的那个节点，把它的前后两个节点接起来，并返回被删节点后面一个位置。所以把返回值存回 it（写成 it = l.erase(it);）之后，游标正好落在 40 上，可以接着往下走。被删节点的迭代器会失效，但其他迭代器仍然有效。

逐项扩展核心操作

两端增删：push_front / push_back / pop_front / pop_back

链表的两端也是节点，接上或摘掉一个节点都只改链接，所以四个操作都是 O(1)：

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 30, 40};

    l.push_front(5);
    l.push_back(50);
    cout << "两端加入后：";
    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';

    l.pop_front();
    l.pop_back();
    cout << "两端弹出后：";
    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';
    return 0;
}

输出：

两端加入后：5 10 30 40 50  size = 5
两端弹出后：10 30 40  size = 3

push_front / push_back 在头部 / 尾部加入，pop_front / pop_back 删除头部 / 尾部。pop_* 只负责删除，不返回被删掉的值；想用那个值，先 front() / back() 读出来再删。

用成员 sort() 排序

list 自己带一个排序成员函数，用法是 l.sort()：

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {30, 10, 40, 20};

    cout << "排序前：";
    for (int x : l) cout << x << ' ';
    cout << '\n';

    l.sort();                                 // 成员函数：重接节点，元素本身不搬家

    cout << "l.sort() 后：";
    for (int x : l) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

排序前：30 10 40 20 
l.sort() 后：10 20 30 40 

l.sort() 默认按 < 从小到大排。它和 std::sort 的工作方式不一样：std::sort 靠搬动元素来重排（像数组里那样交换位置），l.sort() 靠重接链接来重排——节点本身一直待在原地，只是挂钩换了个接法。所以它不需要随机访问迭代器，也能用在 list 上。

l.sort() 还是稳定排序：值相等的元素会保持它们原来的相对顺序。稳定排序指“排序前后，相等元素的先后关系不变”，标准规定 list::sort() 满足这一点，而 std::sort() 不保证。例如三条记录 (90,A)、(80,B)、(90,C) 按成绩排序，稳定排序一定得到 (80,B)、(90,A)、(90,C)：两个 90 分的人不会互换。要按多个关键字排序时，这个性质很有用。

为什么 std::sort 不能用在 list 上

std::sort 要求随机访问迭代器：它要在区间里随意跳来跳去、用两个迭代器相减算出元素个数，然后做快速排序式的划分。list 的迭代器只能 ++ / --，两个迭代器还不能相减，所以 std::sort 用不了：

// 错误示例：std::sort 需要随机访问迭代器，list 的迭代器只能一步步走，下面这段不能通过编译
#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {30, 10, 40, 20};

    sort(l.begin(), l.end());   // 编译错误：list 的迭代器不支持相减，sort 无法计算元素个数
    return 0;
}

这段编译不过，报错信息里会直接指出 no match for 'operator-'（list 的迭代器之间没有定义减法）。正确做法就是上一节的 l.sort()。

list 的迭代器还有别的限制，下面这段同样编译不过：

// 错误示例：list 不支持下标和 it + n，下面两行都不能通过编译
#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 30, 40};

    cout << l[0] << '\n';         // list 没有 operator[]，不能按下标取元素
    cout << *(l.begin() + 1) << '\n';   // 双向迭代器不支持 + n
    return 0;
}

所以 list 里想访问“第 3 个元素”，只能 ++it 两次；想找某个值，得从头扫一遍。

删除所有等于某个值的节点：remove

按值删除用成员函数 remove，它会删掉所有值等于给定值的节点：

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 20, 30, 20};

    l.remove(20);                             // 删除所有值为 20 的节点

    cout << "删除 20 后：";
    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';
    return 0;
}

输出：

删除 20 后：10 30  size = 2

remove 收的是值，erase 收的是位置（迭代器），别混。remove 要从头走一遍才能找到所有匹配的节点，是 O(n)。

删除后继续遍历：用 erase 的返回值

“一边遍历一边删除”是链表的常见任务。因为 erase 会返回下一个有效位置，遍历时就不要在 for 里写 ++it，而是把返回值存回游标：

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {1, 2, 3, 4, 5};

    for (list<int>::iterator it = l.begin(); it != l.end(); ) {
        if (*it % 2 == 0) {
            it = l.erase(it);                 // 删掉偶数，erase 返回下一个位置
        } else {
            ++it;
        }
    }

    cout << "删掉所有偶数后：";
    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';
    return 0;
}

输出：

删掉所有偶数后：1 3 5  size = 3

注意 for 的第三段是空的：往不往后走、怎么走，都由循环体自己决定。删掉节点时用 erase 返回的新位置接着走；没删的时候才手动 ++it。

什么时候选它、哪里容易错

不支持下标，也不能跳格。 l[0]、l.begin() + 1、it < it2 全都编译不过。所有定位都要靠 ++it / --it 一格一格走，所以写循环时统一用 it != l.end() 而不是 it < l.end()。

“已知位置快”不等于“找位置快”。 已经拿到指向某个节点的迭代器时，在它前面插入、把它删掉都只改几根链接，是 O(1)；但找到那个位置（比如“值为 20 的节点在哪”）要从头扫，是 O(n)。l.remove(x) 这类按值的操作整体就是 O(n)。

std::sort 用不了，改用成员 sort()。 忘了这一点会直接编译失败。要按自己的规则排序，用 l.sort(cmp)（选读，比较规则见比较规则与函数对象）。

空链表的边界。 front()、back()、pop_front()、pop_back() 都要求容器非空，空链表上调用属于未定义行为，不能靠“它应该会给我 0”来猜。删之前先判 !l.empty()。

复杂度对照：

选读。 每个节点除了元素还要存两根链接，空间开销比 vector 大；节点分散在内存各处，从头到尾走一遍时 CPU 缓存命中率低，所以“同样遍历一遍”，list 通常比 vector 慢。list 的优势在“已知位置频繁插入删除”这类场景，不在于遍历。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

list<int> l = {1, 2, 3};

list<int>::iterator it = l.begin();
++it;                            // 指向 2
l.insert(it, 9);                 // 在 2 之前插入 9

cout << l.front() << ' ' << *it << ' ' << l.size() << '\n';

第 2 题：修改代码

下面这段片段把 [10,20,30,40] 里的 30 删掉。请把它改成删掉 40，让输出变成 10 20 30、size() 变成 3：

list<int> l = {10, 20, 30, 40};

list<int>::iterator it = l.begin();
++it;                            // 指向 20
++it;                            // 指向 30
it = l.erase(it);                // 删掉 30

for (int x : l) cout << x << ' ';
cout << " size = " << l.size() << '\n';

验证条件：先说出改完之后游标要移动几次、erase 返回的位置是什么，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {1, 2, 3};

    list<int>::iterator it = l.begin();
    ++it;                                     // 指向 2
    l.insert(it, 9);                          // 在 2 之前插入 9

    cout << l.front() << ' ' << *it << ' ' << l.size() << '\n';
    return 0;
}

1 2 4

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 20, 30, 40};

    list<int>::iterator it = l.begin();
    ++it;                                     // 指向 20
    ++it;                                     // 指向 30
    ++it;                                     // 指向 40
    it = l.erase(it);                         // 删除 40，返回尾后位置

    for (int x : l) cout << x << ' ';
    cout << " size = " << l.size() << '\n';
    return 0;
}

10 20 30  size = 3

立即练习

这道题只需要数组、循环和本页讲过的 list 操作（insert、erase、迭代器移动）。做完后请说明：为什么这里用 list 比用数组或 vector 更合适？在 list 里“找到第 k 个人”要花多少时间？