从双向链表到 List 容器：C++ 手写笔记

namespace MyList {
    template<class T, class Ref, class Ptr>
    struct list_iterator {
        using Self = list_iterator<T, Ref, Ptr>;
        using Node = list_node<T>;
        
        Node* _node;

        list_iterator(Node* node) : _node(node) {}

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

        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& s) const { return _node != s._node; }
        bool operator==(const Self& s) const { return _node == s._node; }
    };
}

注意迭代器只负责'导航'，不管节点内存的分配和释放，那都是容器的事。

容器类

list 类维护哨兵头节点 _head 和有效元素个数 _size。先写一个 empty_init()，创建哨兵节点并让它的前驱和后继都指向自己，形成自环。空链表和非空链表的插入/删除逻辑就统一了。

插入时，只需要调整四个指针：前驱的 _next、后继的 _prev、新节点的前后指针；删除时同理，调整前后节点跳过被删节点，然后释放内存。push_back/push_front 直接复用 insert，pop_back/pop_front 复用 erase，省去重复代码。

erase 返回下一个有效迭代器，这样使用者可以用 it = lst.erase(it) 安全更新迭代器，避免失效问题。

namespace MyList {
    template<class T>
    class list {
        using Node = list_node<T>;
    public:
        using iterator = list_iterator<T, T&, T*>;
        using const_iterator = list_iterator<T, const T&, const T*>;

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

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

        list() { empty_init(); }

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

        template<class InputIterator>
        list(InputIterator first, InputIterator last) {
            empty_init();
            while (first != last) {
                push_back(*first);
                ++first;
            }
        }

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

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

        void insert(iterator pos, const T& x) {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);

            newnode->_prev = prev;
            newnode->_next = cur;
            prev->_next = newnode;
            cur->_prev = newnode;

            ++_size;
        }

        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 iterator(next);
        }

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

        size_t size() const { return _size; }

    private:
        Node* _head;
        size_t _size = 0;
    };
}

测试验证

写几个用例，覆盖构造、插入、删除、迭代器访问和 const 场景。

基础构造 + 遍历：默认构造，尾插四个数，用迭代器和范围 for 输出。

#define _CRT_SECURE_NO_WARNINGS 1
#include "list.h"
using namespace std;

void test_list1() {
    MyList::list<int> lt;
    lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4);

    MyList::list<int>::iterator it = lt.begin();
    while (it != lt.end()) { cout << *it << " "; ++it; }
    cout << endl;

    for (auto e : lt) cout << e << " ";
    cout << "\n" << endl;
}

int main() {
    test_list1();
    return 0;
}

头插、头删、尾删：插入顺序和预期一致，size() 能反映变化。

void test_list2() {
    MyList::list<int> lt;
    lt.push_front(-2); lt.push_front(-1);
    lt.push_back(1); lt.push_back(2);
    cout << "头插+尾插后：";
    for (auto e : lt) cout << e << " "; // -1 -2 1 2
    cout << endl;

    lt.pop_back(); lt.pop_back();
    lt.pop_front(); lt.pop_front();
    cout << "删除后 size：" << lt.size() << endl; // 0
    cout << endl;
}

int main() {
    test_list2();
    return 0;
}

const 迭代器和拷贝构造：拷贝后修改原容器不影响副本，const 版本只读，尝试修改会编译报错。

void Print(const MyList::list<int>& lt) {
    MyList::list<int>::const_iterator it = lt.begin();
    while (it != lt.end()) {
        // *it = 10; // 编译报错
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

void test_list3() {
    MyList::list<int> lt1 = { 1,2,3,4,5,6 };
    MyList::list<int> lt2(lt1);
    cout << "lt2（拷贝 lt1）：";
    for (auto e : lt2) cout << e << " "; // 1 2 3 4 5 6
    cout << endl;

    const MyList::list<int>& clt = lt1;
    cout << "const 迭代器遍历 lt1：";
    Print(clt);
    cout << endl;
}

int main() {
    test_list3();
    return 0;
}

insert / erase / clear：在中间位置插入，删除后迭代器有效，clear() 后 size 归零。

void test_list4() {
    MyList::list<int> lt;
    lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4);

    auto it = lt.begin();
    ++it;
    lt.insert(it, 100);
    cout << "插入 100 后：";
    for (auto e : lt) cout << e << " "; // 1 100 2 3 4
    cout << endl;

    it = lt.begin();
    ++it;
    it = lt.erase(it);
    cout << "删除 100 后：";
    for (auto e : lt) cout << e << " "; // 1 2 3 4
    cout << endl;

    lt.clear();
    cout << "clear 后 size：" << lt.size() << endl; // 0
}

int main() {
    test_list4();
    return 0;
}

跑通这几个用例，基本功能就算验证完了。

从头到尾写一遍 List，对哨兵节点的妙用、指针操作如何保证 O(1)、迭代器失效的边界，都会比光看文档深刻得多。以后再用 std::list，遇到奇怪的问题，至少知道该往哪个方向排查。