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 43 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_nodenew_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字节链表节点却要41620字节还要考虑内存对齐内存开销是数组的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的listpop(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万个整数观察底层扩容触发的次数14个容量从0→45个容量从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::vectorint 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::listint需要在某个条件下把节点搬到另一个链表中std::listint src {1, 2, 3, 4, 5}; std::listint 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不会使迭代器失效但如果你用的是eraseit就彻底失效了再用就废了。最容易出错的写法是这样的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(maxlen10)一行搞定自动丢弃最旧的记录。8.2 跳表链表的进化版兼顾查找与插入跳表是个很有意思的结构——在有序链表的基础上添加了多级索引让查找从O(n)降到O(log n)同时保留了链表的插入删除灵活性。Redis的有序集合底层就用到了跳表。跳表的思路是给链表加几层“快速通道”高层节点跳过更多的中间节点。查找时从高层往低层走先跳大步伐再跳小步伐最后落到目标位置。多维索引带来的复杂度提升在实际工程中表现非常稳定也免去了平衡树旋转调整的麻烦。8.3 动态数组和链表的选择之外更底层的思考最后分享一个我个人的思考方式。每当我需要选一个数据结构时我不会只问“这是list还是set”而是问自己三个问题读多还是写多读多选动态数组写多且位置明确选链表。数据量大不大小数据量随便选差异微乎其微大数据量必须算清楚。操作是头部、尾部还是中间决定了你要不要用deque或者专门设计。这是我这些年写底层服务积累下来的经验比死记硬背复杂度表可靠得多。数据结构不是数学题而是一组权衡。理解权衡的内在逻辑比记住任何结论都重要。回到list这个话题本身说实在的很多高级的数据结构都脱胎于list的这两个基础版本——数组版和链表版。你把这棵树的根看透了再往上长什么都顺理成章。希望这篇文章能帮你在自己的技术树上把list这根枝干扎得更深一点。