1.1 list 的基本概念list是 C 标准模板库STL中的一种序列容器其底层实现是一个带头结点的双向循环链表。这意味着每个元素节点包含三部分前驱指针、数据、后继指针。链表的头节点不存储有效数据仅作为哨兵简化边界操作。最后一个节点的后继指向头节点头节点的前驱指向尾节点形成循环。这种结构赋予了list两个核心特性任意位置插入/删除 O(1)前提是已经找到位置。不支持随机访问不能使用[]或偏移。1.2 为什么有了 vector 还需要 list操作vectorlist尾插O(1) 均摊O(1)中间插入O(n)需搬移元素O(1)只需改指针随机访问O(1)O(n)缓存友好高连续内存低节点分散因此当你的程序需要频繁在中间位置插入删除并且不关心随机访问时list是更合适的选择。例如实现 LRU 缓存、消息队列、邻接表等。二、list 的基本使用使用list需要包含list头文件。2.1 构造方式#include list #include iostream using namespace std; int main() { listint l1; // 空链表 listint l2(5, 10); // 5 个节点值均为 10 listint l3(l2); // 拷贝构造 listint l4(l2.begin(), l2.end()); // 迭代器区间构造 int arr[] {1,2,3,4,5}; listint l5(arr, arr5); // 数组构造 for (auto x : l5) cout x ; // 1 2 3 4 5 return 0; }2.2 迭代器与遍历list的迭代器是双向迭代器支持、--但不支持n或-n。迭代器说明begin()/end()正向迭代器begin指向第一个有效节点end指向头节点哨兵。rbegin()/rend()反向迭代器rbegin指向最后一个节点rend指向头节点之前的位置。遍历方式示例listint l {1,2,3,4,5}; // 正向迭代器 for (listint::iterator it l.begin(); it ! l.end(); it) cout *it ; // 反向迭代器逆向遍历 for (listint::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 容量与元素访问listint l {10,20,30}; cout l.front() endl; // 10 cout l.back() endl; // 30函数作用empty()判断是否为空size()返回节点个数O(n)因为链表通常不存储长度变量实际上大多数实现中 size 是缓存好的O(1)front()返回第一个元素的引用back()返回最后一个元素的引用2.4 修改操作增删改查函数说明push_front(val)头插pop_front()头删push_back(val)尾插pop_back()尾删insert(pos, val)在迭代器 pos 之前插入 valerase(pos)删除迭代器 pos 处的节点clear()清空所有有效节点swap(list)交换两个链表的内容只是交换头指针O(1)代码示例listint 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 典型错误示例listint 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操作vector 迭代器失效list 迭代器失效尾插未扩容所有迭代器有效所有迭代器有效尾插扩容所有迭代器失效不适用list 不扩容中间插入插入点之后所有迭代器失效仅新节点自己不插入不影响已有迭代器删除删除点之后所有迭代器失效仅被删节点的迭代器失效因此list在需要频繁修改、且希望迭代器保持稳定的场景下非常有优势。四、list 的模拟实现 —— 揭开底层面纱为了真正理解list我们尝试手写一个简化版命名为bit::list。主要实现节点结构、迭代器封装、基本增删查改。4.1 节点结构namespace bit { templateclass T struct _list_node { _list_nodeT* _prev; _list_nodeT* _next; T _data; _list_node(const T val T()) : _prev(nullptr), _next(nullptr), _data(val) {} }; }4.2 迭代器封装list的迭代器不能是原生指针因为节点在内存中不连续。我们需要封装一个类重载、--、*、-等运算符。templateclass T struct _list_iterator { typedef _list_nodeT node; typedef _list_iteratorT 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 主体templateclass T class list { public: typedef _list_nodeT node; typedef _list_iteratorT 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 listT 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; } // 赋值运算符现代写法 listT operator(listT other) { swap(other); return *this; } void swap(listT 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 中反向迭代器可以通过适配正向迭代器来实现templateclass 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 对比一张表看懂对比维度vectorlist底层结构连续数组带头双向循环链表随机访问O(1)O(n)头部插入/删除O(n)搬移所有元素O(1)中间插入/删除O(n)搬移后续元素O(1)前提已知位置尾部插入/删除O(1)均摊O(1)内存占用紧凑无额外指针每个元素多两个指针8或16字节额外开销缓存命中率极高连续内存极低节点分散跳转多迭代器类型随机访问迭代器双向迭代器插入时迭代器失效扩容时全部失效不失效删除时迭代器失效被删元素及之后全部失效仅被删元素失效适用场景需要快速随机访问元素数量相对稳定尾部操作多频繁在任意位置插入删除不关心随机访问如链表、LRU、队列六、常见误区与最佳实践6.1 避免对 list 使用std::sortstd::sort要求随机访问迭代器而list只提供双向迭代器。如果想对list排序应使用其成员函数sort()归并排序O(n log n)。listint 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) 的需要遍历链表。虽然 C11 要求为 O(1)但在某些旧环境或特定实现下仍可能存在。如果必须反复获取大小可以自己维护一个变量。6.3 利用 splice 高效转移节点list提供了splice操作可以在 O(1) 时间内将一个链表的节点转移到另一个链表无需复制数据。这是vector无法做到的。listint l1 {1,2,3}; listint 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 个一组翻转链表链表综合题