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

前言

相比于 string 和 vector，list 的实现逻辑更为复杂。它没有重载 [] 运算符，也不提供 reserve 扩容接口，但增加了 merge、unique、sort 等特有功能。其核心差异在于迭代器的实现方式。

1. 与 vector/string 的区别

无 [] 接口：底层非连续存储，随机访问效率低，依赖迭代器。
无 reserve 接口：每次插入一个节点，无需预分配大块内存。
特有接口：如 merge（归并）、unique（去重）、sort（排序）。注意 sort 底层使用归并排序，因 list 迭代器不支持减法运算，无法直接使用算法库中的通用排序。
迭代器不同：vector 和 string 使用原生指针作为迭代器，而 list 必须对迭代器进行包装，重载运算符以满足解引用和自增的核心功能。

一、底层结构与节点构造

list 采用带头双向链表结构。每个节点包含数据域、前驱指针和后继指针。

文章配图

节点定义：

template <class T>
struct ListNode {
    T _data;
    ListNode<T>* _prev;
    ListNode<T>* _next;
    
    // 构造函数
    ListNode(const T& x = T()) : _data(x), _prev(nullptr), _next(nullptr) {}
};

使用 struct 而非 class 是因为成员默认公有，便于在友元函数中直接访问，减少繁琐的 getter/setter。

哨兵位节点： list 内部维护一个头尾相连的哨兵节点（Sentinel），不存储有效数据。这使得头插、尾插、删除首尾元素的操作逻辑统一，无需特殊判断空表情况。

二、迭代器封装

由于 list 节点不连续，不能直接用裸指针遍历。我们需要封装一个迭代器类。

1. 迭代器分类

迭代器分为普通迭代器和常量迭代器。主要区别在于解引用后返回值的类型是否可写。

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 更优的选择。