给新手看的 C++ List 完全入门指南（C++98 经典写法）

在很多 C++ 教材和面试题里，list 是个绕不开的容器。它不像 vector 那样连续存放数据，而是一个双向链表——每个元素都记着自己前一个和后一个是谁，所以不管链表有多长，在中间塞一个元素或者删一个元素，都只是一瞬间的事。

这篇文章不讲什么花里胡哨的新标准语法，全部用 C++98 的方式来写。你就算用的是老掉牙的 Visual C++ 6.0，代码也能原样编译通过。

---

一、最简单的开始：创建 list 并往里加数据

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

int main()
{
    list<int> lt;

    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    return 0;
}

push_back 就是往链表尾部加一个元素。每次调用，它都会在末尾造一个新节点，把数据塞进去，然后把前后指针接好。整个过程的复杂度是 O(1)，跟你链表里已经存了多少数据没关系。

对应的还有 push_front，往头部加。不过这篇文章先从最常用的 push_back 开始。

---

二、遍历链表：list 没有下标，得用迭代器

vector 你可以写 v[0]、v[1] 这样用下标访问，但 list 不行。链表的节点在内存里是东一个西一个的，根本不在同一片连续区域，所以没法用下标。

替代方案是 迭代器（iterator）。你可以把它理解成一个"智能指针"，指向链表里的某个节点，通过 ++ 就能走到下一个节点：

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    list<int>::iterator it = lt.begin();   // 指向第一个元素
    while (it != lt.end())                 // end() 是哨兵，不是最后一个元素
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    return 0;
}

// 输出: 1 2 3 4

Pasted image 20260629111206.png
这里有两个重要的概念要搞清楚：

• begin() 返回指向第一个元素的迭代器
• end() 返回的是最后一个元素的下一个位置，它是一个标记位，不是真实数据

所以遍历的条件是 it != lt.end()，不是 it <= lt.end()。list 的迭代器只支持 == 和 !=，不支持大小比较——因为节点之间在内存里没有大小关系可言。

---

三、在指定位置插入数据：insert

假设你有一个链表 1 2 3 4 5 6，你想在第三个位置（也就是 3 的前面）插入一个 30：

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);

// 让迭代器走到第三个位置
list<int>::iterator it = lt.begin();
int k = 3;
while (--k)
{
    ++it;
}

// 在 it 指向的位置前面插入 30
lt.insert(it, 30);

// 遍历打印
for (list<int>::iterator pos = lt.begin(); pos != lt.end(); ++pos)
{
    cout << *pos << " ";
}
cout << endl;

// 输出: 1 2 30 3 4 5 6

Pasted image 20260629111355.png
insert 不会让原来的迭代器失效——这在 list 里是一个重要特性。你插完数据之后，之前拿到的迭代器依然有效，指向的还是原来那个元素。

---

四、删除指定元素：erase

配合算法库里的 find，我们可以根据值来删除元素：

#include <algorithm>  // find 在这个头文件里

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);

int x;
cin >> x;

list<int>::iterator it = find(lt.begin(), lt.end(), x);
if (it != lt.end())
{
    lt.erase(it);   // 删除找到的元素
}

// 再次遍历查看结果
for (list<int>::iterator pos = lt.begin(); pos != lt.end(); ++pos)
{
    cout << *pos << " ";
}
cout << endl;

Pasted image 20260629111615.png
这里有一个关键点：erase 之后，被删除的那个迭代器就失效了。如果你还想继续遍历，必须用 erase 的返回值——它返回被删元素的下一个位置的迭代器。

比如删除链表中所有的偶数：

list<int> lt;
// ... 往里面加了很多数据

list<int>::iterator it = lt.begin();
while (it != lt.end())
{
    if (*it % 2 == 0)
    {
        it = lt.erase(it);   // 关键：用返回值接住
    }
    else
    {
        ++it;
    }
}

Pasted image 20260629112921.png
你要是写成 lt.erase(it); ++it; 那程序直接炸——it 已经是个野指针了，再对它 ++ 就是未定义行为。

---

五、sort 排序

list 有自己专属的 sort 成员函数，不能用标准库的 std::sort。原因还是那个：std::sort 需要随机访问迭代器（支持 it + 5 这种操作），但 list 的迭代器只支持一步步走，所以 STL 给你单独准备了一个成员函数：

list<double> lt;
lt.push_back(3.3);
lt.push_back(1.1);
lt.push_back(2.2);

lt.sort();  // 升序排列

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

// 输出: 1.1 2.2 3.3

Pasted image 20260629114459.png
注意，这是 lt.sort()，不是 sort(lt.begin(), lt.end())。别写错了。

---

六、merge：合并两个有序链表

如果你有两个各自排好序的链表，想把它们合并成一个，merge 是最快的方式：

list<double> first, second;

first.push_back(1.1);
first.push_back(1.2);
first.push_back(1.3);

second.push_back(2.1);
second.push_back(2.2);
second.push_back(2.3);

first.sort();
second.sort();

first.merge(second);   // second 里的内容全部移到 first 里

// 合并后 second 变成空的
cout << "second 的大小: " << second.size() << endl;  // 输出: 0

Pasted image 20260629114638.png
有两点要特别注意：

1. 合并前两个链表必须是排好序的，否则结果不是正确排序，只是按顺序归并
2. 合并后第二个链表就空了，它的元素不是被拷贝，而是被"转移"过去的——只动了指针，没有额外内存分配

---

七、unique：去掉连续的重复值

unique 会把链表中连续重复的元素干掉，只保留第一个：

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(4);   // 连着两个 4
lt.push_back(5);
lt.push_back(5);   // 连着两个 5
lt.push_back(6);
lt.push_back(6);   // 连着两个 6

lt.unique();

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

// 输出: 1 2 3 4 5 6

Pasted image 20260629114718.png
注意"连续"这两个字。如果你的数据是 1, 2, 1, 2，调用 unique 之后还是 1, 2, 1, 2，因为相同的 1 和 2 没有挨在一起。常规做法是先 sort() 再 unique()。

---

八、splice：链表的终极武器

splice 是 list 最特别的操作，没有之一。它可以把一个链表的某一段直接剪切到另一个链表的任意位置，全程只改了几个指针，一个元素都没有拷贝。

8.1把一个元素挪到最前面

有时候你想把链表里的某个元素"置顶"：

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);

    int x;
    cin >> x;

    list<int>::iterator it = find(lt.begin(), lt.end(), x);
    if (it != lt.end())
    {
        // 把从 it 开始到末尾的所有元素，全部挪到链表开头
        lt.splice(lt.begin(), lt, it, lt.end());
    }
    for (int val : lt)
    {
        cout << val << " ";
    }
    return 0;
}

// 如果输入 3，输出: 3 4 5 1 2

Pasted image 20260629115330.png
这个操作如果在 vector 里做，你得把 3、4、5 一个个拷贝挪到前面，再把后面的往前搬——复杂度 O(n)。而 list 只改了四个指针，O(1) 搞定。这就是链表最核心的优势。

---

九、push_back 和 emplace_back 的区别

文章主要讲 C++98，所以 emplace_back 要特别说明一下：它是 C++11 才引入的，C++98 里没有。

但哪怕你用的是老标准，了解一下它和 push_back 的区别也有好处。假设你有一个自定义类型：

struct A
{
    int _a1;
    int _a2;
    A(int a1 = 1, int a2 = 2) : _a1(a1), _a2(a2) {}
};

push_back 要求你传一个已经构造好的对象：

list<A> lt;

A aa1(1, 1);
lt.push_back(aa1);             // OK，传对象
lt.push_back(A(2, 2));         // OK，传匿名对象
// lt.push_back(3, 3);         // 错误！push_back 只接受一个参数

而 emplace_back 可以直接传构造参数，在链表内部原地构造：

// C++11 才能用
lt.emplace_back(3, 3);         // OK，直接传两个 int

本质上，emplace_back 省了一次拷贝构造。对于简单类型（int、double）无所谓，但对于复杂对象，能省就省