话说 C++ 里的 List，本质上就是一个带头节点的双向循环链表，听着是不是有点绕？

很多朋友刚开始学List的时候，搞不懂它和vector的区别...大家请看这张图

图：带头节点的双向循环链表，头节点像个小队长，两边都指向自己

想象一下：

• List就像幼儿园里手拉手的小朋友们，每个小朋友（节点）都牵着前一个和后一个的手，这样就形成了一条长长的队伍。想加个新朋友？只要让旁边的两个小朋友松开手，拉上新朋友再重新牵上就行！
• vector更像军训时的方阵，大家排得整整齐齐，每个人都有自己固定的位置编号。想插个队？后面的所有人都要集体往后挪一步！

List这种结构的核心优势就是：插入删除超方便！ 就像队伍中加人，只要让前后的小朋友松开手再重新牵上就行，不用像vector那样整个队伍都要移动位置～

Part1List基本概念

（1）功能定位

将数据进行链式存储，不像vector那样"住在一起"，而是"各住各家"，通过"电话线"（指针）联系！

（2）链表本质

list是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。就像你家的连锁店，每家店地理位置不挨着，但都通过内部系统连成一个整体！

（3）链表组成

链表由一系列结点（节点）组成，每个节点都是独立个体！

（4）节点结构

一部分是存数据的，叫数据域，就像小朋友兜里揣的糖果；另一部分是存下一个结点地址的，叫指针域，相当于小朋友知道下一个人在哪。

（5）STL中的特殊设计

STL中的list是一个双向循环链表，不仅每个节点知道下一个是谁，还知道上一个是谁，并且首尾相连形成闭环！

（6）迭代器特性

由于存储方式不连续，list中的迭代器只支持前移和后移，属于双向迭代器。这就像你只能沿着链子一个方向一个方向走，不能直接跳到任意位置！

（7）内存方面

list采用动态存储分配，不会造成内存浪费和溢出。执行插入和删除操作只需修改指针即可，不需要移动大量元素。这就像租房，想加人就加间房，不用所有人挤一挤！

（8）缺点也得说说

灵活是灵活，但指针域占空间，遍历起来也费时间，这就跟带了一堆行李出门，方便是方便，就是沉了点。

（9）重要性质

插入和删除操作不会让原来的迭代器失效，这点 Vector 可做不到，Vector 动一下，迭代器可能就废了。

专注Linux C/C++技术讲解~

Part2框架搭建

现在我们开始实现list容器，首先要思考一下框架结构：

1. 节点结构体：（类似源码中的节点）——链表的"砖块"
2. list类：要带一个头结点，让我们更方便进行插入删除操作——链表的"地基"
3. 迭代器类——让我们能用++/--优雅遍历的"魔法棒"

基本就是这样，现在我们开始手搓！

2.1、节点类：链表的DNA

// 节点 结构体
template<class T>
struct ListNode
{
    ListNode* _next;  // 指向下一个节点的指针
    ListNode* _prev;  // 指向前一个节点的指针
    T _data;          // 节点存储的数据


    // 构造函数使用初始化列表（推荐但非必须）
    ListNode(T x = T()) :
        _next(nullptr),
        _prev(nullptr),
        _data(x)
    {}


    /* 
    // 等效的构造函数写法（不使用初始化列表）
    ListNode(T x = T()) 
    {
        _next = nullptr;
        _prev = nullptr;
        _data = x;
    }    
    */


    // 析构函数：避免野指针出现，将指针赋值为nullptr就可以了
    ~ListNode()
    {
        _next = nullptr;
        _prev = nullptr;
    }
};

代码解析：

• 使用模板来适配更多数据类型，这才是STL的通用做法！
• 每个节点包含三个核心成员：_next、_prev和_data
• 提供了构造函数（使用初始化列表是推荐做法，但不是必须的）
• 析构函数虽然简单，但能有效避免野指针问题

思考：构造函数使用初始化列表是必须的吗？

答：不是必须的，但推荐使用！初始化列表更高效，特别是对于类类型成员。

2.2、list类：双向循环链表的"骨架"

template<class T>
class list
{
public:
    // 设置适配的节点类型别名（方便后续使用）
    typedef ListNode<T> Node;


    // 空初始化：创建头节点并形成循环
    void empty_init()
    {
        _head = new Node;           // 创建头节点（哨兵节点）
        _head->_next = _head;       // 头节点的next指向自己
        _head->_prev = _head;       // 头节点的prev也指向自己
        _size = 0;                  // 初始大小为0
    }


    // 构造函数
    list() : _head(nullptr)
    {
        empty_init();               // 调用初始化函数
    }


private:
    Node* _head;    // 头指针（实际上是哨兵节点）
    size_t _size;   // 链表大小
};

为什么要有哨兵节点？因为它让"空链表"和"非空链表"的操作逻辑完全一致，无需特殊处理头尾边界！

2.3、迭代器类：让链表也能优雅遍历

这才是最精华的部分！我们思考一下：这里能不能使用原生指针来完成迭代器的操作（++、--、==、!=）？

答案当然是不能！

因为链表的物理地址并不是连续的，对原生指针的++或--操作是没有意义的！所以我们需要自行编写迭代器类，对原生指针进行封装，来满足我们特殊的++和--操作！

基础迭代器实现

// 这里的模板可以再次升级  先简单写一下
template<class T>
class ListIterator 
{
public:
    // 重命名方便书写（类型别名是C++的优良传统）
    typedef ListNode<T> Node;
    typedef ListIterator<T> Self;


    Node* _node;  // 指向当前节点的指针


    // 构造函数
    ListIterator(Node* x) : _node(x) {}


    // 前置++ ( ++it )
    Self& operator++()    // 注意返回引用，支持连续操作如++++it
    {
        _node = _node->_next;  // 移动到下一个节点
        return *this;          // 返回当前迭代器引用
    }


    // 后置++ ( it++ )
    Self operator++(int)     // int参数仅用于区分前置和后置
    {
        Self tmp(*this);       // 保存当前状态（浅拷贝即可）
        _node = _node->_next;  // 移动到下一个节点
        return tmp;            // 返回移动前的状态
    }


    // 前置-- ( --it )
    Self& operator--()
    {
        _node = _node->_prev;  // 移动到前一个节点
        return *this;
    }


    // 后置-- ( it-- )
    Self operator--(int)
    {
        Self tmp(*this);       // 保存当前状态
        _node = _node->_prev;  // 移动到前一个节点
        return tmp;
    }


    // 判断是否相等（比较指针地址是否相同）
    bool operator!=(const Self& it) const  // 加上const更规范
    {
        return _node != it._node;
    }


    // 判断是否相等
    bool operator==(const Self& it) const
    {
        return _node == it._node;
    }


    // 解引用操作（*it）返回节点数据的引用（可以进行修改）
    T& operator*() 
    {
        return  _node->_data;
    }


    // ->操作符重载（因为指针才能使用->，所以要返回地址/指针）
    T* operator->()  // 编译器会进行省略->
    {
        return &_node->_data;
    }
};

解析：

• ++it / it++：让迭代器指向下一个节点（不再是内存地址+1！）
• --it / it--：让迭代器指向前一个节点
• it：解引用获取当前节点的数据（返回引用，支持修改）
• it->：访问当前节点数据的成员（编译器会自动处理）
• == / !=：比较两个迭代器是否指向同一个节点

关键点：前置++返回引用，后置++返回临时对象！这是C++迭代器的标准做法！

一般我们的迭代器应该还要支持const，不然我们传入一个不可修改的链表（const list）时，就会发生报错！那么我们还要书写一份const版的迭代器。如果每样都写一遍，那大部分代码都重复了（++、--、==、!=都是一样的），只有operator*()和operator->()返回值不一致：

• 普通迭代器：可以修改数据，返回 T& 和 T*
• const迭代器：数据只读，返回 const T& 和 const T*

那这样就发现了痛点：不同迭代器大部分代码相同，只有返回值类型不同！

解决方案：使用模板参数技巧，让编译器帮我们处理类型差异！

// 升级版迭代器模板（三个参数：数据类型、引用类型、指针类型）
template<class T, class Ref, class Ptr>
class ListIterator 
{
public:
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;


    Node* _node;


    ListIterator(Node* x) : _node(x) {}


    // 移动操作（++/--）保持不变
    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) const { return _node != it._node; }
    bool operator==(const Self& it) const { return _node == it._node; }


    // 关键点：使用模板参数Ref和Ptr来处理返回值类型差异
    Ref operator*() { return  _node->_data; }
    Ptr operator->() { return &_node->_data; }
};

使用方式：

// 在list类中定义迭代器类型别名
typedef ListIterator<T, T&, T*> iterator;            // 普通迭代器
typedef ListIterator<T, const T&, const T*> const_iterator;  // const迭代器

到此，我们实现了STL风格链表的三大核心组件：节点存储结构、容器主体框架、安全遍历机制，是不是很简单？

Part3功能实现

咱接着来接着说 list 容器的各种功能咋实现

3.1、begin() 与 end()：迭代器的起点与终点

迭代器的起始和结束位置得整明白。begin () 就是头结点的下一个，end () 直接就是头结点本身。

为啥呢？因为遍历的时候，一圈下来最后就回到头结点了，所以判断是不是头结点就能知道该不该停。

// 普通迭代器
typedef ListIterator<T, T&, T*> iterator;
// 常迭代器
typedef ListIterator<T, const T&, const T*> const_iterator;
iterator begin() { return _head->_next; }
iterator end() { return _head; }
const_iterator begin() const { return _head->_next; }
const_iterator end() const { return _head; }

代码解析：

• begin()：返回指向第一个实际数据节点的迭代器（即头节点的下一个节点）
• end()：返回指向哨兵节点（头节点）的迭代器，这就是遍历的终点！
• 为什么end()是头节点？因为我们的链表是双向循环的，遍历完最后一个节点后，它的next就是头节点！
• const重载：为const list对象提供只读访问能力

核心思想：利用哨兵节点作为统一的"终点标志"，让空链表和非空链表的遍历逻辑完全一致！空链表时，begin()也等于end()（都指向头节点）

3.2、插入操作：在链表中安插新节点

尾插操作 push_back()

void push_back(const T& x = T())
{
    // 1. 创建新节点
    Node* node = new Node(x);


    // 2. 找尾（头节点的前一个就是尾节点）
    Node* tail = _head->_prev;


    // 3. 进行插入操作（修改四个指针）
    node->_next = _head;     // 新节点的next指向头节点
    node->_prev = tail;      // 新节点的prev指向原尾节点


    tail->_next = node;      // 原尾节点的next指向新节点
    _head->_prev = node;     // 头节点的prev也指向新节点


    // 4. 更新大小
    _size++;
}

插入逻辑可视化：

原尾节点(tail)        新节点(node)         头节点(_head)
    |                   |                   |
    |                   |                   |
    V                   V                   V
[prev] ---> [next]    [prev] ---> [next]    [prev] ---> [next]
    ^                   ^                   ^
    |                   |                   |
    |                   |                   |
 原尾节点的前驱      原尾节点            新节点的后续

任意位置插入 insert()

void insert(iterator pos = begin(), T x = T())
{
    // 1. 创建新节点
    Node* node = new Node(x);


    // 2. 找到插入位置的前后节点
    Node* prev = pos._node->_prev;  // pos前一个节点
    Node* next = pos._node;         // pos节点本身


    // 3. 处理新节点的指针
    node->_prev = prev;    // 新节点前驱指向pos前一个节点
    node->_next = next;    // 新节点后继指向pos节点


    // 4. 处理前后节点的指针
    prev->_next = node;    // pos前一个节点的后继指向新节点
    next->_prev = node;    // pos节点的前驱指向新节点


    // 5. 更新大小
    _size++;
}

核心思想：通过调整四个指针完成插入，不需要移动任何已有元素

头插操作 push_front()：优雅复用

void push_front(const T& x = T())
{
    insert(begin(), x);  // 直接复用insert接口，在begin()位置插入
}

头插其实就是"在第一个位置插入"，完全可以用insert(begin(), x)实现，避免重复代码！

3.3、删除操作：从链表中移除节点

尾删操作 pop_back()

void pop_back()
{
    // 1. 找到尾节点（头节点的前一个）
    Node* tail = _head->_prev;
    // 2. 找到尾节点的前一个节点（新的尾节点）
    Node* prev = tail->_prev;


    // 3. 调整指针：绕过tail节点
    prev->_next = _head;    // 新尾节点的next指向头节点
    _head->_prev = prev;    // 头节点的prev指向新尾节点


    // 4. 释放内存（重要！避免内存泄漏）
    delete tail;


    // 5. 更新大小
    _size--;
}

头删操作 pop_front()

void pop_front()
{
    // 1. 找到头节点的下一个（第一个实际节点）
    Node* head = _head->_next;
    // 2. 找到第二个节点（新的头节点）
    Node* next = head->_next;


    // 3. 调整指针：绕过head节点
    _head->_next = next;    // 头节点的next指向第二个节点
    next->_prev = _head;    // 第二个节点的prev指向头节点


    // 4. 释放内存
    delete head;


    // 5. 更新大小
    _size--;
}

任意位置删除 erase()：返回下一个有效迭代器

iterator erase(iterator pos)
{
    // 1. 获取要删除的节点及其前后节点
    Node* cur = pos._node;    // 当前要删除的节点
    Node* prev = cur->_prev;  // 当前节点的前一个节点
    Node* next = cur->_next;  // 当前节点的后一个节点


    // 2. 调整指针：绕过cur节点
    prev->_next = next;    // 前一个节点的next指向后一个节点
    next->_prev = prev;    // 后一个节点的prev指向前一个节点


    // 3. 释放内存
    delete cur;


    // 4. 更新大小
    _size--;


    // 5. 返回下一个节点的迭代器（重要！）
    return iterator(next);
}

关键要点：

• 内存管理：一定要记得delete删除的节点，否则内存泄漏！
• 迭代器失效处理：返回被删除节点的下一个节点的迭代器，这是STL的标准做法，让用户可以继续安全遍历
• 边界安全：即使是删除最后一个节点，也能正确处理（next此时就是头节点）

3.4、拷贝构造：深度复制链表数据

list(const list<T>& l)
{
    empty_init();  // 先初始化一个空链表（创建哨兵节点）


    // 遍历原链表，逐个插入数据
    iterator it = l.begin();
    while (it != l.end())
    {
        push_back(*it);  // 复制数据到新链表
        it++;
    }
}

如果追求更高性能，可以实现移动构造函数，避免不必要的数据拷贝！

3.5、析构函数：清理所有资源

void clear()
{
    // 依次释放所有数据节点
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);  // erase会返回下一个有效迭代器
    }
}


~list()
{
    clear();      // 先清除所有数据节点
    // 单独释放头结点空间
    delete _head; 
    _head = nullptr;  // 避免野指针
}

3.6、其他实用功能

返回链表大小

size_t size() const { return _size; }

维护一个_size成员变量，让获取大小的操作是O(1)时间复杂度，而不是遍历计算！

判断链表是否为空

bool empty()
{
    return _size == 0;  // 直接检查_size是最可靠的方式
}

虽然也可以通过判断begin() == end()来判断是否为空，但直接检查_size更直观高效！

清空链表数据

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);  // 循环删除所有数据节点
    }
}

复用性： 与析构函数中的clear()复用，保持代码一致性！

3.7、赋值运算符重载：支持深拷贝与移动语义

在C++中，如果你不显式定义赋值运算符，编译器会生成一个默认的版本，但对于管理资源的类（如我们的list），默认的赋值运算符只是简单地按成员拷贝指针，这会导致多个对象共享同一块内存，最终可能引发双重释放的严重问题！

拷贝赋值运算符（深拷贝版本）

// 拷贝赋值运算符（传统写法：先拷贝后交换）
list<T>& operator=(const list<T>& other)
{
    // 1. 防止自赋值（非常重要！）
    if (this != &other)
    {
        // 2. 先清空当前链表
        clear();
        // 3. 再深拷贝other链表的数据
        iterator it = other.begin();
        while (it != other.end())
        {
            push_back(*it);  // 逐个添加元素
            it++;
        }
    }
    // 4. 返回当前对象的引用以支持链式赋值
    return *this;
}

移动赋值运算符（C++11 引入的高效版本）

// 移动赋值运算符（C++11 移动语义）
list<T>& operator=(list<T>&& other) noexcept
{
    // 1. 防止自赋值
    if (this != &other)
    {
        // 2. 先清理当前链表的资源
        clear();


        // 3. 直接"窃取"other的资源（高效转移所有权）
        _head = other._head;
        _size = other._size;


        // 4. 将other置于有效但空的状态（符合移动语义约定）
        other._head = nullptr;
        other._size = 0;
    }
    return *this;
}

3.8、迭代器失效处理

迭代器失效是一个重要但容易被忽视的。对于list来说，由于其非连续内存布局的特性，大部分操作不会使所有迭代器失效，但也有特殊情况需要注意！

在我们前面的实现中，除了被删除节点的迭代器外，其他迭代器在插入和删除操作后仍然有效！这是list相比vector的一大优势！

特别注意：当调用 erase(iterator pos) 时，被删除节点的迭代器pos会失效，但函数返回的是下一个有效节点的迭代器，这正是STL的标准做法！

// 我们之前的erase实现已经考虑了这一点
iterator erase(iterator pos)
{
    // ... [指针调整和内存释放代码同前] ...


    // 关键点：返回下一个节点的迭代器，保证迭代器连续性
    return iterator(next);  // 用户可以安全地继续使用返回的迭代器
}

最佳实践建议（给list使用者的建议）

// 典型安全使用模式：
iterator it = myList.begin();
while (it != myList.end())
{
    if (需要删除当前元素的条件)
    {
        // erase会返回下一个有效迭代器，直接赋值给it即可
        it = myList.erase(it);  //  安全！
    }
    else
    {
        // 只是不删除时才递增迭代器
        ++it;  //  安全！
    }
}

3.9、添加更多STL兼容接口

为了让我们的手搓list更像STL原版，我们可以添加一些常用的STL兼容接口！

在指定位置前插入元素（insert的另一种形式）

// 在指定迭代器位置前插入元素（与现有insert保持一致的语义）
// 我们的现有insert实际上是在pos位置前插入（STL标准做法）
// 所以此函数可以作为别名或明确文档说明
iterator insert_before(iterator pos, const T& x)
{
    return insert(pos, x);  // 复用现有实现
}

在链表尾部插入元素（push_back的另一种形式）

// 尾部插入的另一种表示（与push_back完全一样，仅为接口丰富性）
void emplace_back(const T& x)
{
    push_back(x);  // 当前简单实现，后续可扩展为原地构造
}

在链表头部插入元素（push_front的另一种形式）

// 头部插入的另一种表示（与push_front完全一样，仅为接口丰富性）
void emplace_front(const T& x)
{
    push_front(x);  // 当前简单实现，后续可扩展为原地构造
}

查找元素（便利功能，非STL标准但实用）

// 查找元素（线性搜索，返回第一个匹配元素的迭代器）
iterator find(const T& x)
{
    iterator it = begin();
    while (it != end())
    {
        if (*it == x)  // 假设T类型支持==操作符
        {
            return it;
        }
        ++it;
    }
    return end();  // 未找到返回end()
}

理解底层原理比单纯使用API更重要，当你自己实现过list，以后用STL的list就会更加得心应手！