C++ STL list实现原理与双向链表详解

1. 什么是list

在C++标准模板库(STL)中，list是一个双向链表容器。与vector这种连续存储的容器不同，list通过指针将分散的节点连接起来，每个节点包含数据域和两个指针域：一个指向前驱节点，一个指向后继节点。

list的核心特性包括：

• 动态内存分配：每个节点独立分配内存
• 非连续存储：节点在内存中分散分布
• 双向遍历：支持从前向后和从后向前遍历
• 常数时间插入删除：在任意位置插入删除元素都是O(1)时间复杂度

list的常用操作接口：

cpp复制// 插入操作
push_front(const T& value);  // 头部插入
push_back(const T& value);   // 尾部插入
insert(iterator pos, const T& value);  // 指定位置插入

// 删除操作
pop_front();  // 删除头部元素
pop_back();   // 删除尾部元素
erase(iterator pos);  // 删除指定位置元素

与vector的对比：

1. 内存布局：

   • vector：连续内存块
   • list：分散的内存节点

2. 访问效率：

   • vector：支持随机访问(O(1))
   • list：仅支持顺序访问(O(n))

3. 插入删除：

   • vector：中间插入删除需要移动元素(O(n))
   • list：任意位置插入删除都是O(1)

提示：选择容器时，如果需要频繁随机访问，优先考虑vector；如果需要频繁在中间位置插入删除，list更合适。

2. list类的模拟实现

2.1 节点的基本结构

list的核心是节点结构，我们使用模板类实现：

cpp复制template<class T>
struct ListNode {
    ListNode(const T& data = T())
        : data(data)
        , prev(nullptr)
        , next(nullptr) 
    {}
    
    T data;
    ListNode<T>* prev;
    ListNode<T>* next;
};

关键设计点：

1. 使用struct而非class，使成员默认公有
2. 包含数据域和两个指针域
3. 提供默认构造函数，方便创建头节点
4. 模板参数T支持任意数据类型

注意：这里使用struct是为了简化访问控制，实际项目中根据需求可以选择class并明确指定public成员。

2.2 迭代器的封装

迭代器是STL设计的精髓所在，它抽象了容器元素的访问方式。list迭代器的核心是封装节点指针，并重载相关运算符：

cpp复制template <class T, class Ref, class Ptr>
struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;
    
    Node* node;  // 封装的节点指针
    
    // 构造函数
    ListIterator(Node* n = nullptr) : node(n) {}
    
    // 解引用操作符
    Ref operator*() const { 
        return