Sunday面试指南

Python 列表底层怎么实现?append 为什么通常很快,头部插入却慢?

下面是模拟面试对话,用来讲解本题,不是真实面经。

🧑‍💻 面试官:Python 列表里能放不同类型,底层是不是链表?

🙋‍♂️ 我:看起来每一项可以不同,所以我猜它更像链表。

🧑‍💻 面试官:那为什么按下标读取很方便,头部插入却要搬动一批成员?

🙋‍♂️ 我:可能它实际保存的是一组对象引用。

🧑‍💻 面试官:如果是连续数组,append 每次都要重新分配吗?

先把列表对象、存放引用的数组、成员对象分开。扩容和移动发生在哪一层,时间复杂度就更容易解释。

面试速答(60 秒版)

以 CPython 为例,list 底层使用可扩展的引用数组。数组里放的是成员对象的引用,所以同一个列表可以保存整数、字符串和其他对象。

列表会区分当前成员数量和已经准备好的容量。尾部还有空位时,append 只需要把新成员引用放进去;容量不够时,才需要扩大引用数组。因此,连续多次追加的平均成本可以摊薄,通常说 append 的均摊复杂度是 O(1)。

头部插入不同。为了给新成员腾位置,后面的引用需要往后移,所以成本随列表长度增长。频繁在两端入队、出队时,可以考虑 deque。

具体扩容公式属于 CPython 的实现细节,解释原理时要说明版本,也不能把均摊 O(1) 说成每次调用都一样快。

列表快在哪里,慢在哪里

知识点详解:列表里连续摆放的是引用

不同类型的成员,为什么能放在一起?

假设 tasks 保存一个任务编号、一段说明和一个任务对象。这三个成员在自己的存储里有不同布局,列表并不需要把它们塞成三个相同大小的数据块。

引用数组保存的是指向这些对象的引用。下标 0、1、2 对应三个引用位置,读取 tasks[1],先找到这个位置,再得到它指向的字符串对象。

这里的“连续”描述引用数组,不表示全部成员对象也紧挨着。这一点和列表占用多少空间有关。只测外层列表的大小,并没有把它指向的所有内容都加进去。

成员数量和容量,为什么要分开?

假设当前有三项任务,引用数组还留着空位。那么追加第四项时,可以利用现有空间。

如果每追加一次都只分配刚好够用的空间,下次追加又要扩大,已有引用可能被反复搬运。CPython 会在扩容时准备一定的额外容量,让后面的若干次追加先使用这些空位。

在 CPython 3.11 的 list_resize 中,可以看到针对增长的预留策略。它还会根据扩展规模调整预留,不能简单背成“所有版本每次都翻倍”。

长度和容量不是同一个数

均摊复杂度,和单次耗时有什么区别?

偶尔一次 append 会碰到扩容,成本比只填一个空位高。分析连续追加时,把这部分成本分摊到整个操作序列,才得到均摊 O(1) 的结论。

下面只观察空间变化,不拿这个小实验宣称性能提升了多少。Python 外层大小会在某些追加点发生变化;TS 的 Array 没有公开 CPython 式的容量查询接口,因此只对照相同的追加与插入操作。

import sys
items = []
previous = sys.getsizeof(items)
for value in range(12):
    items.append(value)
    current = sys.getsizeof(items)
    if current != previous:
        print("长度", len(items), "外层字节数", current)
        previous = current

空间数据和解释器、平台及构造方式有关。这个实验只说明当前环境里能观察到的分配变化,不能靠它直接计算所有成员的总内存。

头部插入,额外工作在哪里?

现在往三项任务前面插入一项。原来第 0 项要变成第 1 项,后面的引用也要相应移动。

尾部还有容量,也省不掉这次移位。容量解决的是有没有地方存,移位解决的是成员应该在哪个下标,两者不是一回事。

因此,主要按下标读取、尾部追加,列表通常很合适。工作集中在头部删除或两端调整时,就应比较 deque 的实际接口与行为。大列表里的成员查找仍可能逐项比较,也不能因为按下标读取快,就说所有查找都是 O(1)。

依据:CPython 3.11 listobject.c、Python 3.11 序列类型、collections.deque。

有空位,头部插入仍要移位

面试官继续追问

提前留下容量,长度也会跟着变大吗?

不会。成员数量和可用容量是两个值,空位不算可读取的列表成员。

扩容一定会把成员对象复制一份吗?

通常调整的是引用数组。已有成员对象不需要因此被深拷贝,其他引用仍能指向它们。

一次追加很多项,能直接套单项 append 的分析吗?

不能。extend 还需要遍历输入并加入每一项,成本应结合新增成员数量和可能发生的扩容计算。

面试速记卡

  • CPython list 保存可扩展的成员引用数组。
  • 对象可以不同类型,引用位置仍可按下标访问。
  • 长度记录成员数量,容量记录已分配空间。
  • append 的 O(1) 是均摊结论,扩容时单次成本更高。
  • 头部插入需要移位,预留容量不能省掉移位。

公司面试真题

这道题暂未收录可核验的公司真题来源。你可以先阅读本文解析,或浏览已收录的公司面试真题。

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历