C++ list 容器完全指南：从入门到手撕双向链表

1.1 list 的基本概念

list 是 C++ 标准模板库（STL）中的一种序列容器，其底层实现是一个带头结点的双向循环链表。这意味着：

• 每个元素（节点）包含三部分：前驱指针、数据、后继指针。

• 链表的头节点不存储有效数据，仅作为哨兵，简化边界操作。

• 最后一个节点的后继指向头节点，头节点的前驱指向尾节点，形成循环。

这种结构赋予了 list 两个核心特性：

• 任意位置插入/删除 O(1)（前提是已经找到位置）。

• 不支持随机访问（不能使用 [] 或 + 偏移）。

1.2 为什么有了 vector 还需要 list？

因此，当你的程序需要频繁在中间位置插入删除，并且不关心随机访问时，list 是更合适的选择。例如：实现 LRU 缓存、消息队列、邻接表等。

二、list 的基本使用

使用 list 需要包含 <list> 头文件。

2.1 构造方式

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

int main() {
list<int> l1; // 空链表
list<int> l2(5, 10); // 5 个节点，值均为 10
list<int> l3(l2); // 拷贝构造
list<int> l4(l2.begin(), l2.end()); // 迭代器区间构造

int arr[] = {1,2,3,4,5};
list<int> l5(arr, arr+5); // 数组构造

for (auto x : l5) cout << x << " "; // 1 2 3 4 5
return 0;
}

2.2 迭代器与遍历

list 的迭代器是双向迭代器，支持 ++、–，但不支持 +n 或 -n。

遍历方式示例：

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

// 正向迭代器
for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
cout << *it << " ";

// 反向迭代器（逆向遍历）
for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit)
cout << *rit << " "; // 5 4 3 2 1

// 范围 for
for (auto e : l) cout << e << " ";

注意：++ 操作对于 list 迭代器是 O(1) 的，但它是顺着节点的 next 指针移动，不是简单的地址加常数。因此不要试图用 it + 5，编译器会报错。

2.3 容量与元素访问

list<int> l = {10,20,30};
cout << l.front() << endl; // 10
cout << l.back() << endl; // 30

2.4 修改操作：增删改查

代码示例：

list<int> l;
l.push_back(1); // 1
l.push_front(0); // 0 1
l.push_back(2); // 0 1 2
l.pop_front(); // 1 2
l.pop_back(); // 1

auto it = l.begin();
l.insert(it, 10); // 在第一个元素前插入 10 -> 10 1

it = l.begin();
++it;
l.erase(it); // 删除第二个元素（1） -> 10

for (auto e : l) cout << e << " "; // 10

三、list 迭代器失效 —— 与 vector 的重大区别

迭代器失效是指迭代器原本指向的元素被销毁，导致迭代器不再有效。由于 list 和 vector 的底层结构不同，失效规则也完全不同。

3.1 list 的失效规则

• 插入操作：insert、push_front、push_back 等不会导致任何现有迭代器失效。因为插入只是创建新节点、调整相邻节点的指针，原节点在内存中的位置不变。

• 删除操作：erase、pop_front、pop_back 会使指向被删除节点的迭代器失效，但其他迭代器（包括被删除节点前后的节点）仍然有效。

3.2 典型错误示例

list<int> l = {1,2,3,4,5};
auto it = l.begin();
while (it != l.end()) {
l.erase(it); // 删除 it 指向的节点，it 立即失效
++it; // 错误！对失效迭代器执行 ++ 未定义行为
}

3.3 正确删除所有节点

方法一：利用 erase 返回下一个有效迭代器

while (it != l.end()) {
it = l.erase(it); // erase 返回被删节点的下一个位置
}

方法二：使用 it++ 技巧（先拷贝，再递增原迭代器）

while (it != l.end()) {
l.erase(it++); // 先用 it 的副本删除，然后 it 自增到下一个节点
}

两种方式均可安全删除所有节点。建议使用第一种，语义更清晰。

3.4 对比 vector

因此，list 在需要频繁修改、且希望迭代器保持稳定的场景下非常有优势。

四、list 的模拟实现 —— 揭开底层面纱

为了真正理解 list，我们尝试手写一个简化版，命名为 bit::list。主要实现：节点结构、迭代器封装、基本增删查改。

4.1 节点结构

namespace bit {
template<class T>
struct _list_node {
_list_node<T>* _prev;
_list_node<T>* _next;
T _data;

_list_node(const T& val = T())
: _prev(nullptr), _next(nullptr), _data(val)
{}
};
}

4.2 迭代器封装

list 的迭代器不能是原生指针，因为节点在内存中不连续。我们需要封装一个类，重载 ++、–、*、-> 等运算符。

template<class T>
struct _list_iterator {
typedef _list_node<T> node;
typedef _list_iterator<T> self;

node* _pnode;

_list_iterator(node* p) : _pnode(p) {}

// 解引用
T& operator*() { return _pnode->_data; }
T* operator->() { return &_pnode->_data; }

// 前置++
self& operator++() {
_pnode = _pnode->_next;
return *this;
}
// 后置++
self operator++(int) {
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
// 前置–
self& operator–() {
_pnode = _pnode->_prev;
return *this;
}
// 后置–
self operator–(int) {
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}

bool operator==(const self& other) const { return _pnode == other._pnode; }
bool operator!=(const self& other) const { return _pnode != other._pnode; }
};

4.3 list 主体

template<class T>
class list {
public:
typedef _list_node<T> node;
typedef _list_iterator<T> iterator;

private:
node* _head; // 哨兵头节点（不存储有效数据）
size_t _size; // 可选，方便 size() O(1)

public:
// 构造
list() {
_head = new node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}

// 拷贝构造
list(const list<T>& other) : _head(nullptr), _size(0) {
_head = new node;
_head->_prev = _head;
_head->_next = _head;
for (auto e : other) push_back(e);
}

// 析构
~list() {
clear();
delete _head;
_head = nullptr;
}

// 赋值运算符（现代写法）
list<T>& operator=(list<T> other) {
swap(other);
return *this;
}

void swap(list<T>& other) {
std::swap(_head, other._head);
std::swap(_size, other._size);
}

// 迭代器
iterator begin() { return iterator(_head->_next); }
iterator end() { return iterator(_head); }

// 容量
size_t size() const { return _size; }
bool empty() const { return _size == 0; }

// 元素访问
T& front() { return *begin(); }
T& back() { return *(–end()); }

// 修改
void push_back(const T& val) { insert(end(), val); }
void push_front(const T& val) { insert(begin(), val); }
void pop_back() { erase(–end()); }
void pop_front() { erase(begin()); }

iterator insert(iterator pos, const T& val) {
node* cur = pos._pnode;
node* prev = cur->_prev;
node* new_node = new node(val);
// 链接
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = cur;
cur->_prev = new_node;
++_size;
return iterator(new_node);
}

iterator erase(iterator pos) {
node* cur = pos._pnode;
node* prev = cur->_prev;
node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
–_size;
return iterator(next);
}

void clear() {
iterator it = begin();
while (it != end())
it = erase(it);
}
};

4.4 反向迭代器的实现（了解）

STL 中反向迭代器可以通过适配正向迭代器来实现：

template<class Iterator>
class ReverseListIterator {
Iterator _it;
public:
ReverseListIterator(Iterator it) : _it(it) {}
auto operator*() {
Iterator tmp = _it;
–tmp;
return *tmp;
}
ReverseListIterator& operator++() { –_it; return *this; }
ReverseListIterator operator++(int) { auto tmp = *this; –_it; return tmp; }
// 其它运算符类似 …
};

五、list 与 vector 对比：一张表看懂

六、常见误区与最佳实践

6.1 避免对 list 使用 std::sort

std::sort 要求随机访问迭代器，而 list 只提供双向迭代器。如果想对 list 排序，应使用其成员函数 sort()（归并排序，O(n log n)）。

list<int> l = {5,2,8,1,4};
l.sort(); // 正确，1 2 4 5 8
// std::sort(l.begin(), l.end()); // 错误，编译失败

6.2 慎用 size() 在 O(n) 实现中

早期某些 STL 实现中，list::size() 是 O(n) 的（需要遍历链表）。虽然 C++11 要求为 O(1)，但在某些旧环境或特定实现下仍可能存在。如果必须反复获取大小，可以自己维护一个变量。

6.3 利用 splice 高效转移节点

list 提供了 splice 操作，可以在 O(1) 时间内将一个链表的节点转移到另一个链表，无需复制数据。这是 vector 无法做到的。

list<int> l1 = {1,2,3};
list<int> l2 = {4,5};
auto it = l1.begin();
++it; // 指向 2
l1.splice(it, l2); // 将 l2 全部节点插入到 it 之前，l2 变为空
// l1 变为 1 4 5 2 3

七、总结

• list 的核心优势：O(1) 的任意位置插入删除，迭代器在插入时永不失效。

• 核心劣势：不支持随机访问，缓存不友好，每个元素额外占用指针内存。

• 使用场景：适合需要频繁增删且不关心索引的场景，如 LRU 缓存、消息队列、邻接表等。

• 迭代器失效：只有删除操作会让指向被删节点的迭代器失效，插入不会。

• 模拟实现：理解 list 的节点结构、迭代器封装和双向指针维护，是迈向高手的重要一步。

学习 list 不仅能让你熟练使用 STL，更能加深对链式数据结构、迭代器设计模式的理解。下一篇文章我们将深入 deque 容器——它既是“双端队列”，也是 stack 和 queue 的底层基石，敬请期待！

练习题推荐：

• LeetCode 146. LRU 缓存（需要用 list 或手写链表）

• LeetCode 2. 两数相加（链表操作）

• LeetCode 25. K 个一组翻转链表（链表综合题）