C++ : list 源码级深度拆解——双向循环链表的优雅与代价

在 STL 顺序容器三巨头中，list 是最“纯粹”的链式结构代表：vector 主打连续内存的极致访问效率，deque 主打双端操作的折中平衡，list 则把任意位置插删的能力拉满，代价是彻底放弃随机访问与缓存友好性。

它的底层是经典的双向循环链表，实现看似简单，实则藏着大量 STL 的设计巧思——比如哨兵节点、分层节点结构、专属成员算法等。本文基于 GCC libstdc++ 源码，从内存布局、迭代器实现、核心操作到性能权衡，一层层扒透 list 的底层。

一、整体架构：双向循环链表 + 哨兵节点

list 的核心设计只有两个要点：用双向链表保证任意位置 O(1) 插删，用哨兵节点统一边界处理，消除空链表、头尾节点的分支判断。

1.1 节点的分层设计

STL 没有把数据和指针塞在同一个结构体里直接用，而是做了基类+派生类的分层设计，把链表结构和数据解耦。

底层基类：只负责链表结构

struct _List_node_base {
_List_node_base* _M_next; // 后继指针
_List_node_base* _M_prev; // 前驱指针
};

这个基类只存两个指针，和元素类型完全无关，所有链表通用操作（节点移动、拼接、反转）都可以基于基类指针实现，不用关心数据类型，大幅减少代码冗余。

派生类：负责承载数据

template <typename _Tp>
struct _List_node : public _List_node_base {
_Tp _M_data; // 实际存储的元素数据
};

继承基类的指针能力，再加上数据成员，就是一个完整的链表节点。

1.2 哨兵节点：消除边界判断的神来之笔

list 容器本身只持有一个指针——指向哨兵节点（Sentinel Node）的 _M_node。哨兵是一个不存有效数据的虚拟节点，用来把链表首尾连起来形成闭环。

• 空链表状态：哨兵的 _M_next 和 _M_prev 都指向自己
• 有元素状态：
  • 哨兵->_M_next → 第一个元素节点（对应 begin()）
  • 哨兵->_M_prev → 最后一个元素节点（对应 –end()）
  • 最后一个节点的 _M_next → 哨兵
  • 第一个节点的 _M_prev → 哨兵

这个设计的好处非常直观：

• 插入、删除操作不需要特判“空链表”“头节点”“尾节点”等边界情况，所有位置的操作逻辑完全一致
• end() 迭代器直接指向哨兵，天然就是“最后一个元素的下一个位置”，语义完美匹配

1.3 容器的核心数据成员

list 的数据成员极简，全部定义在基类 _List_base 中：

template <typename _Tp, typename _Alloc>
class _List_base {
protected:
_List_node_base* _M_node; // 指向哨兵节点的唯一指针
size_t _M_size; // 元素总数，C++11 后加入
// … 分配器相关成员
};

这里有一个经典面试考点：

C++11 之前，list 的 size() 是 O(n) 时间复杂度。早期实现没有 _M_size 成员，调用 size() 时会遍历整个链表计数。C++11 标准强制要求所有容器的 size() 为常数时间，libstdc++ 才加入了 _M_size 成员，每次插入删除都同步维护计数。

二、灵魂部件：双向迭代器的实现

list 不支持随机访问，它的迭代器是双向迭代器（Bidirectional Iterator），只能前后逐个移动，不能跳跃。

2.1 迭代器的数据结构

迭代器本身非常轻量，内部只有一个指针：

template <typename _Tp>
struct _List_iterator {
_List_node_base* _M_node; // 指向当前节点的基类指针
// … 类型定义
};

用基类指针而不是派生类指针的原因很简单：迭代器只需要操作 prev/next 指针，不需要关心数据类型，const 迭代器也可以复用这套结构。

2.2 核心运算符重载

迭代器的所有操作本质都是在操作内部的节点指针。

1. 解引用与成员访问

_Tp& operator*() const {
// 向下转型为数据节点，取数据
return static_cast<_List_node<_Tp>*>(_M_node)->_M_data;
}

_Tp* operator->() const {
return &(operator*());
}

2. 前后移动

// 前置++
_List_iterator& operator++() {
_M_node = _M_node->_M_next;
return *this;
}

// 前置–
_List_iterator& operator—() {
_M_node = _M_node->_M_prev;
return *this;
}

没有任何计算，纯指针跳转，单步操作是 O(1)，但要走到第 n 个位置就必须一步一步跳，整体 O(n)。

2.3 迭代器的能力边界

它属于双向迭代器，只支持 ++、–，不支持 +=、-=、[] 等随机访问操作。这也是为什么 std::sort 不能直接作用于 list——标准排序算法要求随机访问迭代器来支撑分治、索引跳跃。

也正因为这个限制，list 不得不自己实现了一套专属的成员算法，后面会详细讲。

三、核心操作的源码级流程

3.1 插入操作：O(1) 的本质是改两个指针

所有插入操作（push_back、push_front、insert）最终都会调用底层的 _M_insert 函数，逻辑完全统一，不需要区分头尾和中间位置。

// 在 position 指向的节点之前插入新节点
iterator _M_insert(iterator __position, const _Tp& __x) {
_List_node<_Tp>* __new_node = _M_create_node(__x); // 分配新节点

// 四步指针操作，完成插入
__new_node->_M_next = __position._M_node; // 新节点后继 = 目标节点
__new_node->_M_prev = __position._M_node->_M_prev; // 新节点前驱 = 目标节点的前驱
__position._M_node->_M_prev->_M_next = __new_node; // 前驱节点的后继 = 新节点
__position._M_node->_M_prev = __new_node; // 目标节点的前驱 = 新节点

++_M_size; // 维护计数
return iterator(__new_node);
}

四步指针操作，和位置完全无关——插在头、插在尾、插在中间，代码一模一样，这就是哨兵节点带来的好处。

关键特性：插入操作不会导致任何已有迭代器、引用、指针失效。所有已有节点的内存地址都没有变化，只是指针指向变了。

3.2 删除操作：只让被删节点失效

删除操作和插入对称，只需要修改前后节点的指针，然后释放目标节点。

iterator _M_erase(iterator __position) {
_List_node_base* __next_node = __position._M_node->_M_next;
_List_node_base* __prev_node = __position._M_node->_M_prev;

// 前后节点直接互连，跳过被删节点
__prev_node->_M_next = __next_node;
__next_node->_M_prev = __prev_node;

_M_destroy_node(static_cast<_List_node<_Tp>*>(__position._M_node)); // 释放节点
—_M_size;
return iterator(__next_node);
}

迭代器失效规则：只有被删除的那个节点的迭代器、引用、指针会失效，其余所有节点全部不受影响。这是所有 STL 容器里迭代器稳定性最强的表现。

3.3 独门绝技：splice 链表拼接

splice 是 list 独有的操作，也是链表结构的价值天花板——它可以把另一个 list 的节点直接“剪”过来，零拷贝、零元素构造析构，纯指针操作。

它有三种常用重载：

时间复杂度的细节

• 整个链表转移、单个节点转移：O(1)，只改指针，直接复用 other 的总大小更新计数
• 区间转移：O(k)（k 为区间元素个数），因为需要遍历区间统计元素个数来更新 _M_size
• 注：C++11 之前没有 _M_size，所有 splice 都是纯 O(1)

splice 的典型应用场景是 LRU 缓存：把刚访问的节点从链表中间移到表头，全程不需要拷贝数据，性能极高。

3.4 专属成员算法：为什么不直接用 STL 通用算法

list 自带 sort、merge、reverse、unique、remove 等成员函数，不是重复造轮子，而是通用算法要么用不了，要么效率太低。

其中 list::sort 的实现非常精巧：它维护一个长度固定的指针数组，每个位置对应一条长度为 2^i 的有序子链表，逐个把节点合并进对应层级，最终拼接出完整有序链表，全程不需要额外数组空间。

四、内存特性与性能真相

4.1 内存开销：小元素场景极其浪费

每个 list 节点除了数据本身，还要携带两个指针：

• 64 位系统下，两个指针共 16 字节
• 如果存 int（4 字节），额外开销高达 300%，内存利用率只有 20%
• 如果存大对象（比如几百字节的结构体），指针开销可以忽略

同时，节点是逐个分配在堆上的，没有预分配、没有容量概念，用一个分配一个，不存在扩容抖动，但也带来了内存碎片问题。

4.2 缓存友好性：几乎为零

这是 list 最致命的性能短板。现代 CPU 依赖缓存预取来加速连续内存访问，而 list 的节点散落在堆内存的各个位置，地址毫无连续性。

遍历 list 时，每访问一个节点都大概率触发一次缓存未命中（Cache Miss），需要从主存读取数据，耗时是缓存访问的几十上百倍。很多人直觉上“链表插删快”，但实际场景中，找到插入位置的遍历开销，早已抵消了插删的 O(1) 优势。

这也是业界共识：默认优先用 vector，除非你能实测证明 list 更快。

4.3 迭代器失效规则总结

这是所有 STL 容器中迭代器稳定性最高的，也是很多场景选择 list 的核心理由——你可以放心地持有某个元素的指针或引用，不用担心其他节点增删导致它失效。

五、设计权衡与选型建议

5.1 list 的核心优势

5.2 list 的核心劣势

5.3 选型原则

• 90% 的常规场景，优先选 vector
• 频繁双端操作、不需要随机访问，选 deque
• 只有满足以下条件时，才考虑 list：
• 频繁在中间位置插入删除
• 可以快速拿到插入位置的迭代器（比如配合哈希表索引）
• 需要保证元素地址/引用长期稳定，不能因增删失效
• 需要频繁进行节点拼接、转移操作