list这两个字，几乎所有写代码的人都用过。但真要说清楚它是什么、底层怎么实现的，能讲明白的人不算多。很多初学者把list当成一个“能装东西的盒子”就完事了，等到面试被问一句“Python的list和C++的list有什么区别”，或者排查线上问题时发现往列表头插数据居然这么慢，才意识到自己对这个最常用的数据结构其实并不了解。
这篇文章我想把list从抽象概念到底层实现完整梳理一遍，重点拆解两大主流实现方式——动态数组和链表——帮你建立一张清晰的认知地图。无论你是刚入门的新手，还是写了两三年代码想补基础的老手，这篇文章都能给你一些值得沉淀的东西。
1. 先把“list是什么”这个问题回答清楚
1.1 从生活场景理解list的定位
你去超市买东西，会拿一张购物清单，从上往下写：牛奶、鸡蛋、面包、纸巾。这个清单就是一个list。你关心的是“第几项是什么”，你会在末尾追加一项，你可能会在某次购物后划掉某个不再需要的项。list这个数据结构，本质上就是计算机世界里那张购物清单。
不过，同样是“清单”这个概念，不同语言给了它不同的性格。Python里的list可以装各种不同类型的东西——整数、字符串、甚至另一个list套在里面；C++的std::list是严格同类型的；Java的ArrayList也是同类型的。性格不同，是因为它们底层实现不同，服务的使用场景也不同。
这里要澄清一个非常常见的认知误区：很多人以为所有语言的list都是一回事。事实不是这样。list在编程语言里只是一个抽象接口，具体怎么存储、怎么增删、性能如何，完全是另一套底层故事。理解list的关键，不是背下它的API，而是理解它背后“怎么存”、“怎么改”、“内存怎么管理”这三大问题。
1.2 list在编程语言中的角色定位
翻开任何一门现代编程语言的标准库，list都是出镜率最高的数据结构。为什么？因为它太贴合人类的思维习惯了。人类天然习惯用“一串东西”来组织信息：一串数字、一串名字、一串步骤。list就是这种线性思维的直译。
从数据结构的分类来看，list属于线性表。所谓线性表，就是数据元素之间是一对一的线性关系，除了第一个元素没有前驱、最后一个元素没有后继之外，每个元素都有且仅有一个前驱和一个后继。线性表在物理存储上只有两种方案：一种是连续存储（数组），一种是链式存储（链表）。所有语言里的list，最终都落在其中一种或两种方案的组合上。
搞清楚了这一点，你就拿到了理解list底层实现的钥匙。后面我们讲的所有内存布局、性能差异、扩容策略，都是从“连续存储”和“链式存储”这两棵树上长出来的。
2. 连续存储：Python list与动态数组的底层真相
2.1 Python list看起来是链表，其实是数组
先说一个很多人不知道的事实：Python的list，底层根本不是链表，而是一个动态数组。这一点让很多从C++转过来的人大跌眼镜，因为C++里有std::list和std::vector之分，前者是链表，后者是动态数组，职责分明。Python的list一个顶俩，但它骨子里是vector那一派的。
动态数组的核心特征是什么？连续内存。所有元素在内存里一个挨着一个排列，像一栋楼的房间一样，门牌号连续。Python的list变量，其实存的是一个指针，指向一个叫做PyListObject的结构体。这个结构体里面有这样一个关键字段：
typedef struct { PyObject **ob_item; Py_ssize_t allocated; Py_ssize_t size; } PyListObject;ob_item指向真正存放元素引用的连续内存区域（是一个指针数组），size是当前实际元素个数，allocated是当前已分配的内存容量（能容纳的元素个数）。注意这两个值的关系：allocated大于等于size，多出来的部分是预留给未来追加元素的。
为什么多留这一部分？答案是性能。如果不预留，每次追加一个元素都要重新分配内存并把旧数据搬过去，复杂度O(n)，一万次追加就是O(n²)，直接爆炸。预分配的本质是用空间换时间。
2.2 扩容策略：为什么是翻倍而不是加一
Python list的扩容机制，经典到几乎每个面试官都会问。什么时候扩容？当size == allocated，也就是当前数组装满了，再追加元素就得扩容。Python的策略是：
- 如果
allocated为0，初次分配4个元素的空间； - 之后扩容时，新容量取
size + (size >> 3) + (size < 9 ? 3 : 6)这个公式。
举个例子，初始容量0，第一次append触发扩容，新容量变成4。当装到第4个元素再append时，新容量大概是4 + 4>>3 + 6 = 4 + 0 + 6 = 10。注意这里不是简单的翻倍，而是约1.125倍加上一个修正量。之所以不选择严格的2倍扩容，是为了减少内存浪费——Python的list太常用来装小数据了，翻倍对小列表来说过于激进。
扩容的具体流程是这样的：
- 申请一块新的连续内存，大小为
new_allocated； - 用
memcpy把旧数组里的每一个指针复制到新内存； - 释放旧内存；
- 更新
ob_item指向和allocated值。
这个过程中最耗时的就是第二步的数据搬运。如果你知道大概要装多少数据，预先用list. reserve（其他语言）或通过初始化指定大小（Python里可以用[None] * n）来规避多次扩容，这是我在写代码时非常常用的一条优化手段。
2.3 连续存储带来的性能双刃剑
连续存储的性能特征，简单说就是“读快写慢（指插入删除）”。
读取快到什么程度？因为内存连续，list支持O(1)时间复杂度的随机访问。要取第1000个元素？直接用list[999]，底层计算ob_item + 999 * 指针大小的偏移量，一步到位。这种直接通过偏移量寻址的方式，跟数组一样高效。
写入为什么慢？如果你在头部插入一个元素，比如list.insert(0, x)，那就要把原有所有元素往后挪动一位。100万个元素的list，头插一次就要搬移100万个指针。这个操作的均摊时间复杂度是O(n)。尾部追加（append）则不同，因为有预留空间，大多数情况直接写在末尾，均摊O(1)。
还有一个很容易被忽视的问题：连续存储对CPU缓存非常友好。现代CPU在读取内存时，会把相邻地址的数据一次性加载到缓存行（cache line）里。遍历一个list时，下一个元素大概率已经在缓存里了，访问速度极快。这一点在性能敏感的场景下，效果天差地别。后面讲链表时你会看到反差有多大。
3. 链式存储：C++ std::list与真正的链表实现
3.1 链表的节点结构与内存布局
如果说动态数组是“一排列队站好的人”，链表就是“手拉手的一串人，每个人只知道自己前后是谁”。链表的每个元素叫做节点，节点里除了存数据，还存着指向下一个节点（以及可能指向上一个节点）的指针。
C++标准库的std::list是一个双向链表，每个节点长这样：
template <class T> struct __list_node { __list_node* _M_prev; __list_node* _M_next; T _M_data; };每个节点包含：指向前一个节点的指针、指向后一个节点的指针、以及真正存储的数据。要注意的是，节点之间在内存里不是连续的。每次new一个节点，操作系统从堆里找一个空闲位置给你，这些位置可能零散地分布在内存各处。
这意味着什么？意味着链表没法用偏移量来寻址。你想访问第5个节点，没有捷径，只能从头部一个个往后跳：第1个的下一个是第2个，第2个的下一个是第3个……这种访问方式叫顺序访问，时间复杂度O(n)。链表没有随机访问能力，这是它和数组最根本的差别。
3.2 为什么链表插入删除真的快
链表最引以为傲的优势是插入和删除。要在某个节点后面插入一个新节点，只需要改几个指针的指向，不需要搬动任何数据。比如在node3后面插入new_node：
new_node->next = node3->next; new_node->prev = &node3; node3->next->prev = new_node; node3->next = new_node;画个图就是：原来node3连着node4，现在把node3往后指的指针改指向new_node，把new_node的next指向node4，再把node4的prev改指向new_node。一共改动4个指针，O(1)完成。
这里有个关键前提：你得已经拿到那个位置的迭代器。这就很像你人在某个节点旁边，伸手一接就把新节点挂上去了。但如果你只知道“我要在第5个位置插入”，那还是得先从头走到第5个位置，这个查找过程是O(n)的。所以链表插入的O(1)是“有前提的O(1)”——你得先站在那个位置。
删除同理。已知某个节点的迭代器，执行erase(it)，把前后节点的指针跨过它接上，然后释放这个节点的内存，O(1)完成。这个特性在某些场景下非常有用，比如用一个链表维护一个“待处理队列”，经常要在中间删除元素。
3.3 链表的代价：缓存不命中与内存开销
世上没有免费的午餐。链表用随机内存分布换来了灵活的插入删除，代价是什么？
代价一：缓存命中率极低。前面说了，连续存储对CPU缓存友好。链表正好相反——节点散落在内存各处，遍历一个链表，每次访问下一个节点都极大概率不在缓存里，需要到内存里重新加载。当链表足够大时，这种“缓存不命中”造成的性能损失非常可观。实验数据表明，在纯遍历场景下，vector（动态数组）比list快一个数量级是很正常的事。这个差异在小数据量时感觉不明显，数据量过百万后你会看到天壤之别。
代价二：内存占用更大。每个节点除了存数据本身，还要额外存两个指针。在64位系统上，一个指针8字节，两个就是16字节，这对存储小对象（比如int）来说，内存膨胀非常严重。存一个int只要4字节，链表节点却要4+16=20字节（还要考虑内存对齐），内存开销是数组的5倍左右。
代价三：频繁的内存分配。每次插入一个新节点都要单独new一次，每次删除都要delete一次。频繁的小块内存申请/释放不仅慢，还会造成内存碎片。相比之下，动态数组是一次性分配一大块，只在扩容时才重新分配。
我记得有一次处理一个实时日志系统，需要维护最近10万条日志的序号，中间频繁删除。一开始用了std::list，结果CPU跑满，换成vector加标记删除法之后，负载直接降了40%。这就是“选错了数据结构”的真实代价。
4. 两种实现的正面交锋：一张表看清差异
4.1 关键性能指标对照
为了让你看得更清楚，我整理了一张对比表。这张表是我多次测试后得到的结果，具体数值会因机器不同而略有差异，但相对关系是稳定的。
| 操作 | Python list（动态数组） | C++ std::list（链表） |
|---|---|---|
| 随机访问（list[i]） | O(1)，极快 | O(n)，需要遍历 |
| 尾部追加 | 均摊O(1) | O(1) |
| 头部插入 | O(n)，全部元素后移 | O(1)（如果有头节点迭代器） |
| 中间插入 | O(n)，需搬移 | O(1)（如果有迭代器）/ O(n)（先查找） |
| 删除元素 | O(n)，搬移补位 | O(1)（如果有迭代器） |
| 内存连续性 | 连续 | 不连续 |
| 缓存友好性 | 高 | 低 |
| 空间效率 | 高（只有数据+少量冗余） | 低（额外2个指针/节点） |
| 扩容/分配次数 | 偶尔扩容，成本均摊 | 每个节点一次分配 |
4.2 一个容易踩坑的操作顺序陷阱
上面这张表看着简单，实际用到的时候很多人会踩坑。其中最典型的一个坑：在遍历链表的同时进行操作。
比如你写了个C++程序，要删除链表中所有符合某个条件的节点：
for (auto it = lst.begin(); it != lst.end();) { if (should_delete(*it)) { it = lst.erase(it); // 正确：erase返回下一个有效迭代器 } else { ++it; } }这是正确写法。如果你写成lst.erase(it); ++it;，那++it访问的已经是被删除节点的next指针，属于悬垂指针访问，是未定义行为。轻则数据错乱，重则直接崩溃。我在code review里见过不下十次这种错误。
Python里也有类似的坑。遍历list时删除元素，用for x in lst:边遍历边删，会导致元素跳过或报错。正确的做法是遍历副本或用索引倒着删：
# 错误示范 lst = [1, 2, 3, 4, 5] for x in lst: if x % 2 == 0: lst.remove(x) # 遍历时修改，结果不可预期 # 正确示范：倒序删除 lst = [1, 2, 3, 4, 5] for i in range(len(lst) - 1, -1, -1): if lst[i] % 2 == 0: del lst[i]4.3 到底该怎么选？我的选型经验
说了这么多对比，回到实际问题：我写代码时怎么选？
大原则一句话：默认选动态数组（vector / Python list），除非你有明确的理由必须用链表。
为什么这么激进？因为我踩过太多链表的坑了。链表的优势（O(1)插入删除）只有在“你已经拿着迭代器”的时候才能真正发挥，而实际业务中绝大多数插入删除都是“先查找再操作”，查找本身就是O(n)，链表的优势被抵消一半。再加上缓存不命中和额外内存开销，链表在很多真实场景下反而是劣势方。
那什么时候用链表？我给你几个我实际遇到的场景：
- 实现LRU缓存的时候：需要在O(1)时间内把某个节点移到头部，这需要从哈希表里拿到节点的迭代器，然后用链表在O(1)内完成删除和插入。哈希表+双向链表是LRU的标准实现方案，这个时候链表无可替代。
- 实现文件系统或编辑器的撤销栈：需要频繁在中间插入和删除操作记录，且通常已经持有节点位置。
- 实现一个需要频繁从头部弹出的队列：如果你用的是Python的list，
pop(0)是O(n)的，这时候用collections.deque（底层是双向链表）更好。
除此之外，大部分场景用动态数组就够了。记住一句话：简单场景用数组，高频且位置明确的插入删除用链表。这个经验能帮你少走很多弯路。
5. 深入底层：内存分配与扩容，这些细节真正决定性能
5.1 Python list的扩容过程拆解
Python list的每次扩容，背后其实是Python内存分配器一次较大的内存申请。我在前面简单提了扩容公式，这里完整展开一下。
当触发扩容时，Python会调用list_resize函数，核心逻辑如下（这是CPython的源码逻辑，我用伪代码形式还原）：
def list_resize(self, newsize): allocated = self.allocated # 如果需要增长 if newsize > allocated: allocated = newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6) # 如果需要缩小 elif allocated >= newsize * 5: allocated = max(newsize, self.allocated >> 1)这里有个细节值得注意：Python list不只负责扩容，也负责缩容。当你用pop把一个list从100万减到1万时，Python不会一次次微调，而是在allocated超过所需容量的5倍时一次性压缩到约一半。这个策略的目的很明确——防止频繁增删时反复分配内存。
实际测试一组数据。对一个空list连续append 1000万个整数，观察底层扩容触发的次数：
- 1～4个：容量从0→4
- 5个：容量从4→10
- 第9个：容量从10→20
- 之后每次扩容大约增加1/8的容量
从4到10再到20，看起来有点像“翻倍”，但实际是约1.25倍的增长率。比起C++ vector严格的2倍扩容，Python的做法更省内存，代价是扩容次数略多，极端场景下（比如大量append的循环）会有细微的性能损失。但对绝大多数应用来说，这个损失完全无感。
5.2 再看C++ vector的2倍扩容与迭代器失效
C++的std::vector和Python list是同一个物种——动态数组。但它的扩容策略通常是2倍：当size() == capacity()时，新容量翻倍。2倍扩容的数学意义在于：均摊下来，每个元素被搬移的次数是常数级别，保证append操作均摊O(1)。
但2倍扩容有一个杀手级问题：迭代器失效。
std::vector<int> v = {1, 2, 3}; auto it = v.begin(); v.push_back(100); // 如果发生扩容，it就失效了！为什么？因为扩容时vector会申请新内存、把元素搬过去、然后释放旧内存。it还傻傻地指向旧内存，那块内存已经不属于你了。再访问it就是访问已经释放的内存——这是非常危险的未定义行为。所以在写C++代码时，如果你要边遍历边往vector里追加元素，一定要小心迭代器是否已经失效。
还有一点，reserve是vector的性能利器。如果你知道最终要存多少数据，提前reserve掉，可以完全避免扩容时的搬移操作。我处理大数据时基本都会算一下，该reserve就reserve，这是性价比极高的一行代码。
5.3 内存碎片：链表绕不开的痛
最后讲讲内存碎片。链表每插入一个节点就要单独分配一次内存，这些内存块大小不一、散落各处。频繁增删之后，堆里会留下大量“空洞”——这就是内存碎片。
内存碎片多了会怎么样？最直接的后果是：即使你的程序总共只用了几百MB内存，但碎片占用的空隙让分配器无法找到一块足够大的连续空间，导致明明内存“够用”却分配失败。对长期运行的服务来说，这是很致命的问题。
我遇到过的一个真实案例：一个缓存服务用了std::list保存对象指针，运行一周后内存占用从2GB涨到6GB，但实际有效数据只有1GB。排查后发现就是大量节点增删造成的内存碎片。换用内存池或者改用vector之后，内存占用稳定多了。
所以如果你在一个对内存敏感的长期运行服务里使用链表，强烈建议考虑内存池方案——预分配一大块内存，节点从这个池子里分配，避免频繁交给系统分配器。这是链表高性能使用的必修课。
6. 实践环节：手写一个简化版动态数组
看懂了原理，不如亲手写一遍。这里我用C语言手写一个极简动态数组，把前面讲的理论落成代码。写完你就彻底明白“list底层就是数组加扩容”这句话的含义了。
6.1 核心结构体与初始化
typedef struct { int *data; // 指向连续内存 int size; // 当前元素个数 int capacity; // 已分配容量 } IntList; void list_init(IntList *lst) { lst->data = NULL; lst->size = 0; lst->capacity = 0; } void list_destroy(IntList *lst) { free(lst->data); lst->data = NULL; lst->size = 0; lst->capacity = 0; }这个结构体和PyListObject的核心思想完全一致：用一个指针维护连续内存块，用两个整数分别记录“已用”和“已分配”。
6.2 扩容与追加操作
void list_append(IntList *lst, int val) { if (lst->size == lst->capacity) { // 扩容：初始4，之后2倍 int new_cap = lst->capacity ? lst->capacity * 2 : 4; int *new_data = (int *)realloc(lst->data, new_cap * sizeof(int)); if (new_data == NULL) { // 真实项目中要处理分配失败的情况 exit(-1); } lst->data = new_data; lst->capacity = new_cap; } lst->data[lst->size++] = val; }第3行到第5行就是整个扩容的灵魂。注意我在这里选择了2倍扩容，目的是减少扩容次数；如果你更在意内存占用，可以参考Python的1.125倍策略。两种策略在数学上都能保证均摊O(1)，只是平衡点不同。
6.3 插入与删除操作
void list_insert(IntList *lst, int index, int val) { if (index < 0 || index > lst->size) return; // 先确保有位置 if (lst->size == lst->capacity) { list_append(lst, 0); // 触发扩容 lst->size--; // 撤回这个临时元素 } // 从后往前搬移元素 for (int i = lst->size; i > index; i--) { lst->data[i] = lst->data[i - 1]; } lst->data[index] = val; lst->size++; } void list_remove_at(IntList *lst, int index) { if (index < 0 || index >= lst->size) return; // 从前往后搬移元素，覆盖掉被删的那个 for (int i = index; i < lst->size - 1; i++) { lst->data[i] = lst->data[i + 1]; } lst->size--; }看到那个for循环了吗？这就是“插入O(n)”的来源。你插入的位置越靠前，需要搬移的元素就越多。所以如果你要频繁在头部插入，改用链表或者改成从尾部倒序构建，才是更聪明的解法。
到这里，你对list底层实现的认知应该已经具体化了：list就是一层漂亮的外壳，里面要么是连续数组（Python的list、C++的vector），要么是链式指针（C++的list），所有功能都是在这两种存储结构上加操作而已。
7. 真实场景问题排查：三个案例带你避开list深坑
7.1 案例一：在for循环里删除元素导致元素跳过
这是我见过最多的经典bug。有位同学写了这样的代码：
lst = [1, 2, 2, 3, 2, 4] for x in lst: if x == 2: lst.remove(x) print(lst) # 期望 [1, 3, 4]，实际 [1, 3, 2, 4]为什么最后一个2没删掉？因为for循环是通过下标遍历的，每次循环下标加1。当第一个2被删除后，后面的元素集体往前挪一位，但下标已经指向了下一个位置，于是紧跟在被删元素后面的那个元素就被跳过了。
解决方案有三个：
- 倒序遍历：从后往前删，删除元素不影响前面还没遍历到的下标。
- 遍历副本：
for x in lst[:]:，操作不会互相干扰。 - 用条件构建新列表：
[x for x in lst if x != 2]，最Pythonic的方式。
我实际开发中推荐第三种，一行搞定且逻辑清晰。
7.2 案例二：频繁在头部插入导致性能骤降
有一个日志模块，按时间顺序产生日志，但需要最新日志排在最前面。有人这样写：
logs = [] for log in fetch_all_logs(): logs.insert(0, log) # 每次都在头部插入数据量小的时候没问题，但当日志达到几十万条时，每插入一条就要把已有元素全部后移，总复杂度O(n²)，程序变得奇慢无比。
正确的做法是：
logs = [] for log in fetch_all_logs(): logs.append(log) # 尾部追加 O(1) logs.reverse() # 最后一次性反转 O(n)总复杂度从O(n²)降到O(n)，就是这么简单。这个例子也在提醒你：能用尾部操作就不要用头部操作，这句话对动态数组类list是铁律。
7.3 案例三：C++ std::list的迭代器失效陷阱
最后说一个C++的坑。你有一个std::list<int>，需要在某个条件下把节点搬到另一个链表中：
std::list<int> src = {1, 2, 3, 4, 5}; std::list<int> dst; for (auto it = src.begin(); it != src.end(); ++it) { if (*it % 2 == 0) { dst.splice(dst.end(), src, it); // 把it指向的节点拼接到dst // 注意：splice之后，it依然是有效的！ // 但it指向的内容已经在dst里了 } }注意，这里用splice而不是erase再插入，因为splice是O(1)的节点转移，而“先删除再插入”需要两次指针操作。不过在splice之后，it指向的节点已经不在src里了，此时++it仍然是安全的（splice不会使迭代器失效），但如果你用的是erase，it就彻底失效了，再用就废了。
最容易出错的写法是这样的：
for (auto it = src.begin(); it != src.end(); ++it) { if (*it % 2 == 0) { dst.push_back(*it); src.erase(it); // it失效！ } }erase(it)之后，it就指向了被释放的内存，循环里的++it就是非法访问。这里必须用splice，或者先保存下一个迭代器：
auto it = src.begin(); while (it != src.end()) { if (*it % 2 == 0) { auto next_it = std::next(it); dst.splice(dst.end(), src, it); it = next_it; } else { ++it; } }关于迭代器失效的铁律：**凡是改变了容器结构的操作（erase、insert、push_back导致扩容等），都不要后续使用原来的迭代器，除非语言或文档明确保证它仍然有效。**这条规则救过我太多次了。
8. 从list往深了看：这些进阶数据结构值得进一步了解
8.1 deque：两头都能O(1)的综合体
Python里有collections.deque、C++里有std::deque。它本质是一个分段的连续数组——多个固定大小的数组块，通过一个映射表组织起来。它同时支持头部和尾部的O(1)插入删除，弥补了动态数组和链表各自的短板。
deque的优势是两端的增删都很快，但代价是随机访问略慢于vector。如果你需要的是一个“双端队列”，deque几乎是完美答案。比如Python里实现“最近浏览记录”，用deque(maxlen=10)一行搞定，自动丢弃最旧的记录。
8.2 跳表：链表的进化版，兼顾查找与插入
跳表是个很有意思的结构——在有序链表的基础上添加了多级索引，让查找从O(n)降到O(log n)，同时保留了链表的插入删除灵活性。Redis的有序集合底层就用到了跳表。
跳表的思路是：给链表加几层“快速通道”，高层节点跳过更多的中间节点。查找时从高层往低层走，先跳大步伐，再跳小步伐，最后落到目标位置。多维索引带来的复杂度提升，在实际工程中表现非常稳定，也免去了平衡树旋转调整的麻烦。
8.3 动态数组和链表的选择之外：更底层的思考
最后分享一个我个人的思考方式。每当我需要选一个数据结构时，我不会只问“这是list还是set”，而是问自己三个问题：
- 读多还是写多？读多选动态数组，写多且位置明确选链表。
- 数据量大不大？小数据量随便选，差异微乎其微；大数据量必须算清楚。
- 操作是头部、尾部还是中间？决定了你要不要用deque或者专门设计。
这是我这些年写底层服务积累下来的经验，比死记硬背复杂度表可靠得多。数据结构不是数学题，而是一组权衡。理解权衡的内在逻辑，比记住任何结论都重要。
回到list这个话题本身，说实在的，很多高级的数据结构都脱胎于list的这两个基础版本——数组版和链表版。你把这棵树的根看透了，再往上长什么都顺理成章。希望这篇文章能帮你在自己的技术树上，把list这根枝干扎得更深一点。
