C++ STL 双向链表容器 list 详解与模拟实现

2.迭代器

由于 list 不支持随机访问，只能通过迭代器或 front/back 方法访问元素：

list<int> l = { 1, 2, 3, 4, 5 };
cout << l.front() << endl; // 第一个元素 (1)
cout << l.back() << endl;  // 最后一个元素 (5)

// 遍历 list
for (auto it = l.begin(); it != l.end(); ++it) {
    cout << *it << " ";
}
cout << endl;

// C++11 起可用范围 for 循环
for (int val : l) {
    cout << val << " ";
}
return 0;

3.拷贝构造

直接利用赋值运算符或构造函数即可完成深拷贝，无需手动干预。

4.clear()

效果：清空链表中所有数据，释放节点内存。

5.size()

返回链表中节点的个数。

6.push_back(const T& x)

在链表尾部插入值为 x 的节点。

7.push_front(const T& x)

在链表头部插入值为 x 的节点。

8.insert(iterator pos, const T& x)

在第 pos 个位置插入值为 x 的节点。

9.pop_back()

删除尾部元素。

10.pop_front()

删除头部元素。

11.erase(iterator pos)

删除第 pos 位置的元素。

三、list 的模拟实现

为了深入理解底层机制，我们可以通过 STL 库学习一下 list 的基本实现方法，然后自己根据源码逻辑模拟实现一个 list。

通过库中代码，我们需要先实现出 list 底层节点的模板以及迭代器所需要的模板，然后在构造函数中完成初始化。

1.节点与迭代器定义

首先定义节点结构和迭代器类。注意迭代器需要重载解引用、自增自减及比较运算符。

#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <iostream>
using namespace std;

namespace lwf {
    // 创建模板结构体
    template<class T>
    struct list_node {
        list_node<T>* _next;
        list_node<T>* _prev;
        T _val;
        list_node(const T& val = T()) :_next(nullptr), _prev(nullptr), _val(val) {}
    };

    // 迭代器模板
    template<class T, class Ref, class Ptr>
    struct _list_iterator {
        typedef list_node<T> Node;
        typedef _list_iterator<T, Ref, Ptr> self;
        Node* _node;
        _list_iterator(Node* node) :_node(node) {}

        Ref operator*() { return _node->_val; }
        Ptr operator->() { return &_node->_val; }

        self& operator++() {
            _node = _node->_next;
            return *this;
        }
        self operator++(int) {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        self& operator--() {
            _node = _node->_prev;
            return *this;
        }
        self operator--(int) {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        bool operator!=(const self& it) { return _node != it._node; }
        bool operator==(const self& it) { return _node == it._node; }
    };

    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;

        void empty_init() {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            _size = 0;
        }

        list() { empty_init(); }

        list(const list<T>& It) {
            empty_init();
            for (auto& e : It) {
                push_back(e);
            }
        }

        iterator begin() {
            return _head->_next;
        }
        iterator end() {
            return _head;
        }
        const_iterator begin()const {
            return _head->_next;
        }
        const_iterator end()const {
            return _head;
        }

        void swap(list<T> It) {
            std::swap(_head, It._head);
            std::swap(_size, It._size);
        }
        list<T>& operator=(list<T> It) {
            swap(It);
            return *this;
        }

        ~list() {
            clear();
            delete _head;
            _head = nullptr;
        }

        void clear() {
            iterator it = begin();
            while (it != end()) {
                it = erase(it);
            }
            _size = 0;
        }

        size_t size() {
            return _size;
        }

        void push_back(const T& x) {
            insert(end(), x);
        }

        void push_front(const T& x) {
            insert(begin(), x);
        }

        void pop_back() {
            erase(--end());
        }

        void pop_front() {
            erase(begin());
        }

        iterator insert(iterator pos, const T& x) {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);
            prev->_next = newnode;
            newnode->_prev = prev;
            cur->_prev = newnode;
            newnode->_next = cur;
            ++_size;
            // 解决迭代器失效问题，返回新节点对应的迭代器
            return iterator(newnode);
        }

        iterator erase(iterator pos) {
            assert(pos != end());
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;
            prev->_next = next;
            next->_prev = prev;
            delete cur;
            --_size;
            // 返回下一个有效位置
            return iterator(next);
        }

    private:
        Node* _head;
        size_t _size;
    };

    void Test_1() {
        list<int> It;
        It.push_back(1);
        It.push_back(2);
        It.push_back(3);
        It.push_back(4);
        It.push_front(5);
        It.push_front(6);
        It.push_front(7);
        It.push_front(8);
        for (auto& e : It) {
            cout << e << " ";
        }
        cout << endl;
        It.pop_back();
        It.pop_front();
        for (auto& e : It) {
            cout << e << " ";
        }
        cout << endl;
    }

    void Test_2() {
        list<int> It;
        It.push_back(1);
        It.push_back(2);
        It.push_back(3);
        It.push_back(4);
        It.push_front(5);
        It.push_front(6);
        It.push_front(7);
        It.push_front(8);
        for (auto& e : It) {
            cout << e << " ";
        }
        cout << endl;
        It.pop_back();
        It.pop_front();
        for (auto& e : It) {
            cout << e << " ";
        }
        cout << endl;
        It.clear();
        It.push_front(50);
        It.push_front(60);
        It.push_front(70);
        It.push_front(80);
        for (auto& e : It) {
            cout << e << " ";
        }
        cout << endl;
        cout << It.size() << endl;
    }

    void Test_3() {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        for (auto e : lt) {
            cout << e << " ";
        }
        cout << endl;
        list<int> lt1(lt);
        for (auto e : lt1) {
            cout << e << " ";
        }
        cout << endl;
        list<int> lt2;
        lt2.push_back(10);
        lt2.push_back(20);
        lt2.push_back(30);
        lt2.push_back(40);
        for (auto e : lt2) {
            cout << e << " ";
        }
        cout << endl;
        lt1 = lt2;
        for (auto e : lt1) {
            cout << e << " ";
        }
        cout << endl;
    }
}

四、关键实现细节说明

在模拟实现过程中，有几个点值得注意：

1. 哨兵节点：我们使用了一个虚拟头节点 _head，它的前驱指向尾节点，后继指向首节点，形成一个闭环。这样处理边界情况（如空表、头插、尾删）会统一很多。
2. 迭代器失效：在 erase 操作中，删除当前节点后，必须返回下一个有效节点的迭代器，否则调用者无法继续遍历。insert 同理，虽然不破坏现有迭代器，但返回新节点便于后续操作。
3. 内存管理：析构函数中先调用 clear 释放所有数据节点，最后释放哨兵节点，避免悬空指针。
4. 赋值运算符：采用交换法 (swap) 实现，既安全又高效，避免了浅拷贝带来的资源冲突。