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

个人专栏:

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

? 1. 引言

? 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++标准库和数据结构实现的相关知识：

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

? 8. 互动与讨论

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