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

个人主页: 起名字真南的CSDN博客

个人专栏:

• 【数据结构初阶】 📘 基础数据结构
• 【C语言】 💻 C语言编程技巧
• 【C++】 🚀 进阶C++
• 【OJ题解】 📝 题解精讲

目录

📌 1. 引言

在 C++ 中，STL

list

容器提供了双向链表的实现，适用于需要频繁插入和删除的场景。本文将手把手带你实现一个自定义的

list

容器，详细解析双向链表的节点设计、迭代器实现、增删操作等。希望通过本文的学习，你能对链表的底层原理有更深入的理解，并学会如何用 C++ 实现一个高效的

list

容器。

📌 2. 内容概要

• 双向链表的基本结构设计
• 自定义迭代器的实现原理
• 核心方法实现：push_back、insert、erase等
• 内存管理与析构函数
• 性能分析与应用场景

📌 3.

list

容器结构设计

✨ 3.1 节点结构设计

在双向链表中，每个节点包含数据域和两个指针域，分别指向前后节点。我们首先定义节点的结构体

list_node

，用于存储数据和链接信息。

template<classT>structlist_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<classT,classRef,classPtr>structlist_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;}booloperator!=(const list_iterator& other)const{return _node != other._node;}booloperator==(const list_iterator& other)const{return _node == other._node;}};

• 代码解读： - operator* 和 operator->：分别返回节点的值和地址。- ++ 和 --：支持前后遍历。- == 和 !=：判断两个迭代器是否指向相同节点。

📌 4.

list

容器的实现

✨ 4.1 核心成员函数

• 构造函数：初始化一个空的链表，并设置头节点。
• **push_back 和 push_front**：在链表尾部或头部插入元素。
• **insert 和 erase**：在指定位置插入或删除元素。
• 析构函数：清理所有节点，防止内存泄漏。

template<classT>classlist{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 =newNode(); _head->_next = _head; _head->_prev = _head; _size =0;}~list(){clear();delete _head;}
    iterator begin(){return _head->_next;}
    iterator end(){return _head;}voidpush_back(const T& x){insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}
    iterator insert(iterator pos,const T& x){
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* newnode =newNode(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;}voidclear(){
        iterator it =begin();while(it !=end()) it =erase(it);}
    size_t size()const{return _size;}boolempty()const{return _size ==0;}private:
    Node* _head;
    size_t _size;};

📌 5. 代码示例和测试

这些测试函数覆盖了自定义

list

容器的基本功能，包括增删操作、迭代器遍历、插入与删除、拷贝构造、赋值运算等。在实际测试中，使用

print_container

输出链表内容，便于观察操作结果。

🚀5.1

test_list1()

• 测试基本的增删操作与遍历

voidtest_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()

• 测试插入、修改与迭代器失效问题

voidtest_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;// 将第一个元素加100print_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()

• 测试拷贝构造和赋值操作

voidtest_list3(){
    list<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    list<int>lt2(lt1);// 使用拷贝构造函数初始化lt2print_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++标准库和数据结构实现的相关知识：

• C++数据结构与算法：链表详解
• C++ 迭代器设计模式与实现技巧

📌 8. 互动与讨论

你在项目中使用过

list

吗？你对本实现有其他的优化建议吗？欢迎在评论区讨论，分享你的想法和见解！