【C++】从零实现 C++ 自定义 list 容器：双向链表与迭代器深度解析

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);
}

1
2
3
4

解释：

创建链表 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)，但随机访问的效率低，适合顺序访问或遍历操作。
————————————————

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/weixin_74837455/article/details/143649743