2.6、list的底层原理和常用函数

底层数据结构

• • 双向循环链表实现：
  std::list底层采用双向循环链表，每个节点包含三个部分：
  • • 数据元素（存储用户数据）；
  • • 前驱指针（prev）：指向前一个节点；
  • • 后继指针（next）：指向后一个节点。
• • 内存分布特性：
  节点在内存中非连续分布，通过指针形成逻辑上的序列，插入/删除操作仅需修改指针指向，无需移动元素，时间复杂度为 O(1)（已定位节点时）。

迭代器设计与特性

• • 迭代器本质：
  迭代器内部封装了一个指向链表节点的指针，通过重载以下运算符实现链表遍历：
  • • *：解引用获取节点数据；
  • • ++：移动到后继节点（operator++()）；
  • • --：移动到前驱节点（operator--()）；
  • • ==/!=：判断迭代器是否指向同一节点。
• • 关键限制：
  • • 不支持随机访问（无法通过下标operator[]或跳跃式操作直接定位元素）；
  • • 遍历效率：访问第n个元素需顺序移动n次迭代器，时间复杂度为 O(n)。

核心优势与适用场景

优势：

1. 1. 高效的插入/删除操作：
   • • 任意位置插入/删除只需修改指针，无需移动后续元素，尤其适合频繁在序列中间修改数据的场景（如任务队列动态增删任务）。
2. 2. 迭代器稳定性：
   • • 插入/删除操作仅使当前节点的迭代器失效，其他迭代器保持有效（vector扩容时所有迭代器失效）。

适用场景：

• • 高频中间操作：如链表式数据结构（undo/redo系统、多项式表达式动态修改）；
• • 无需随机访问：仅需顺序遍历的场景（如日志流式处理）；
• • 元素大小不确定：避免连续容器（vector/deque）的扩容开销。

常用操作的底层实现

总结

std::list的设计核心是以双向链表为基础，通过迭代器封装指针操作，换取高效的动态修改能力。其核心特点可概括为：

• • 数据结构：双向循环链表，内存非连续，节点通过指针连接；
• • 操作效率：插入/删除 O(1)（已定位），访问 O(n)；
• • 适用边界：适合“高频中间修改+低频随机访问”场景，如事件队列、动态链表算法。
  本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
  （加入我的知识星球，免费获取账号，解锁所有文章。）