个人主页: 起名字真南的CSDN博客
个人专栏:
【数据结构初阶】 ? 基础数据结构【C语言】 ? C语言编程技巧【C++】 ? 进阶C++【OJ题解】 ? 题解精讲
目录
? 1. 引言? 2. 内容概要? 3. `list` 容器结构设计✨ 3.1 节点结构设计✨ 3.2 自定义迭代器的实现 ? 4. `list` 容器的实现✨ 4.1 核心成员函数 ? 5. 代码示例和测试?5.1 `test_list1()` - 测试基本的增删操作与遍历?5.2 `test_list2()` - 测试插入、修改与迭代器失效问题?5.3 `test_list3()` - 测试拷贝构造和赋值操作 ? 6. 性能分析与适用场景? 7. 总结与扩展阅读? 8. 互动与讨论
? 1. 引言
在 C++ 中，STL list 容器提供了双向链表的实现，适用于需要频繁插入和删除的场景。本文将手把手带你实现一个自定义的 list 容器，详细解析双向链表的节点设计、迭代器实现、增删操作等。希望通过本文的学习，你能对链表的底层原理有更深入的理解，并学会如何用 C++ 实现一个高效的 list 容器。
? 2. 内容概要
双向链表的基本结构设计自定义迭代器的实现原理核心方法实现：push_back、insert、erase等内存管理与析构函数性能分析与应用场景 ? 3. list 容器结构设计
✨ 3.1 节点结构设计
在双向链表中，每个节点包含数据域和两个指针域，分别指向前后节点。我们首先定义节点的结构体 list_node，用于存储数据和链接信息。
template<class T>struct list_node { T _data; list_node<T>* _prev; list_node<T>* _next; list_node(const T& data = T()) : _data(data), _prev(nullptr), _next(nullptr) {}};_data：存储节点的数据。_prev 和 _next：分别指向前一个和后一个节点，形成双向链接。 ✨ 3.2 自定义迭代器的实现
list 容器需要一个迭代器来支持前向和后向遍历。我们设计一个 list_iterator，封装节点指针，并重载 *、->、++、-- 等操作符。
template<class T, class Ref, class Ptr>struct list_iterator { typedef list_node<T> Node; Node* _node; list_iterator(Node* node = nullptr) : _node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } list_iterator& operator++() { _node = _node->_next; return *this; } list_iterator operator++(int) { list_iterator tmp(*this); _node = _node->_next; return tmp; } list_iterator& operator--() { _node = _node->_prev; return *this; } list_iterator operator--(int) { list_iterator tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const list_iterator& other) const { return _node != other._node; } bool operator==(const list_iterator& other) const { return _node == other._node; }};operator* 和 operator->：分别返回节点的值和地址。++ 和 --：支持前后遍历。== 和 !=：判断两个迭代器是否指向相同节点。 ? 4. list 容器的实现
✨ 4.1 核心成员函数
构造函数：初始化一个空的链表，并设置头节点。push_back 和 push_front：在链表尾部或头部插入元素。insert 和 erase：在指定位置插入或删除元素。析构函数：清理所有节点，防止内存泄漏。 template<class T>class list { typedef list_node<T> Node;public: typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; list() { _head = new Node(); _head->_next = _head; _head->_prev = _head; _size = 0; } ~list() { clear(); delete _head; } iterator begin() { return _head->_next; } iterator end() { return _head; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); newnode->_next = cur; cur->_prev = newnode; prev->_next = newnode; newnode->_prev = prev; ++_size; return newnode; } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return next; } void clear() { iterator it = begin(); while (it != end()) it = erase(it); } size_t size() const { return _size; } bool empty() const { return _size == 0; }private: Node* _head; size_t _size;};? 5. 代码示例和测试
这些测试函数覆盖了自定义 list 容器的基本功能，包括增删操作、迭代器遍历、插入与删除、拷贝构造、赋值运算等。在实际测试中，使用 print_container 输出链表内容，便于观察操作结果。
?5.1 test_list1() - 测试基本的增删操作与遍历
void test_list1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.pop_back(); // 删除最后一个元素 lt.pop_front(); // 删除第一个元素 // 使用迭代器遍历链表，并将每个元素加10 list<int>::iterator it = lt.begin(); while (it != lt.end()) { *it += 10; // 将每个元素的值加 10 cout << *it << " "; ++it; } cout << endl; // 使用自定义的print_container函数输出链表内容 print_container(lt);}解释：
初始化一个链表lt 并插入元素。删除链表的尾部和头部元素。使用迭代器遍历链表，并对元素加 10 后输出。print_container 函数打印链表的最终内容。 示例输出：
12 13 12 13 ?5.2 test_list2() - 测试插入、修改与迭代器失效问题
void test_list2() { 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(); lt.insert(it, 10); // 在开头插入10 *it += 100; // 将第一个元素加100 print_container(lt); // 遍历链表，删除所有偶数元素 it = lt.begin(); while (it != lt.end()) { if (*it % 2 == 0) { it = lt.erase(it); // 删除偶数元素，并接收下一个有效迭代器 } else { ++it; } } print_container(lt);}解释：
在链表开头插入10，然后修改第一个元素的值。通过迭代器遍历链表，删除所有偶数元素。使用 erase 时注意接收返回的迭代器，以防迭代器失效。 示例输出：
10 101 2 3 4 101 3 ?5.3 test_list3() - 测试拷贝构造和赋值操作
void test_list3() { list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); list<int> lt2(lt1); // 使用拷贝构造函数初始化lt2 print_container(lt1); print_container(lt2); list<int> lt3; lt3.push_back(10); lt3.push_back(20); lt3.push_back(30); lt3.push_back(40); // 测试赋值操作 lt1 = lt3; print_container(lt1); print_container(lt3);}解释：
创建链表lt1 并插入元素，使用 lt1 初始化链表 lt2（测试拷贝构造函数）。创建链表 lt3 并赋值给 lt1（测试赋值运算符的实现）。最后输出 lt1 和 lt3 的内容，验证 lt1 是否成功拷贝了 lt3 的数据。 示例输出：
1 2 3 4 1 2 3 4 10 20 30 40 10 20 30 40 ? 6. 性能分析与适用场景
适用场景：自定义list 容器适用于需要频繁插入和删除的场景，尤其是在链表头部和尾部操作较多时。性能分析：由于链表结构的特性，insert 和 erase 操作在已知位置的时间复杂度为 O(1)，但随机访问的效率低，适合顺序访问或遍历操作。 ? 7. 总结与扩展阅读
本文详细介绍了如何从零实现一个 C++ 双向链表 list 容器，包括节点结构、迭代器设计、增删操作等。通过这篇文章的学习，希望你对 list 的底层实现原理有了更深入的理解。推荐阅读以下文章进一步学习C++标准库和数据结构实现的相关知识：
? 8. 互动与讨论
你在项目中使用过 list 吗？你对本实现有其他的优化建议吗？欢迎在评论区讨论，分享你的想法和见解！