C++ 手写 List 容器：从双向链表到迭代器设计的完整实现

1. 项目概述为什么我们要手写一个 List 容器在 C 的世界里std::list是一个我们再熟悉不过的容器了。面试官爱问教科书里会讲但真正动手从头到尾实现一个的人恐怕不多。很多人对它的理解停留在“一个双向链表插入删除快随机访问慢”的层面至于它内部节点如何连接、迭代器怎么设计、内存如何管理往往是一知半解。这就是我决定动手实现一个List容器的初衷——不是为了替代标准库而是为了彻底搞懂它。当你亲手实现一遍你会发现很多“理所当然”的特性背后藏着精妙的设计考量。比如为什么std::list的size()方法在某些实现中可能是 O(n) 复杂度为什么它的迭代器失效规则如此特别通过从零搭建你将不再是一个 STL 容器的“使用者”而会成为其内部机制的“洞察者”。这对于深入理解 C 面向对象、模板、迭代器、异常安全乃至内存模型都是一次绝佳的实战演练。本次实战我们将构建一个具备完整功能的List容器包含迭代器、常用成员函数并通过详尽的测试来验证其正确性。2. 核心设计双向链表的数据结构与迭代器抽象2.1 节点ListNode的设计数据的基石一切链表的起点都是节点。对于双向链表每个节点需要存储三样东西数据本身、指向前一个节点的指针、指向后一个节点的指针。template typename T struct ListNode { T data; // 存储的数据 ListNode* prev; // 指向前驱节点 ListNode* next; // 指向后继节点 // 构造函数 ListNode(const T val T(), ListNode* p nullptr, ListNode* n nullptr) : data(val), prev(p), next(n) {} };这里有几个设计细节值得讨论使用struct而非class节点是一个纯粹的数据载体不需要封装复杂的成员函数如 getter/setter使用struct让数据成员默认为public在List类内部访问起来更直接、高效。这是一种常见的 C 惯用法。默认参数构造函数这个构造函数非常实用。val T()提供了数据的默认值对于内置类型是零值对于类类型调用其默认构造函数。prev和next默认为nullptr方便创建孤立节点或作为哨兵节点的初始状态。模板化使用模板template typename T使得我们的List能够容纳任意类型的元素这是现代 C 容器的基本要求。注意这里存在一个潜在的效率问题。构造函数参数const T val接受一个常引用但如果调用者传递的是一个右值例如临时对象这里会引发一次不必要的拷贝。在 C11 及以后的标准中我们可以通过添加移动构造函数ListNode(T val, ...)来优化。但在我们基础版本的实现中为了优先保证清晰度我们暂时使用拷贝。这是一个可以后续优化的点。2.2 迭代器Iterator的设计容器的灵魂迭代器是连接容器和算法的桥梁。对于链表它不能像vector的迭代器那样简单地是一个指针的别名因为它需要重载、--、*、-等操作符来模拟指针的行为同时正确地遍历节点。template typename T class ListIterator { public: // 必要的类型别名用于满足 STL 迭代器特性如 std::iterator_traits using value_type T; using pointer T*; using reference T; using difference_type std::ptrdiff_t; using iterator_category std::bidirectional_iterator_tag; // 双向迭代器 // 当前迭代器指向的节点指针 ListNodeT* node; // 构造函数 explicit ListIterator(ListNodeT* n nullptr) : node(n) {} // 解引用操作符获取节点数据的引用 reference operator*() const { return node-data; } // 成员访问操作符 pointer operator-() const { return (node-data); } // 前缀递增移动到下一个节点 ListIterator operator() { node node-next; return *this; } // 后缀递增 ListIterator operator(int) { ListIterator tmp *this; (*this); // 调用前缀递增 return tmp; } // 前缀递减移动到上一个节点 ListIterator operator--() { node node-prev; return *this; } // 后缀递减 ListIterator operator--(int) { ListIterator tmp *this; --(*this); return tmp; } // 比较操作符 bool operator(const ListIterator other) const { return node other.node; } bool operator!(const ListIterator other) const { return node ! other.node; } };为什么迭代器要设计成一个类因为我们需要自定义行为。指针的操作是内存地址的线性增加但链表节点的next指针指向的可能是内存中任意位置。我们必须通过重载操作符将的行为定义为node node-next。iterator_category的重要性将其定义为std::bidirectional_iterator_tag告诉标准库算法这个迭代器支持前进和后退--操作但不支持随机访问如iter 5。像std::reverse、std::prev这样的算法会根据这个标签选择最高效的实现。explicit关键字防止隐式转换。我们不想让一个ListNodeT*被意外地当作ListIterator使用这可能导致逻辑错误。强制显式构造让代码意图更清晰。2.3 常量迭代器ConstIterator的设计为了保证容器的const正确性我们需要一个不能修改所指数据的常量迭代器。一种朴素的方法是再写一个ListConstIterator类。但更优雅的方式是使用模板和继承。template typename T class ListConstIterator { public: using value_type T; using pointer const T*; // 指针和引用都是 const 的 using reference const T; using difference_type std::ptrdiff_t; using iterator_category std::bidirectional_iterator_tag; const ListNodeT* node; // 指向 const 节点 explicit ListConstIterator(const ListNodeT* n nullptr) : node(n) {} // 关键允许从普通迭代器隐式转换为常量迭代器这是安全的 ListConstIterator(const ListIteratorT iter) : node(iter.node) {} reference operator*() const { return node-data; } pointer operator-() const { return (node-data); } // ... 递增、递减、比较操作符与 ListIterator 类似但操作的是 const ListNodeT* };这里最精妙的一行是ListConstIterator(const ListIteratorT iter)。它使得我们可以将一个ListIterator赋值给一个ListConstIterator例如将begin()的返回值传给一个接受const_iterator参数的函数这是符合直觉且安全的。反之则不成立因为那会破坏const约定。3. List 容器本体的实现骨架与内存管理3.1 私有成员与哨兵节点Dummy Node我们的List类将采用一个带哨兵节点或称哑元节点的环形双向链表结构。这是实现上的一个关键技巧。template typename T class List { private: // 哨兵节点。它的 next 指向第一个真实节点prev 指向最后一个真实节点。 // 当链表为空时sentinel.next sentinel.prev sentinel; ListNodeT sentinel; size_t list_size; // 记录元素个数使 size() 为 O(1) public: using iterator ListIteratorT; using const_iterator ListConstIteratorT; using value_type T; // ... 后续成员函数 };为什么使用哨兵节点简化边界条件无论链表是否为空begin()永远返回sentinel.nextend()永远返回sentinel。插入和删除操作无需特殊处理头尾节点的情况代码逻辑统一。环形结构最后一个节点的next指向sentinelsentinel的prev指向最后一个节点。这使得从尾节点移动到“超尾”位置end()是自然的也方便实现rbegin()和rend()。list_size成员标准并未强制要求std::list::size()是常数时间但主流实现如 GCC、Clang 的 libstdc/libc都维护了一个大小变量。我们同样这样做以避免 O(n) 的遍历计算。3.2 构造函数、析构函数与拷贝控制这是体现 C 资源管理RAII精髓的地方。template typename T class List { public: // 1. 默认构造函数 List() : list_size(0) { sentinel.next sentinel; sentinel.prev sentinel; } // 2. 拷贝构造函数深拷贝 List(const List other) : List() { // 委托默认构造函数初始化哨兵 for (const auto val : other) { push_back(val); // 逐个元素拷贝插入 } } // 3. 拷贝赋值运算符 List operator(const List other) { if (this ! other) { // 防止自赋值 List tmp(other); // 利用拷贝构造函数 swap(tmp); // 与临时对象交换 } // tmp 析构释放原资源 return *this; } // 4. 析构函数 ~List() { clear(); // 清空所有元素 // sentinel 是栈上对象会自动销毁 } // 交换函数 void swap(List other) noexcept { using std::swap; // 交换哨兵节点的连接关系 if (list_size 0 other.list_size 0) { // 两者都为空交换后仍是空链表 } else if (list_size 0) { // this 为空other 不为空 sentinel.next other.sentinel.next; sentinel.prev other.sentinel.prev; other.sentinel.next-prev sentinel; other.sentinel.prev-next sentinel; other.sentinel.next other.sentinel; other.sentinel.prev other.sentinel; } else if (other.list_size 0) { // other 为空this 不为空 other.sentinel.next sentinel.next; other.sentinel.prev sentinel.prev; sentinel.next-prev other.sentinel; sentinel.prev-next other.sentinel; sentinel.next sentinel; sentinel.prev sentinel; } else { // 两者都不为空直接交换指针 swap(sentinel.next, other.sentinel.next); swap(sentinel.prev, other.sentinel.prev); // 更新相邻节点指向新哨兵 sentinel.next-prev sentinel; sentinel.prev-next sentinel; other.sentinel.next-prev other.sentinel; other.sentinel.prev-next other.sentinel; } swap(list_size, other.list_size); } private: // 内部链接辅助函数 void link_nodes(ListNodeT* prev_node, ListNodeT* new_node, ListNodeT* next_node) { prev_node-next new_node; new_node-prev prev_node; new_node-next next_node; next_node-prev new_node; list_size; } void unlink_node(ListNodeT* node) { node-prev-next node-next; node-next-prev node-prev; --list_size; delete node; // 释放节点内存 } };拷贝赋值运算符的“拷贝并交换”惯用法这是异常安全且简洁的写法。先创建临时副本tmp再与当前对象交换。如果拷贝构造失败可能因为内存不足tmp不会被创建当前对象状态不变保证了强异常安全性。交换成功后原对象的资源由临时对象tmp在析构时释放。swap的实现细节交换两个链表并非简单地交换sentinel和list_size。因为sentinel是对象的一部分其地址是固定的。我们必须交换哨兵节点所连接的“整个链表网络”。上面的实现处理了四种情况双空、此空彼非空、此非空彼空、双非空确保了交换后两个链表的结构完全正确。noexcept说明符表明此操作不会抛出异常这对于标准库容器在特定算法下的性能优化很重要。内部辅助函数link_nodes和unlink_node将节点插入和删除的指针操作封装起来避免了代码重复也使核心的insert和erase函数更清晰。4. 核心功能实现增删改查与迭代器4.1 元素访问与容量查询这些函数通常比较简单直接返回内部状态。template typename T class List { public: // 容量 size_t size() const { return list_size; } bool empty() const { return list_size 0; } // 元素访问不检查边界与 std::list 行为一致 T front() { // assert(!empty()); return sentinel.next-data; } const T front() const { // assert(!empty()); return sentinel.next-data; } T back() { // assert(!empty()); return sentinel.prev-data; } const T back() const { // assert(!empty()); return sentinel.prev-data; } // 迭代器 iterator begin() { return iterator(sentinel.next); } const_iterator begin() const { return const_iterator(sentinel.next); } const_iterator cbegin() const { return begin(); } iterator end() { return iterator(sentinel); } const_iterator end() const { return const_iterator(sentinel); } const_iterator cend() const { return end(); } };注意front()和back()在链表为空时调用是未定义行为。标准库的实现通常也不做检查。在实际项目中如果你需要安全访问可以先用empty()判断或者使用类似std::optional的包装。这里我们遵循标准库的“不检查”哲学将责任交给调用者。4.2 插入操作push_back,push_front,insert插入是链表的强项。我们利用哨兵节点和内部辅助函数使代码非常简洁。template typename T class List { public: // 在尾部插入 void push_back(const T value) { ListNodeT* new_node new ListNodeT(value, sentinel.prev, sentinel); link_nodes(sentinel.prev, new_node, sentinel); } // 在头部插入 void push_front(const T value) { ListNodeT* new_node new ListNodeT(value, sentinel, sentinel.next); link_nodes(sentinel, new_node, sentinel.next); } // 在指定位置前插入 iterator insert(iterator pos, const T value) { ListNodeT* pos_node pos.node; ListNodeT* new_node new ListNodeT(value, pos_node-prev, pos_node); link_nodes(pos_node-prev, new_node, pos_node); return iterator(new_node); // 返回指向新元素的迭代器 } };insert的返回值标准规定insert返回指向新插入元素的迭代器。这非常有用例如在循环中插入元素后我们可以继续从新位置开始操作而迭代器不会失效对于list插入操作不会使其他迭代器失效。关于右值引用和移动语义为了完善我们应该重载push_back(T value)和insert(iterator pos, T value)以及emplace_back和emplace函数以支持高效地插入临时对象。这是现代 C 的重要优化。基础版本为了聚焦核心逻辑我们暂不实现但你需要知道这是生产级代码必备的。4.3 删除操作pop_back,pop_front,erase,clear删除操作需要小心处理内存释放和迭代器失效。template typename T class List { public: // 删除尾部元素 void pop_back() { // assert(!empty()); unlink_node(sentinel.prev); } // 删除头部元素 void pop_front() { // assert(!empty()); unlink_node(sentinel.next); } // 删除指定位置的元素 iterator erase(iterator pos) { // assert(pos ! end()); // 不能删除 end() 迭代器 ListNodeT* to_erase pos.node; iterator next_iter(to_erase-next); // 保存下一个位置的迭代器 unlink_node(to_erase); return next_iter; // 返回被删除元素之后元素的迭代器 } // 删除一个区间 [first, last) iterator erase(iterator first, iterator last) { while (first ! last) { first erase(first); // erase 返回下一个迭代器循环继续 } return last; } // 清空链表 void clear() { while (!empty()) { pop_front(); // 或 pop_back都可以 } } };erase的返回值与迭代器失效erase返回被删除元素之后那个元素的迭代器。这是为了支持像it mylist.erase(it);这样的循环删除模式。对于list只有指向被删除元素的迭代器会失效其他迭代器包括end()仍然有效。这与vector或deque完全不同是链表数据结构带来的优势。clear()的实现我们循环调用pop_front()直到链表为空。pop_front()内部调用了unlink_node并delete节点。确保所有动态分配的内存都被正确释放。在析构函数中调用clear()是标准的 RAII 做法。4.4 其他常用操作splice,remove,unique,reverse,sort这些是list特有的高效算法因为它们可以操作内部指针而不需要移动或拷贝数据。template typename T class List { public: // 将另一个链表的所有元素移动到当前链表的 pos 之前 void splice(iterator pos, List other) { if (other.empty()) return; if (this other) return; // 自我拼接无意义 // 连接other 的第一个节点接到 pos 之前 ListNodeT* first other.sentinel.next; ListNodeT* last other.sentinel.prev; ListNodeT* pos_node pos.node; // 从 other 中摘除整个链表 other.sentinel.next other.sentinel; other.sentinel.prev other.sentinel; size_t moved_size other.list_size; other.list_size 0; // 插入到 this 中 first-prev pos_node-prev; last-next pos_node; pos_node-prev-next first; pos_node-prev last; list_size moved_size; } // 删除所有值等于 value 的元素 void remove(const T value) { iterator it begin(); while (it ! end()) { if (*it value) { it erase(it); // erase 返回下一个有效迭代器 } else { it; } } } // 反转链表 void reverse() noexcept { if (list_size 2) return; ListNodeT* current sentinel; do { ListNodeT* temp current-next; current-next current-prev; current-prev temp; current temp; } while (current ! sentinel); } };splice的高效性splice操作是O(1)的因为它只修改了几个指针没有元素的拷贝或移动。这是链表相对于顺序容器的巨大优势之一常用于合并链表或调整元素顺序。reverse的原地算法上面的reverse实现非常巧妙。它遍历每个节点交换其prev和next指针。由于是环形链表从哨兵节点开始遍历一圈后整个链表就被反转了。注意循环条件do...while和结束条件current ! sentinel确保哨兵节点的指针也被正确交换。关于sort链表的排序通常使用归并排序因为它可以很好地利用链表的特点不需要随机访问合并操作高效。实现一个完整的归并排序比较复杂但核心思想是递归地将链表分割成两半分别排序然后合并。许多教材将其作为经典练习题。在我们的基础实现中可以先不实现sort或者提供一个调用std::list::sort的接口如果我们的迭代器满足要求。5. 测试验证如何确保我们的 List 是正确的代码写完了但没经过测试的代码等于没写。我们需要一套全面的测试来验证容器的正确性、异常安全性和性能边界。5.1 基础功能测试我们从最简单的开始测试构造、插入、删除和遍历。#include cassert #include iostream #include MyList.h // 假设我们的 List 类定义在这个头文件里 void test_basic() { std::cout 基础功能测试 std::endl; Listint lst; // 测试空链表 assert(lst.empty()); assert(lst.size() 0); assert(lst.begin() lst.end()); // 测试 push_back 和 push_front lst.push_back(2); lst.push_front(1); lst.push_back(3); assert(lst.size() 3); assert(lst.front() 1); assert(lst.back() 3); // 测试迭代器遍历 int sum 0; for (int val : lst) { sum val; } assert(sum 6); // 123 // 测试 pop lst.pop_front(); assert(lst.front() 2); lst.pop_back(); assert(lst.back() 2); assert(lst.size() 1); // 测试 insert 和 erase auto it lst.begin(); it lst.insert(it, 0); // 在头部插入0 assert(lst.front() 0); it; // it 现在指向原来的 2 it lst.erase(it); // 删除 2 assert(lst.size() 1 lst.front() 0); lst.clear(); assert(lst.empty()); std::cout 基础测试通过 std::endl; }5.2 拷贝控制与异常安全测试这部分测试容器的“三/五法则”是否正确实现。void test_copy_and_swap() { std::cout \n 拷贝与交换测试 std::endl; Listint lst1; for (int i 0; i 5; i) lst1.push_back(i*10); // 0, 10, 20, 30, 40 // 拷贝构造函数 Listint lst2(lst1); assert(lst2.size() 5); auto it1 lst1.begin(); auto it2 lst2.begin(); while (it1 ! lst1.end()) { assert(*it1 *it2); it1; it2; } // 修改 lst2 不应影响 lst1 lst2.front() 100; assert(lst1.front() 0); // 拷贝赋值运算符 Listint lst3; lst3 lst1; assert(lst3.size() 5); // ... 类似的内容比较 // 自赋值测试 lst3 lst3; assert(lst3.size() 5); // 自赋值后应保持不变 // 交换测试 Listint lstA, lstB; lstA.push_back(1); lstA.push_back(2); lstB.push_back(3); lstB.push_back(4); lstB.push_back(5); size_t sizeA lstA.size(), sizeB lstB.size(); lstA.swap(lstB); assert(lstA.size() sizeB lstB.size() sizeA); assert(lstA.front() 3 lstB.front() 1); std::cout 拷贝与交换测试通过 std::endl; }自赋值测试的重要性a a这种操作看起来傻但确实可能发生尤其是在模板或宏代码中。我们的“拷贝并交换”实现天然地正确处理了自赋值因为if (this ! other)检查会阻止不必要的操作。5.3 复杂操作与边界条件测试测试splice、remove、reverse等高级功能以及空链表、单个元素链表等边界情况。void test_advanced_and_edge_cases() { std::cout \n 高级功能与边界测试 std::endl; Listint lst; // 边界对空链表进行 pop/erase 操作应断言失败或未定义我们这里不主动触发 // lst.pop_back(); // 在 Debug 模式下应触发 assert // 边界单个元素链表 lst.push_back(42); assert(lst.front() lst.back()); lst.pop_back(); assert(lst.empty()); // 测试 splice Listint lstA, lstB; lstA.push_back(1); lstA.push_back(2); lstB.push_back(3); lstB.push_back(4); lstA.splice(lstA.end(), lstB); // 将 lstB 拼接到 lstA 末尾 assert(lstA.size() 4 lstB.empty()); int expected[] {1, 2, 3, 4}; int idx 0; for (int val : lstA) { assert(val expected[idx]); } // 测试 remove lstA.push_back(2); lstA.push_back(2); lstA.remove(2); assert(lstA.size() 2); // 只剩下 1 和 3不对上一步拼接后是 1,2,3,4再添加两个2变成1,2,3,4,2,2移除所有2后剩下1,3,4 // 让我们重新计算 lstA.clear(); lstA.push_back(1); lstA.push_back(2); lstA.push_back(3); lstA.push_back(4); lstA.push_back(2); lstA.push_back(2); lstA.remove(2); assert(lstA.size() 3); Listint lstCheck; lstCheck.push_back(1); lstCheck.push_back(3); lstCheck.push_back(4); auto itA lstA.begin(); auto itC lstCheck.begin(); while (itA ! lstA.end()) { assert(*itA *itC); itA; itC; } // 测试 reverse Listint lstR; for (int i 1; i 5; i) lstR.push_back(i); lstR.reverse(); auto rit lstR.begin(); for (int i 5; i 1; --i) { assert(*rit i); rit; } std::cout 高级功能与边界测试通过 std::endl; }5.4 内存泄漏检查对于手动管理内存的容器内存泄漏是致命的。我们可以使用一些简单的方法来检查。在析构函数中加入调试输出在ListNode的析构函数或List的clear()中加入打印观察节点是否被正确销毁。使用 Valgrind 或 AddressSanitizer这是更专业的方法。在 Linux/macOS 下使用valgrind ./your_test_program运行测试程序它会报告是否有内存泄漏。编写一个循环创建和销毁大量链表的测试在循环中创建包含大量元素的链表然后让其离开作用域被销毁。同时监控程序的内存使用情况如任务管理器看内存是否平稳没有持续增长。void test_memory_leak() { // 这是一个压力测试并非严格意义上的内存泄漏检测但能暴露问题 const int OUTER_LOOPS 1000; const int INNER_SIZE 1000; for (int i 0; i OUTER_LOOPS; i) { Listint temp_list; for (int j 0; j INNER_SIZE; j) { temp_list.push_back(j); } // temp_list 在此处析构应释放所有内存 } std::cout \n内存压力测试完成。如果程序没有崩溃且内存使用稳定则初步判断无内存泄漏。 std::endl; }6. 常见问题与实战心得在实现和测试过程中我踩过不少坑也总结出一些心得。6.1 迭代器失效规则这是使用任何容器都必须牢记于心的。对于我们的List插入操作insert,push_back,push_front不会使任何已存在的迭代器失效。这是链表最大的优势之一。删除操作erase,pop_back,pop_front只有指向被删除元素的迭代器会失效。指向其他元素的迭代器仍然有效。重要这意味着你不能在删除一个元素后再使用指向它的迭代器。但你可以安全地使用erase的返回值指向下一个元素的迭代器来继续遍历。// 正确的遍历删除方式 for (auto it mylist.begin(); it ! mylist.end(); /* 这里不递增 */) { if (condition(*it)) { it mylist.erase(it); // erase 返回下一个迭代器 } else { it; } } // 错误的方式在 erase 后继续使用旧的 it6.2 关于size()的复杂度我们选择了 O(1) 的实现维护了一个list_size成员。这带来了轻微的空间开销和每次增删操作时维护该变量的开销但换来了size()的常数时间查询。标准库的实现策略允许 O(n)但现代实现为了用户体验基本都采用了 O(1)。这是一个典型的空间换时间的权衡。6.3 哨兵节点的内存开销每个List对象都有一个sentinel节点即使链表为空。对于存储大量小型List对象的场景这个开销是存在的。但它的好处——简化代码逻辑、消除边界判断——在大多数情况下远大于其成本。这也是标准库std::list的常见实现方式。6.4 模板的分离编译问题如果你将List的成员函数实现放在.cpp文件里然后在另一个.cpp文件中使用Listint很可能会遇到链接错误。这是因为模板代码需要在编译时看到完整的定义。解决方案将整个模板类的定义和实现都放在头文件.hpp或.h中。这是 C 模板编程的一个基本规则。6.5 如何更进一步迈向生产级代码我们这个实现是一个教学版本为了清晰牺牲了一些高级特性和优化异常安全我们的push_back等操作在new失败时会抛出std::bad_alloc但容器会保持原有状态强异常安全。更复杂的操作如insert多个元素需要更精细的保证。移动语义实现push_back(T),emplace_back(Args...)等可以大幅提升插入临时对象的效率。自定义分配器标准库容器支持自定义分配器。我们可以为List添加一个Allocator模板参数让用户控制节点的内存分配策略。C20 概念约束可以为模板参数T添加约束例如要求T是可拷贝构造/可析构的提供更清晰的编译错误信息。性能剖析与std::list进行性能对比测试特别是在大规模插入、删除、遍历和拼接操作上分析差距并优化。手写一个完整的容器是一次深刻的修行。它强迫你去思考每一个细节内存如何布局、指针如何跳动、异常何时抛出、迭代器如何行走。当你完成它再回头去看std::list的文档那些冰冷的描述会变得鲜活起来。你会真正理解为什么链表在某些场景下不可替代也会更清醒地认识到它在缓存不友好、内存开销大等方面的劣势。这种从内到外的理解是仅仅阅读文档或使用 API 无法获得的。