list 用得越多你越该搞清楚它底层到底是个什么东西。我用 Python 写了这么久最深的感受是平时不觉得一旦碰上性能排查、算法题、面试顺序表这块知识就是绕不过去的坎。说白了Python 的 list 底层就是一张动态顺序表——也就是把数据按顺序存在一块连续内存里的表装不下了就自动扩容。这篇是这个系列的第二个主题我不打算给你念课本而是带你从代码层面把顺序表拆开看包括手动实现一个迷你 list、分析 Python 自带的 list 为什么 add 很快但 insert 很慢再拿一个“求并集”的小问题实战收尾。内容适合刚学会 Python 语法、想系统入门数据结构和算法的朋友也适合那些已经会用 list 但一直没弄懂它内部机制的人。先说清楚一个前提千万不要把“数据结构课上的顺序表”和“Python 里的 list ”当成两件事。它们一个是抽象概念一个是具体实现。理解了顺序表你再回头用 Python 的 list很多行为就会变得合理为什么访问元素是 O(1) 的为什么往头部插入元素那么慢为什么“改一个子列表其他全跟着变”答案其实都在顺序表的内存模型里。1. 顺序表是什么为什么 list 就是它的代表1.1 连续内存与随机存取顺序表的定义挺朴素用一段地址连续的存储单元依次存放数据元素。这句话拆开看有两个关键点一是“连续”二是“顺序存放”。连续意味着第 i 个元素和第 i 1 个元素在内存里是挨着的所以只要你知道了起始地址、每个元素占多大空间就能用一条公式直接算出任意位置元素的地址地址(i) 起始地址 i × 单个元素占用的字节数这个公式是所有顺序表操作的基石。它直接带来的好处就是随机存取想拿第 5 个元素不需要从头数 5 次大脑里算一次乘法和加法就到了。Python 里的lst[5]能那么快底层就是这种定位方式时间复杂度 O(1)。很多初学者会混淆“查找一个值”和“按下标访问一个位置”的复杂度。按下标访问永远是 O(1)因为计算地址只需要公式但按值查找比如x in lst你得一个一个比过去最坏是 O(n)。这两者的区别在课堂上经常考在工作排查性能时也特别有用。1.2 Python list 就是动态顺序表我理解 Python 的 list 时喜欢把它看作“升级版顺序表”。它不要求你在创建时指定最大容量而是用多少存多少不够了自己长大。这种设计叫动态数组在国内的数据结构教材里对应“动态顺序表”。动态主要体现在容量管理上。list 内部除了保存元素还额外记录两个东西当前已用元素数量以及当前容量也就是底层指针数组最多能装多少个元素。当元素个数接近容量时Python 会分配一块更大的连续内存把旧元素全部搬过去再释放掉旧内存。这个“搬过去”的动作听起来很重但因为 Python 会预留一部分容量所以并不是每次 append 都触发搬迁。绝大多数 append 只是往尾部写一个引用很快。你可以在自己电脑上做一个很直观的实验用sys.getsizeof([])看空列表占多少字节再不断 append观察内存大小的跳跃。你会发现它不是每加一个都变而是隔一段跳一次这个“跳”就是扩容发生的时候。2. 先搞清楚 Python 列表的内存真相2.1 列表里存的是引用不是数据本体这里必须单独强调一个非常关键的实现细节CPython 的 list 底层是一个PyObject**数组也就是“指向对象的指针数组”。每个槽位放的不是元素本身而是元素对象的内存地址。这话翻译成人话就是Python list 存的是一堆“门牌号”不是“人”。64 位机器上一个指针占 8 字节所以一个有 10 万个元素的 list光指针数组本身大约占 0.8 MB。如果里面每个元素是一个大型对象真正的对象内存另算。这一点和 C 语言里的数组直接存 int、double 很不一样也是 Python 一切皆对象的代价和特性。因为只存引用list 对元素的类型没有限制。同一个 list 里既能放字符串又能放函数就是因为槽位只管指向对象不在乎对象是什么类型。但也因为只存引用一个经典陷阱就出现了如果你拿同一个可变对象往列表里填了多次看起来是“多个元素”实际上是多个槽位指向同一个对象改一个等于改所有。inner [] lst [inner] * 3 lst[0].append(x) print(lst) # [[x], [x], [x]]很多人第一次遇到这个现象都以为是 Python 疯了其实用“存引用”理解就很顺三个空槽全指向同一个 inner 列表对 lst[0] 做 append操作的是那个共享对象当然另外两个“位置”也看得到变化。如果真想生成三个独立子列表得用列表推导[[] for _ in range(3)]。2.2 扩容不是翻倍那么暴力网上很多教程喜欢说“list 扩容是 2 倍增长”这个说法是简化过的和 CPython 的真实实现有差别。在 CPython 的 list 对象里扩容时机发生在快要填满时新的容量会在“需要容量”基础上再额外留一点缓冲大概多出 12.5% 左右不同版本还会加一点常数。你要是问这有什么实际影响其实主要影响内存占用和扩容频率。预留 12.5% 意味着一个容量 800 的列表等到要装第 801 个元素时底层可能直接扩到 900 多。这样设计的好处是兼顾了内存利用率和扩容成本。你不需要把这个整数背下来只需要抓住一句话list 的 append 之所以总体是接近 O(1) 的就是因为扩容次数少均摊下来每次 append 的成本极低。顺带说一句数据结构教材里通常会讲两种扩容策略增量扩容和倍增扩容。每次固定增加若干容量的方式最坏情况会退化得很厉害按比例扩容的方式均摊复杂度才是 O(1)。Python 的选择也是按比例只是比例没到 2 倍那么大。3. 动手写一个迷你顺序表类3.1 类的骨架与初始化光看理论不够扎实我的建议是别急着直接用 list先自己实现一个简化版顺序表类。你不需要把 list 的所有方法都抄一遍只要覆盖核心操作就行追加、插入、删除、按下标访问、按值查找。我下面这份代码是从实际教课笔记里整理出来的能跑也保留了设计说明。class SeqList: 一个用数组模拟的动态顺序表教学简化版 def __init__(self, capacity8): if capacity 0: raise ValueError(capacity must be positive) self._capacity capacity # 底层容量 self._size 0 # 实际元素个数 self._data [None] * capacity # 底层存储区 def __len__(self): return self._size def __repr__(self): items , .join(str(self._data[i]) for i in range(self._size)) return fSeqList([{items}]) def is_empty(self): return self._size 0 def __getitem__(self, index): if index 0: index self._size if not 0 index self._size: raise IndexError(SeqList index out of range) return self._data[index] def __setitem__(self, index, value): if index 0: index self._size if not 0 index self._size: raise IndexError(SeqList assignment index out of range) self._data[index] value初始化时我提前分配了一块长度为 capacity 的底层数组里面先用 None 占位。_size表示真正暴露给使用者的元素个数而_capacity是底层数组已经申请到的空间。很多初学者会漏掉_size和_capacity的区别一旦漏掉扩容逻辑就会写得乱七八糟。3.2 append 与扩容逻辑追加是最常用的操作。往尾部放一个元素之前先检查容量不够就扩容。我选用 1.5 倍扩容这个策略在工程里很常见比固定 1 高效也比总是 2 倍省内存。def _need_grow(self, extra): return self._size extra self._capacity def _grow(self): new_capacity self._capacity (self._capacity 1) if new_capacity self._size 1: new_capacity self._size 1 self._data.extend([None] * (new_capacity - self._capacity)) self._capacity new_capacity def append(self, value): if self._need_grow(1): self._grow() self._data[self._size] value self._size 1这里有个细节_grow里我用self._data.extend([None] * ...)而不是直接新建一个列表再拷贝。教学版这样写简单不会出错。真实 Python list 的内部实现为了性能会直接用 C 层面的 realloc 或新建指针数组效果类似但省了很多 Python 层面的开销。你只要记住扩容的本质是“找一块更大的连续内存把旧元素搬过去”。为什么说固定 1 不行假如初始容量 8每次只加 1那么前 8 次 append 是 O(1)第 9 次扩容要搬 8 个元素第 10 次又得搬 9 个……总共插入 n 个元素的搬动次数是 8 9 ... n复杂度变成 O(n²)。而按比例扩容时总搬动次数是等比数列求和结果仍然是 O(n)均摊到每次 append 就是 O(1)。3.3 插入、删除和收缩插入操作是顺序表最有代表性的操作。把元素放到指定位置 index必须先将 index 到末尾的所有元素整体往后挪一位腾出空位。挪动方向必须从后往前否则后面的元素会被前面的覆盖。def insert(self, index, value): if index 0: index self._size if index 0: index 0 if index self._size: index self._size if self._need_grow(1): self._grow() for i in range(self._size, index, -1): self._data[i] self._data[i - 1] self._data[index] value self._size 1删除就反过来把后面的元素往前挪把“洞”补上。删除末尾后我还会把最后一个位置置为 None这是很多教程不会主动提的细节。为什么要置 None因为self._data[self._size]里还残留着一个对象引用如果不清理即使逻辑上元素删了那个对象仍然被列表引用着垃圾回收不会及时回收它。在长期运行的进程里频繁插入删除又不清理尾部内存占用会悄悄变大。def pop(self, indexNone): if self._size 0: raise IndexError(pop from empty SeqList) if index is None: index self._size - 1 if index 0: index self._size if not 0 index self._size: raise IndexError(SeqList index out of range) value self._data[index] for i in range(index, self._size - 1): self._data[i] self._data[i 1] self._size - 1 self._data[self._size] None self._maybe_shrink() return value def _maybe_shrink(self): if self._capacity 8 and self._size self._capacity // 4: new_capacity max(8, self._capacity // 2) self._data self._data[:new_capacity] self._capacity new_capacity缩容也是一门学问。以我的经验不要在每次删除时都立刻缩容否则会出现“删除一个元素就搬一次家”的抖动性能会很差。正确做法是设置一个较低的阈值比如容量大于 8 且实际元素数不足容量的四分之一时才缩成一半。Python list 本身也有类似机制所以你会发现删除尾部大量元素后内存有时并不会立刻大幅度下降。最后补一个按值查找方法因为很多场景要用到 index 函数def index(self, value): for i in range(self._size): if self._data[i] value: return i raise ValueError(f{value!r} is not in SeqList) def __iter__(self): for i in range(self._size): yield self._data[i]把上面几段拼在一起就是一个能跑的教学版顺序表。你可以在交互式环境里试试s SeqList() for i in range(20): s.append(i) print(s) s.insert(0, -1) print(s[0]) s.pop(0) print(len(s))所有行为都和内置 list 的关键特性一致按下标访问快、插入和删除头部慢、追加总体很快。4. 顺序表操作复杂度与 Python 使用细节4.1 一张表看懂复杂度我对学员讲顺序表时一定会放这张表。它把 list 日常操作的成本讲透了操作平均复杂度说明lst[i]O(1)按下标定位地址公式直接算len(lst)O(1)内部记录了已用元素个数lst.append(x)O(1) 均摊偶尔触发扩容但平均下来常数小lst.insert(i, x)O(n)需要往后搬动 index 到末尾的所有元素lst.pop()O(1)删除尾部不搬动元素lst.pop(0)/del lst[0]O(n)删除头部全部元素都得往前挪x in lstO(n)最坏逐个比较找不到就遍历完lst.index(x)O(n)同样是线性查找lst.sort()O(n log n)排序算法不在顺序表范畴但和底层数组相关这张表最值得记住的是随机访问便宜中间/头部插入删除贵按值查找也贵。很多性能问题都是“用错了位置”明明只需要先进先出却总在一个大 list 的头部insert(0, x)导致 O(n) 的操作重复了成千上万次。4.2 不同场景下的顺序表使用姿势掌握了复杂度你在实际项目里就能做更合理的选择。我随便举几个经验如果主要操作是两端进出尤其是头部频繁弹出不要用 list应该用collections.deque。deque 在两端都是 O(1)但它牺牲了按下标随机访问的速度因为元素被分成了多个内存块。如果存储的是大量同类型数字可以考虑array.array或numpy.ndarray。普通 list 存的是对象引用即使 10 万个整数对象也各有各的开销array 直接在连续内存里存数值省内存但不是“一切皆对象”。如果需要在已经排序的 list 里保持有序插入bisect.insort能帮你快速找到位置但插入本身仍是 O(n)。数据量大时要换思路比如用跳表或者不实时保持有序只在最后排序。这里多说一句不要每个地方都追求“最优数据结构”。顺序表在 Python 里最大的优势其实是缓存友好和遍历效率高。因为底层数组是连续内存CPU 遍历时能很好地命中缓存在数据量几千到几十万这个量级list 的表现通常很惊艳。盲目引入复杂结构反而可能更慢。5. 实战用顺序表求两个集合的并集5.1 无序版本的直接实现“求解一般集合的并集问题”是很经典的顺序表应用。假设有两个用 list 表示的集合元素不一定有序可能有重复目标是生成并集 list里面的元素不能重复。先写一个最直观的无序版def union_unsorted(a, b): result list(a) for x in b: if x not in result: result.append(x) return result思路很简单先把第一个集合复制一份然后遍历第二个集合只有不在结果里的才追加。但这段代码的复杂度需要警惕x not in result是线性查找外层又要遍历 b 的每个元素整体最坏是 O(m × n)。如果两个集合各有一万个元素最坏就是一亿次比较肉眼可见地卡。这个版本没有用哈希完全符合“顺序表”这个限定场景。考试和面试里如果老师指定只能用顺序表不能借助 set那就得接受 O(m × n)。但如果实际工程里允许用 Python 的 set我还是会建议你换个实现因为 hash 集合的查询平均是 O(1)。5.2 有序顺序表的线性合并如果两个集合并集前都是有序的题目就变了我们可以用合并的思路做到 O(m n)。这也是归并排序里 merge 过程的雏形。def union_sorted(a, b): i, j 0, 0 result [] while i len(a) and j len(b): if a[i] b[j]: result.append(a[i]) i 1 elif a[i] b[j]: result.append(b[j]) j 1 else: result.append(a[i]) i 1 j 1 while i len(a): result.append(a[i]) i 1 while j len(b): result.append(b[j]) j 1 return result这个实现同样是顺序表思路使用辅助 list 当结果容器每次比较两个输入列表的当前元素把较小的加入结果相等时只加一次。这样整个流程每个元素最多被访问一次不会有重复比较。给个例子a [1, 3, 5, 7] b [2, 3, 6, 8] print(union_sorted(a, b)) # [1, 2, 3, 5, 6, 7, 8]从这道小实战能看出顺序表的另一个特点因为支持随机访问用下标 i 和 j 同时从两个表里取元素非常自然。如果换成链表你得先想好自己的指针怎么走逻辑会绕不少。这也解释了为什么很多算法题默认给你数组因为数组就是顺序表。6. 性能实测与常见教训6.1 用 timeit 实测插入差距光说“头部插入慢”不够直观最好自己动手测一次。下面这段代码对比list.insert(0, ...)和list.append(...)的耗时import timeit n 100000 setup_tail flst list(range({n})) setup_head flst list(range({n})) t_tail timeit.timeit(lst.append(-1), setupsetup_tail, number1000) t_head timeit.timeit(lst.insert(0, -1), setupsetup_head, number1000) print(f尾部追加 1000 次: {t_tail:.6f}s) print(f头部插入 1000 次: {t_head:.6f}s)在我自己的机器上同样 1000 次操作头部插入明显比尾部追加慢好几个数量级。原因不用怀疑每次insert(0, -1)底层都要把原有 10 万个元素的引用从后往前整体挪一格。1000 次就是约一亿次指针搬动。尾部的 append 大部分只是写一个位置几乎不搬动。数据量越大差距越夸张。这个实验建议你也跑一遍不是为了记住具体数字而是为了建立“直觉”以后写代码时如果感觉到“为什么这个 list 操作这么慢”先怀疑是不是在头部或中间反复插入删除。6.2 用错了顺序表会踩的坑我最后整理几个高频问题都是实战里真会遇到的情况直接做成快速排查版。第一个坑循环删除元素漏删。很多人喜欢这样lst [1, 2, 3, 2, 1] for x in lst: if x 2: lst.remove(x)看着没毛病跑完发现列表里还有个 2。原因很简单remove删掉某个元素后后面的元素整体前移而循环内部持有的迭代器继续往后走就跳过了紧跟其后的那个元素。这种问题在顺序表里尤其常见因为删除涉及大规模元素移动。正确姿势是先收集要删除的下标再倒序删除或者用列表推导生成新列表lst[:] [x for x in lst if x ! 2]第二个坑修改 append 进去的列表对象导致“全变”。之前提到的[inner] * 3已经是典型还有一个变种是用同一个空列表循环 appendresult [] temp [] for i in range(3): temp.append(i) result.append(temp) print(result) # [[0,1,2], [0,1,2], [0,1,2]]而且三个元素是同一个对象要避免就在循环里新建temp []而不是复用同一个对象。第三个坑大列表pop(0)导致明显卡顿。如果一个队列需要频繁从头部出队用deque而不是 list。list 的pop(0)每次都是 O(n)deque 的popleft()是 O(1)。第四个坑误以为切片等于深拷贝。lst2 lst[:]只复制了引用数组元素对象还是同一批。若元素本身可变且会在新列表里被修改原列表也可能被影响。想要完全独立请使用copy.deepcopy但也要知道深拷贝对性能和内存的消耗都很大不是随便用的。第五个坑频繁插入删除后内存居高不下。前面手动实现缩容时已经说过原因Python 的 list 会在一定条件下缩容但不会每次删除都立刻缩。如果你明确知道某段峰值数据已经不需要了可以主动del lst或把lst重赋值把整个底层数组让给垃圾回收。写在最后的体会平时项目里真没必要自己写一个 SeqList内置 list 在绝大部分场景下又快又稳。但我觉得理解顺序表带来的收益是长远的。面试被问到“Python list 底层是什么”时不再回答“就是个数组”而是能从“引用数组、动态扩容、均摊复杂度、插入删除要搬元素”几个角度展开。调试代码遇到“某个子列表怎么全变了”时也能立刻想到引用共享而不是怀疑 Python 出 bug。这个系列继续往下的话下一类线性表就是链表。顺序表和链表就像两个性格相反的老朋友一个住大平层找东西快但搬家累一个住小隔间搬家快但找东西得挨个敲门。你只有把顺序表先摸透再去看链表才能真正理解为什么链表插入删除快、随机访问慢。至少我自己是这样走过来的希望你也能从这篇里得到一点能落地的收获。