C++ list 模拟实现：带头双向链表的增删查改

2. 实现思路

利用模板参数区分返回值类型。

template <class T>
struct ListIterator {
    typedef ListNode<T> NodeType;
    typedef ListIterator<T> Self;
    
    NodeType* _node;
    
    // 构造函数
    ListIterator(NodeType* node) : _node(node) {}
    
    // 解引用
    T& operator*() const { return _node->_data; }
    T* operator->() const { return &_node->_data; }
    
    // 前置自增
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }
    
    // 后置自增
    Self operator++(int) {
        Self tmp = *this;
        _node = _node->_next;
        return tmp;
    }
    
    // 相等比较
    bool operator==(const Self& rhs) const { return _node == rhs._node; }
    bool operator!=(const Self& rhs) const { return _node != rhs._node; }
};

注意：迭代器本身不需要析构函数，它只是持有节点指针，不负责释放节点内存。

三、基本接口实现

1. 构造与析构

构造函数初始化哨兵节点，析构函数清除所有节点并销毁哨兵。

List() {
    _head = new ListNode<T>();
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
}

~List() {
    clear();
    delete _head;
}

这里复用了 clear 函数来释放中间节点，最后单独删除哨兵位。

2. 拷贝构造与赋值

需要深拷贝。先创建新的哨兵节点，再逐个插入数据。

List(const List& lt) {
    _head = new ListNode<T>();
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
    
    auto it = lt.begin();
    while(it != lt.end()) {
        push_back(*it);
        ++it;
    }
}

赋值运算符重载推荐使用'交换法'（Copy-and-Swap）：传值构造临时对象，然后交换成员变量。这样既安全又高效。

3. 插入与删除

任意位置插入

依据插入位置 pos，将新节点插入到 pos 之前。

iterator insert(iterator pos, const T& x) {
    ListNode<T>* nextNode = pos._node->_next;
    ListNode<T>* newNode = new ListNode<T>(x);
    
    pos._node->_next = newNode;
    newNode->_prev = pos._node;
    newNode->_next = nextNode;
    nextNode->_prev = newNode;
    
    ++_size;
    return iterator(newNode);
}

关键点：修改指针顺序时，务必保存好被覆盖的指针，防止断链。

任意位置删除

删除 pos 指向的节点，并返回下一个有效位置的迭代器。

iterator erase(iterator pos) {
    assert(pos._node != _head); // 哨兵位不可删除
    
    ListNode<T>* prevNode = pos._node->_prev;
    ListNode<T>* nextNode = pos._node->_next;
    
    prevNode->_next = nextNode;
    nextNode->_prev = prevNode;
    
    delete pos._node;
    --_size;
    
    return iterator(nextNode);
}

注意：删除后原迭代器失效，必须返回新位置。

四、完善与优化

1. 自定义类型访问

对于自定义类型，若未重载 << 运算符，直接打印会报错。可以通过重载 operator-> 来简化成员访问。

// 编译器会将 it->_a1 转换为 (*it).operator->()->_a1
cout << it->_a1 << endl; 

2. 泛型打印

利用模板泛型编程，编写通用的容器打印函数。

template <typename Container>
void print_container(const Container& con) {
    typename Container::const_iterator it = con.begin();
    while(it != con.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

注意：在模板中访问嵌套类型时，需加 typename 关键字告知编译器这是一个类型而非静态成员。

五、总结

list 的模拟实现涵盖了动态内存管理、指针操作、迭代器封装及异常安全等核心知识点。掌握这些细节，能帮助你更好地理解 STL 容器的设计哲学。实际开发中，若数据量大且频繁在中间插入删除，list 是比 vector 更优的选择。