list链表容器 - CSP-J | C++ & Algorithm 编程研习社

轻松学会C++ list链表：像玩火车玩具一样操作数据

你有没有玩过火车玩具？火车由很多节车厢连在一起，你可以把新车厢挂在前面或后面，也可以从中间拆掉一节车厢，还能在两节车厢之间加挂新的一节。C++里的list容器就像这样一列火车，每个元素就是一节车厢，它能随意在任意位置插入或删除元素，而且不需要移动其他车厢——就像火车挂车厢时，其他车厢不用动位置，只要改变连接点就行。

要使用list，需要先包含头文件 #include <list>。

1. 什么是list？—— 双向链表的“火车”

list 实际上是一个双向链表。链条上的每个元素（车厢）都保存着两个“地址”：一个指向它前面的元素，一个指向它后面的元素。所以：

你可以从最前面或最后面快速添加/删除元素（因为直接知道两端的地址）。
你也能从中间任意位置插入或删除元素，只要改变前后元素的“连接”关系，不需要像数组那样搬动一大片元素。

对比一下你熟悉的vector（数组）：

vector 就像一列固定座位的动车，座位编号0、1、2……你想在2号座位和3号座位之间加一个座位？不行，你得把3号及以后所有乘客往后挪一个位置，很麻烦。
list 则像积木火车，随时可以在任意两节车厢之间插一节新的，或者抽走一节，其他车厢原地不动。

所以，如果你需要频繁地在序列中间插入或删除元素，list 非常合适；但如果只是总是在末尾添加或删除，vector 更快更省空间。

2. 基本操作：像玩火车一样增减车厢

list 提供了丰富的头尾操作和中间操作，我们用一个“宠物列表”的例子来学习。

2.1 头尾操作：加车厢、卸车厢

操作	作用	代码示例
`push_front(x)`	在链表头部（最前面）插入元素x	`pets.push_front("小猫");`
`push_back(x)`	在链表尾部（最后面）插入元素x	`pets.push_back("小狗");`
`pop_front()`	删除链表头部元素	`pets.pop_front();`
`pop_back()`	删除链表尾部元素	`pets.pop_back();`
`front()`	获取头部元素（不删除）	`string first = pets.front();`
`back()`	获取尾部元素（不删除）	`string last = pets.back();`

举例：管理你的宠物列表

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<string> pets; // 创建一个空的宠物名字链表

    // 先给末尾加两只宠物
    pets.push_back("兔子"); // 末尾加兔子
    pets.push_back("金鱼"); // 末尾加金鱼

    // 在开头加一只小猫
    pets.push_front("小猫"); // 现在顺序：小猫 兔子 金鱼

    // 删除第一只（小猫）——小猫被领走了
    pets.pop_front(); // 现在顺序：兔子 金鱼

    // 再在末尾加一条小狗
    pets.push_back("小狗"); // 现在顺序：兔子 金鱼 小狗

    cout << "现在宠物列表有 " << pets.size() << " 种：" << endl;
    // 输出：现在宠物列表有 3 种：

    // 用迭代器遍历所有元素
    for (list<string>::iterator it = pets.begin(); it != pets.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    // 输出：兔子 金鱼 小狗

    return 0;
}

2.2 中间操作：在任意位置插入或删除

除了头尾，list 还可以在中间“加车厢”或“拆车厢”。这需要用到一个叫做迭代器的小工具，它就像一把指向车厢位置的“指针”。

插入操作：insert(迭代器位置, 元素) —— 在指定位置的前面插入一个元素。
删除操作：erase(迭代器位置) —— 删除指定位置的元素。

注意：迭代器可以通过 find 查找元素得到，也可以手动遍历得到。

生活例子：你有一个排队的小组名单，小明、小红、小刚、小丽。你想在小红后面插入小明，然后删除小刚。

#include <iostream>
#include <list>
#include <algorithm> // 为了使用find
using namespace std;

int main() {
    list<string> team = {"小明", "小红", "小刚", "小丽"}; // 初始化列表

    // 1. 找到“小红”的位置
    list<string>::iterator it = team.begin();
    while (it != team.end() && *it != "小红") {
        ++it; // 继续向后走
    }
    // 如果找到了，it就指向小红。没找到则it==team.end()

    // 2. 在“小红”后面插入“小明”（注意insert是在位置之前插入）
    // 我们希望插在小红后面，所以要在小红的下一个位置前插入。
    // 先让it指向小红后面的位置：使用next(it)
    if (it != team.end()) {
        team.insert(next(it), "小明"); // 在小红后面加小明
    }

    // 3. 删除“小刚”：找到小刚并erase
    list<string>::iterator it2 = team.begin();
    while (it2 != team.end() && *it2 != "小刚") {
        ++it2;
    }
    if (it2 != team.end()) {
        team.erase(it2); // 删掉小刚
    }

    // 输出最终名单
    cout << "最终排队顺序：";
    for (auto& name : team) { // 使用C++11范围for，更简洁
        cout << name << " ";
    }
    cout << endl;
    // 输出：最终排队顺序：小明 小红 小明 小丽  （小刚被删，小红后面插入了小明）

    return 0;
}

更快捷的方法：C++11以后，你还可以用 remove 直接删除所有等于某个值的元素（但不删除元素本身，只是把目标值移到后面，然后需要配合 erase）。不过初学时建议先用查找+erase。

3. 如何遍历list？

因为list不是数组，不支持像 pets[0] 这样按位置随机访问。你只能用迭代器（iterator）一个接一个地访问。

begin() 返回指向第一个元素的迭代器。
end() 返回指向最后一个元素后面的位置（这个位置没有元素，不能取值）。
用 *it 取出当前迭代器指向的元素的值。
用 ++it 让迭代器移向下一个元素。

两种常见写法：

写法一：传统迭代器循环

for (list<string>::iterator it = pets.begin(); it != pets.end(); ++it) {
    cout << *it << " ";
}

写法二：C++11 范围for循环（推荐，更简洁）

for (string pet : pets) {
    cout << pet << " ";
}

范围for循环本质上也用了迭代器，但语法更简单。C++11以上编译器都支持。

4. 常见错误（新手最容易踩的坑）

错误1：忘记包含头文件
只写了 #include <iostream>，没写 #include <list>，编译报错。
解决：检查文件开头是否包含 <list>。

错误2：用下标访问
比如想取第2个元素，写成 pets[1] —— 编译报错。list没有下标运算符。
解决：只能用迭代器或范围for遍历。

错误3：在遍历list时直接删除当前元素（迭代器失效）
例如：

for (auto it = pets.begin(); it != pets.end(); ++it) {
    if (*it == "金鱼") {
        pets.erase(it); // 错误！删除后it失效，++it会导致未定义行为
    }
}

正确做法：使用 erase 的返回值，它会返回被删除元素的下一个元素的迭代器：

it = pets.erase(it); // 删除it指向的元素，it自动变成下一个

但注意，erase后原来的it就失效了，必须用返回的新迭代器。

错误4：混淆 push_front 和 push_back
想往末尾加元素却用了 push_front，结果顺序反了。
解决：操作前想清楚是在头部还是尾部。

错误5：混淆 pop_front 和 pop_back
同上，删除前确认方向。

错误6：忘记检查空容器
对一个空list调用 front() 或 pop_front()，会导致程序崩溃。
解决：用 empty() 先判断是否为空。

5. 完整可运行示例：一个“任务待办”管理器

我们模拟一个简单的任务清单，支持添加任务到末尾、在某个任务后插入新任务、删除指定任务。

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> tasks; // 待办任务链表

    // 添加几个初始任务
    tasks.push_back("写数学作业");  // 末尾添加
    tasks.push_back("背英语单词");
    tasks.push_front("起床");       // 在开头添加（其实应该是第一个任务）
    // 现在顺序：起床 -> 写数学作业 -> 背英语单词

    // 在“写数学作业”后插入“吃早饭”
    list<string>::iterator it = tasks.begin();
    while (it != tasks.end() && *it != "写数学作业") {
        ++it;
    }
    if (it != tasks.end()) {
        tasks.insert(next(it), "吃早饭"); // 在写数学作业后面插入
    }

    // 删除“背英语单词”
    list<string>::iterator it2 = tasks.begin();
    while (it2 != tasks.end() && *it2 != "背英语单词") {
        ++it2;
    }
    if (it2 != tasks.end()) {
        it2 = tasks.erase(it2); // 删除并更新迭代器
    }

    // 输出所有任务
    cout << "我的任务清单（顺序：从早到晚）" << endl;
    int index = 1;
    for (string task : tasks) {
        cout << index << ". " << task << endl;
        ++index;
    }
    // 输出：
    // 我的任务清单（顺序：从早到晚）
    // 1. 起床
    // 2. 写数学作业
    // 3. 吃早饭
    // （背英语单词被删除了）

    // 查看第一个和最后一个任务
    cout << "第一个任务是：" << tasks.front() << endl; // 起床
    cout << "最后一个任务是：" << tasks.back() << endl; // 吃早饭

    return 0;
}

6. 什么时候用list？什么时候用vector或deque？

list：需要在序列中间频繁插入或删除（比如任务管理器、学生排队顺序调整）。它的缺点是：不能随机访问（无法快速知道第几个元素是啥），而且每个元素需要额外存储两个指针，内存开销比vector大。
vector：需要在尾部频繁添加/删除，但几乎不在中间操作；或者需要快速随机访问（比如用下标取第n个数据）。它像个数组，内存连续。
deque（双端队列）：既需要在头部又需要在尾部频繁添加/删除，但很少在中间操作。它比list更省内存，且支持随机访问（但不如vector快）。

总结：如果你需要“在任意位置插拔”，首选 list；如果只是尾部操作，用 vector；如果头尾都要操作，用 deque。

7. 小练习（试一试）

创建一个 list 存放你一天中三个时间段的活动（比如“起床”、“写作业”、“睡觉”）。然后：

在“起床”后面插入“吃早饭”。
删除“写作业”（提示：可以使用 erase 配合迭代器查找）。
再在末尾添加一个“看电视”。

最后输出所有活动，看看顺序对不对。

8. 相关知识点指引

vector：动态数组，适合尾部操作和随机访问。
deque：双端队列，头尾操作都很快。
stack与queue：基于容器的适配器，分别实现栈和队列。
迭代器：所有STL容器都支持迭代器，学会它才能灵活操作各种容器。
算法：如 find、sort，结合迭代器用于list（注意list不能用全局sort，自己有sort成员函数）。

希望你现在对 list 这列“数据火车”有了更清晰的认识！动手写下你的第一个链表程序吧。

例题精讲