先交代一个背景我自己在学数据结构的时候顺序表这块其实一开始是有点看不起的——不就是个数组吗有什么好学的直到后来用 Python 手写了一遍又被链表、栈、队列轮番虐过之后才意识到顺序表才是真正值得吃透的地基。这个标题是“【数据结构与算法】2_python版_顺序表”关键词就三个数据结构与算法、Python、顺序表但我今天想聊的远不止这三个词。我会把底层的内存布局、Python list 的真实实现、手写顺序表的完整代码、复杂度的来龙去脉以及我踩过的几个典型坑全部讲清楚。这篇东西特别适合正在学数据结构、准备面试笔试、或者用 Python 做开发但从来没深究过列表底层的朋友。哪怕你之前没接触过数据结构只要有一点 Python 基础也能跟得上。1. 顺序表到底是什么——先搞清楚底层逻辑1.1 从内存布局说起为什么叫顺序很多人第一次接触“顺序表”这个概念时会下意识把“顺序”理解成“有顺序”也就是元素排成一排。这个理解没有错但没说到根上。数据结构里说的顺序表全称是“顺序存储结构的线性表”它的核心特征不是逻辑上的顺序而是物理存储位置上的连续。你可以把内存想象成一栋酒店的大楼每个房间都有一个唯一的门牌号内存地址。顺序表的意思是你要入住 5 个元素就直接订一层楼里挨在一起的 5 个房间谁的地址都比前一个小一点或者大一点中间不能穿插其他房间。正是因为地址连续所以我可以不靠任何额外的线索只凭“起始地址 下标 × 每个元素大小”就能算出第 N 个元素的位置。这就是为什么顺序表按下标访问的时间复杂度是 O(1)纯数学运算不需要真的去挨个数。这个逻辑用 C 语言表达非常直观int arr[5] {10, 20, 30, 40, 50}; printf(%d, *(arr 3)); // 直接算出地址取出40而在 Python 里底层帮你把“算地址”这件事封装掉了你用list[3]就能拿到第 4 个元素。封装是好事但如果你不知道底层是在做地址运算你就很难理解为什么数组按下标访问能 O(1)、为什么插入删除要挪动一堆元素。1.2 顺序表和链表的选型之争学顺序表几乎不可能不提到链表因为这俩是线性表最经典的两种实现方式。很多人喜欢背结论顺序表查得快、增删慢链表增删快、查得慢。这个结论对但太粗糙了。我举个生活中的例子。顺序表就像是电影院里一整排连在一起的座位座位号固定你买票时说“第 5 排 7 座”检票员直接就能告诉你往哪走不需要数座位。但如果你想在 5 号座和 6 号座之间再塞进去一个座位那从 6 号座开始的每个人都得挪一个位置这就是插入的代价。链表则像一条手拉手的队伍每个人只记住下一个人在哪想往中间插一个人只需要让前面的人改一下手拉的是谁后面的人不用动。但如果你想找队伍里第 10 个人你必须从第 1 个人开始一个接一个数过去。但真实场景里选哪个光背结论是不够的。关键看三个指标读多写多、操作位置、数据量级。如果是一个高频按下标随机访问、偶尔追加数据的场景比如实现一个排行榜、缓冲区、内存池顺序表几乎总是更好的选择因为 CPU 缓存对连续内存非常友好。如果是高频在头部或中间插入删除、又不太需要随机访问的场景比如 LRU 缓存、文本编辑器的撤销栈那链表结构才合适。大多数普通业务代码里Python list 一个就够了因为它是动态扩容的顺序表绝大多数场景的读写模式都够用。2. Python 列表和顺序表的关系——不要傻傻分不清2.1 Python list 的底层就是动态顺序表很多刚入门 Python 的人会有一个错觉觉得 Python 的 list 是“高级货”和数据结构课里的顺序表、链表都不一样。实际上CPython 里 list 的底层实现就是一个动态数组也就是带自动扩容功能的顺序表。它不是链表也不是什么杂合体就是顺序表。具体展开说CPython 中 list 对象的核心结构是PyListObject它内部维护了三样东西一个指向指针数组的指针ob_item、一个记录已用元素个数的ob_size、一个记录当前容量最多能存多少个元素的allocated。注意一个关键点这个数组里存的不是对象本体而是指向 Python 对象的指针。这意味着无论你存的是整数、字符串还是自定义类的实例数组里每个元素占用的空间大小是一样的都是指针大小所以依然可以用地址运算来按下标访问。还有一个特别容易忽略的细节Python list 里存的元素是强引用。也就是说只要这个 list 还存在引用list 里的对象就不会被垃圾回收。所以用 list 做缓存时要注意内存可能被撑爆这和 C 数组存数值的本体是完全不同的思路。明白了这一层我们再回头看为什么 Python 的list.insert(0, x)很慢就顺理成章了——那是在原地把整个顺序表所有元素往后挪一位时间复杂度 O(n)。2.2 扩容机制为什么 append 有时候快有时候慢我第一次听说动态数组会“自动扩容”时心里想的是那不就相当于每次要数组变大的时候重新找块更大的内存把数据搬过去吗那按理说每次 append 都该很慢啊为什么大家都说 append 是 O(1)这里面有一个非常关键的机制叫“增量扩容”。Python 的 list 扩容倍数大致是容量不够时新的容量会在原来基础上增加约 1/8 再加上若干固定值不同版本细节不同整体上可以理解为按比例增长。更经典的讲解方式是看 C vector 或早期 Python 的 2 倍扩容策略容量从 1 扩到 2再扩到 4、8、16、32……这样大部分 append 操作直接写入下一个空位就行不需要搬数据只有到达容量上限的那一次才触发整体搬迁。如果每次扩容都翻倍那么从空列表开始连续 append n 个元素搬迁元素的总次数大约是 1 2 4 8 ... n ≈ 2n均摊到 n 次 append 上每次也就是常数级别的开销。这就是“均摊时间复杂度 O(1)”的含义。我打个比方你每个月往存钱罐里放 100 块罐子快满的时候换一个大 2 倍的罐子虽然换罐子那一次代价很高但摊到每个月来看其实平均成本非常低。Python 的 list 扩容用的就是这个思路只是倍率没那么激进更偏向省内存。实操心得不要在循环里用list.insert(0, x)来构建一个反序列表正确做法是用append后reverse()或者直接用collections.deque。一旦你亲手实现过顺序表你会特别理解 Python 为什么给出这些内置方法——很多语言层面的设计都是在帮你避开 O(n) 的操作。3. 手写一个 Python 顺序表——核心操作实现3.1 基础骨架初始化与判空我强烈建议每个学数据结构的人都动手写一遍顺序表哪怕你平时开发根本不会用到自己写的版本。因为只有自己写过你才会明白 insert 到底在做什么、delete 为什么要把末尾清空、复杂度分析里的每一步到底对应哪一行代码。先看一个最基础的手写版本。不像 CPython 不需要你手动 malloc 和 free但“预留容量”和“已用长度”这两个概念依然要自己维护class SeqList: def __init__(self, capacity10): self.capacity capacity # 当前最多能存多少元素 self.data [None] * capacity # 底层数组先占好坑 self.length 0 # 当前实际元素个数 def is_empty(self): return self.length 0 def is_full(self): return self.length self.capacity def __len__(self): return self.length def __getitem__(self, index): if index 0 or index self.length: raise IndexError(index out of range) return self.data[index] def __setitem__(self, index, value): if index 0 or index self.length: raise IndexError(index out of range) self.data[index] valueself.data [None] * capacity这行就是在内存里申请一段连续空间。None在这里不是元素值而是“空位”的意思这在 Python 里很重要。数据结构的逻辑长度和物理容量是两码事数组长度 10不代表里面有 10 个逻辑元素只有self.length个。3.2 插入操作的位移陷阱顺序表的插入逻辑一句话就能说完把插入位置及其后面的所有元素都往后挪一位再把新元素放进去。但这句话落到代码里有三个坑。第一个坑是移动方向。插入时要“从后往前”移动否则前面的元素会覆盖后面的元素。假设数组是[1, 2, 3, 4]要在下标 1 插入99如果从前往后搬2被搬到3的位置时其实先把3覆盖了数据就丢了。正确做法是从最后一个元素开始搬到后一个位置再搬倒数第二个直到把插入位置空出来。第二个坑是循环边界。可以这样理解假设当前长度是 4要在下标 1 插入那么下标 3 的元素要搬到下标 4下标 2 的搬到 3下标 1 的搬到 2。所以range要从self.length - 1一路递减到index。第三个坑是越界判断。插入允许的位置范围是0到self.length含两端因为插到末尾是合法操作。如果传个负索引或者比 length 还大的数得主动抛异常而不是让底层数组悄悄出错。完整的插入代码如下def insert(self, index, value): if index 0 or index self.length: raise IndexError(index out of range) if self.is_full(): self._resize() for i in range(self.length, index, -1): self.data[i] self.data[i - 1] self.data[index] value self.length 1我在上课和带新人时反复强调range(self.length, index, -1)是在从最后一个元素开始逐个往后挪。你可以在草稿纸上画一个小数组手动模拟一遍。这个过程看似简单但真的有人会漏掉self.length这个初始位置导致最后一个元素平白无故丢了。3.3 删除操作的内存管理删除操作和插入正好相反从删除位置开始后面的元素依次往前挪覆盖掉要删除的那个位置最后让length减一。还是那个例子删除下标 0 的元素就是把下标 1 搬到 02 搬到 13 搬到 2。但 Python 手写时有一个点特别微妙数组里最后一个位置在逻辑删除后仍然可能残留着之前的引用。比如self.length从 4 减到 3 之后self.data[3]还指向原来第 4 个元素。在 C 语言里这只是一个无效的散落数据等着被新数据覆盖但在 Python 里它会让对象一直被引用无法被垃圾回收。所以删除操作的最后一步最好把腾出来的位置重新设置为Nonedef delete(self, index): if index 0 or index self.length: raise IndexError(index out of range) value self.data[index] for i in range(index, self.length - 1): self.data[i] self.data[i 1] self.length - 1 self.data[self.length] None # 释放引用 return value提示这一步对初学者来说可能感觉“多此一举”但是我实测下来在写一个大循环反复增删的测试脚本时如果不把末尾置None内存占用会肉眼可见地增长。Python 的引用计数在这种情况下才不会帮你及时回收对象。删除时还有一个小技巧越界判断是index self.length不是index self.length。因为删除位置必须确实存在元素删除length那个位置本身就是非法的。这个边界条件和插入的边界是两个完全不同的判断标准千万别搞混。3.4 按下标查找与按值查找顺序表最爽的体验就是按下标查找。前面说过因为内存连续按下标访问理论上就是一次地址运算和元素的个数无关。这是所有 O(1) 复杂度操作中最直白的一个。def index_of(self, value): for i in range(self.length): if self.data[i] value: return i return -1按值查找就没办法快了在没有额外结构比如哈希索引的前提下只能从前往后一个元素一个元素比对最坏的情况下要遍历完整张表时间复杂度 O(n)。Python 内置的list.index()底层做的是同一件事它并不是用了什么魔法。这里要顺带提一个很重要的概念内部实现顺序表存储的元素如果是对象引用那按下标访问拿到的是引用本身不是拷贝。如果你在__getitem__里直接return self.data[index]外部拿到引用后可以原地修改这个对象从而绕过顺序表改掉内部数据。在真实项目中这是特性不是 bug但如果你写的是封装性很强的类就要考虑返回副本。这个细节很多资料不提但面试被问到如何防止外部修改内部数据时这就是考点。3.5 扩容动态顺序表自我成长的关键一步前面写插入时调用了_resize()这一步就是动态顺序表最关键的灵魂——当数组满了你不能拒绝写入而应该申请一块更大的连续空间把所有旧数据搬过去然后释放旧数组。def _resize(self): new_capacity self.capacity * 2 new_data [None] * new_capacity for i in range(self.length): new_data[i] self.data[i] self.data new_data self.capacity new_capacity这里我选择“扩容为原来的 2 倍”这是最经典的策略。为什么是 2 倍而不是“1 个位置”假设每次只多申请一个位置那连续插入 n 个元素需要搬迁大约 n²/2 次均摊下来每次 append 是 O(n)整体是灾难性的慢。翻倍扩容则能让均摊成本降到 O(1)。那是不是倍数越大越好也不是如果用 10 倍扩容大部分时间内存被白白占着利用率低空间浪费严重。2 倍是空间和时间比较经典的折中点。如果元素本身特别大、内存压力高有人会用 1.5 倍扩容来减少空间浪费但带来的代价是均摊操作偶尔要搬迁更多次。这属于工程上的取舍笔试面试被问到为什么用 2 倍时主线答均摊 O(1) 空间利用率折中就不会跑偏。在实际 CPython 的实现里扩容策略会刻意考虑内存池的分配粒度不会简单地每次精确乘 2而是在ob_item分配时使用类似按需分配整块内存 预留一部分的方式。但作为数据结构学习先理解 2 倍扩容的核心逻辑就足够遍历所有考点。4. 复杂度分析与性能对比4.1 时间复杂度速查表学这个章节最忌讳的就是只看结论不推过程。下面这张表的每一条你都应该能用前面的代码推出来。操作顺序表数组链表说明按下标访问O(1)O(n)数组直接地址运算按值查找O(n)O(n)都需要遍历但常数不同头部插入O(n)O(1)已知前驱数组要全表后移尾部插入O(1) 均摊O(1)数组扩容均摊后是常数中间插入O(n)O(1)已知位置数组要搬后半段头部删除O(n)O(1)数组要全表前移尾部删除O(1)O(n)单向链表单向链表找前驱也要遍历你可能会问链表尾部删除在双向链表下也是 O(1) 啊为什么表格写 O(n)这就是我强调要基于具体实现聊复杂度的原因。手写单链表时你根本没有办法直接定位到倒数第二个节点必须从头遍历过去。所以任何复杂度结论都必须绑定具体的数据结构和实现细节这才是数据结构这门课真正想训练你的思维方式。4.2 空间复杂度与扩容策略顺序表的空间复杂度主要看两部分一是底层数组本身占用的空间二是逻辑上存储 n 个元素时是否有额外浪费。在不扩容的情况下顺序表空间复杂度是 O(n)非常干净。但动态扩容的顺序表就没这么简单了——数组容量是当前元素数量的上界如果频繁使用插一个删一个的模式容量可能会一直维持在高位造成空间的闲置浪费。举个真实例子你往 list 里连续 append 了一万个元素然后执行while len(lst) 1: lst.pop()把元素删到只剩一个。这时候 Python list 的allocated容量可能仍然是万级。虽然 Python 内部会在列表明显缩小时缩容具体的触发条件与版本相关list_resize或list_clear会根据allocated与size的比例判断但如果你想立刻释放内存更可靠的做法是显式lst []或者lst.clear()甚至创建新列表来彻底释放旧数组。这在写长驻内存的服务时尤为重要。另外有一个经典面试题已知顺序表容量是 n里面实际元素 m n请问空间复杂度是多少标准答案是 O(n) 还是 O(m)要看题目考察的是已分配的空间还是有效使用的空间。底层数组确实占用了 O(n) 的空间但有效数据只占 O(m)。理论上空间复杂度通常以实际存储开销为衡量所以更严谨说是 O(n)因为数组整体被分配了。这个细节建议在回答时直接点明别等面试官追问。5. 实操中常见的坑与排查技巧实录5.1 越界问题index out of range 不等于数据不存在这是新手写顺序表时最常撞的墙。当你连续 insert 很多次之后有时明明length和capacity都对一访问却报IndexError。我排查过很多次这类问题最后发现绝大多数都出在初始化之后的data与length不同步上。比如你可能在初始化时写了self.data []然后在 insert 里用self.data[i] value——空列表根本没有下标i一赋值就报错。正确的做法是初始化时用[None] * capacity预分配好位置这样下标赋值才有效。这个在 Python 里显得不自然但这就是顺序表预先留坑的本质。另一种常见是我在 3.1 里展示的__getitem__边界判断没写对导致访问data[length]时不报错拿到一个不该出现的None这种“静默失败”比报错更可怕因为它会让 bug 潜伏到很后面才暴露。5.2 扩容后的引用失效问题很多从 C 语言转过来的人会特别担心一件事数组扩容后原来拿到的指针是不是就失效了在 C 里确实会realloc之后旧地址可能不再有效所有旧的指针和迭代器都会变成危险的野指针。但在 Python 里你无需关心这个问题因为底层的PyListObject会在扩容后更新ob_item指针而你手里拿到的 list 对象引用始终是同一个对象。你可以做个实验构造一个列表记录它的id()然后不断 append 直到扩容再打印id()你会发现 id 始终不变。但这不意味着没有隐患。隐患在另一个层面——如果你在自定义类中手动管理下标引用比如记下了self.data[index]的引用扩容不会让这个引用失效元素对象本身还活着但如果你想模仿 C 的指针数组 局部缓存思路错误地保存了旧数组对象那扩容后旧数组被替换掉你保存的旧引用就会一直占着内存导致扩容白扩了。也就是说Python 的扩容对使用者透明是好事但你仍然要管理好自己的外部缓存不要让旧数组对象被局部变量长时间引用。5.3 元素移动方向搞反的排查方法我自己带过不少人写顺序表最常见的代码错误就是移动方向反了。插入时从前往后搬结果后半段数据全部被覆盖成同一个值删除时从后往前搬结果开头几个元素被覆盖旧值残留尾端。这类 bug 的特点是小规模测试可能看不出问题元素一多立刻炸。我的排查方法很简单在关键的for循环里打印每一步移动的状态。for i in range(self.length, index, -1): print(fmove data[{i - 1}] - data[{i}]) self.data[i] self.data[i - 1]打印几轮后你就能非常直观地看到插入时一定是先处理最后一个元素删除时一定是先处理最前面的元素。等你把这段代码写顺了后面学插入排序、希尔排序这种依赖相邻交换的算法时会非常顺。5.4 尽量用 Pythonic 的写法但别忘原理最后我特别想提醒一点手写顺序表是为了理解原理但在日常开发里不要重复造轮子。Python 内置的 list 已经是一个高度优化的动态顺序表它的 append、pop、切片操作都是 C 级别实现的性能远超你手写的版本。你要做的是学会在合适的时候用合适的方法# 尾部追加O(1) lst.append(x) # 尾部弹出O(1) lst.pop() # 按位置插入O(n) lst.insert(2, x) # 按位置删除O(n) lst.pop(2) # 原地反转O(n) lst.reverse()真正值得你动手写的是一些内置 list 没法直接提供、但又建立在顺序表思想上的结构比如循环队列、固定容量缓存、基于数组的栈与队列。我自己的学习路径就是先用 Python 手写一遍顺序表再用 Python 分别实现基于顺序表的栈和队列然后做力扣上的数组类题目。这一套下来数组相关的数据结构和复杂度分析会打通百分之七八十。5.5 我踩过的一个印象深刻的坑讲一个我上个月实际遇到的现场。当时我在写一个批量数据处理脚本第一版用的是lst [None] * n预先占位后来需求变化要动态往中间插入我图省事直接用了lst.insert()处理几万行数据时明显卡顿。一查才发现我在一个循环里频繁对中间位置做插入时间全部耗在元素搬移上了。说白了顺序表的中间插入是 O(n)我就用了 O(n²) 的算法。后来我换了思路因为中间插入的位置其实是有规律的我改成先用 list 收集所有数据最后统一做一次分片重组整体耗时下降了不止一个数量级。这说明什么数据结构的理论不是考试用的是写代码时真正能救命的。写在最后算法与数据结构学久了你会慢慢发现最基础的东西往往最值得反复琢磨。顺序表看起来只是数组包装了一下但只有亲手实现了扩容、插入、删除你才会真正理解为什么 Python 的 list 某些操作特别快、某些操作特别慢也才能在写代码时下意识避开 O(n²) 的陷阱。我个人在实际学习中的体会是这类内容别只看文档和视频也别满足于看懂别人写的代码一定要自己在编辑器里敲一遍、跑一遍、故意写错一遍再排查一遍。写错的那一次才是你真正长记性的一刻。如果你现在正卡在顺序表或者 Python 列表的底层机制上希望这篇整理能帮你把那层窗户纸捅破。动手写别停。 Python顺序表底层原理与实现：从内存布局到性能优化
先交代一个背景我自己在学数据结构的时候顺序表这块其实一开始是有点看不起的——不就是个数组吗有什么好学的直到后来用 Python 手写了一遍又被链表、栈、队列轮番虐过之后才意识到顺序表才是真正值得吃透的地基。这个标题是“【数据结构与算法】2_python版_顺序表”关键词就三个数据结构与算法、Python、顺序表但我今天想聊的远不止这三个词。我会把底层的内存布局、Python list 的真实实现、手写顺序表的完整代码、复杂度的来龙去脉以及我踩过的几个典型坑全部讲清楚。这篇东西特别适合正在学数据结构、准备面试笔试、或者用 Python 做开发但从来没深究过列表底层的朋友。哪怕你之前没接触过数据结构只要有一点 Python 基础也能跟得上。1. 顺序表到底是什么——先搞清楚底层逻辑1.1 从内存布局说起为什么叫顺序很多人第一次接触“顺序表”这个概念时会下意识把“顺序”理解成“有顺序”也就是元素排成一排。这个理解没有错但没说到根上。数据结构里说的顺序表全称是“顺序存储结构的线性表”它的核心特征不是逻辑上的顺序而是物理存储位置上的连续。你可以把内存想象成一栋酒店的大楼每个房间都有一个唯一的门牌号内存地址。顺序表的意思是你要入住 5 个元素就直接订一层楼里挨在一起的 5 个房间谁的地址都比前一个小一点或者大一点中间不能穿插其他房间。正是因为地址连续所以我可以不靠任何额外的线索只凭“起始地址 下标 × 每个元素大小”就能算出第 N 个元素的位置。这就是为什么顺序表按下标访问的时间复杂度是 O(1)纯数学运算不需要真的去挨个数。这个逻辑用 C 语言表达非常直观int arr[5] {10, 20, 30, 40, 50}; printf(%d, *(arr 3)); // 直接算出地址取出40而在 Python 里底层帮你把“算地址”这件事封装掉了你用list[3]就能拿到第 4 个元素。封装是好事但如果你不知道底层是在做地址运算你就很难理解为什么数组按下标访问能 O(1)、为什么插入删除要挪动一堆元素。1.2 顺序表和链表的选型之争学顺序表几乎不可能不提到链表因为这俩是线性表最经典的两种实现方式。很多人喜欢背结论顺序表查得快、增删慢链表增删快、查得慢。这个结论对但太粗糙了。我举个生活中的例子。顺序表就像是电影院里一整排连在一起的座位座位号固定你买票时说“第 5 排 7 座”检票员直接就能告诉你往哪走不需要数座位。但如果你想在 5 号座和 6 号座之间再塞进去一个座位那从 6 号座开始的每个人都得挪一个位置这就是插入的代价。链表则像一条手拉手的队伍每个人只记住下一个人在哪想往中间插一个人只需要让前面的人改一下手拉的是谁后面的人不用动。但如果你想找队伍里第 10 个人你必须从第 1 个人开始一个接一个数过去。但真实场景里选哪个光背结论是不够的。关键看三个指标读多写多、操作位置、数据量级。如果是一个高频按下标随机访问、偶尔追加数据的场景比如实现一个排行榜、缓冲区、内存池顺序表几乎总是更好的选择因为 CPU 缓存对连续内存非常友好。如果是高频在头部或中间插入删除、又不太需要随机访问的场景比如 LRU 缓存、文本编辑器的撤销栈那链表结构才合适。大多数普通业务代码里Python list 一个就够了因为它是动态扩容的顺序表绝大多数场景的读写模式都够用。2. Python 列表和顺序表的关系——不要傻傻分不清2.1 Python list 的底层就是动态顺序表很多刚入门 Python 的人会有一个错觉觉得 Python 的 list 是“高级货”和数据结构课里的顺序表、链表都不一样。实际上CPython 里 list 的底层实现就是一个动态数组也就是带自动扩容功能的顺序表。它不是链表也不是什么杂合体就是顺序表。具体展开说CPython 中 list 对象的核心结构是PyListObject它内部维护了三样东西一个指向指针数组的指针ob_item、一个记录已用元素个数的ob_size、一个记录当前容量最多能存多少个元素的allocated。注意一个关键点这个数组里存的不是对象本体而是指向 Python 对象的指针。这意味着无论你存的是整数、字符串还是自定义类的实例数组里每个元素占用的空间大小是一样的都是指针大小所以依然可以用地址运算来按下标访问。还有一个特别容易忽略的细节Python list 里存的元素是强引用。也就是说只要这个 list 还存在引用list 里的对象就不会被垃圾回收。所以用 list 做缓存时要注意内存可能被撑爆这和 C 数组存数值的本体是完全不同的思路。明白了这一层我们再回头看为什么 Python 的list.insert(0, x)很慢就顺理成章了——那是在原地把整个顺序表所有元素往后挪一位时间复杂度 O(n)。2.2 扩容机制为什么 append 有时候快有时候慢我第一次听说动态数组会“自动扩容”时心里想的是那不就相当于每次要数组变大的时候重新找块更大的内存把数据搬过去吗那按理说每次 append 都该很慢啊为什么大家都说 append 是 O(1)这里面有一个非常关键的机制叫“增量扩容”。Python 的 list 扩容倍数大致是容量不够时新的容量会在原来基础上增加约 1/8 再加上若干固定值不同版本细节不同整体上可以理解为按比例增长。更经典的讲解方式是看 C vector 或早期 Python 的 2 倍扩容策略容量从 1 扩到 2再扩到 4、8、16、32……这样大部分 append 操作直接写入下一个空位就行不需要搬数据只有到达容量上限的那一次才触发整体搬迁。如果每次扩容都翻倍那么从空列表开始连续 append n 个元素搬迁元素的总次数大约是 1 2 4 8 ... n ≈ 2n均摊到 n 次 append 上每次也就是常数级别的开销。这就是“均摊时间复杂度 O(1)”的含义。我打个比方你每个月往存钱罐里放 100 块罐子快满的时候换一个大 2 倍的罐子虽然换罐子那一次代价很高但摊到每个月来看其实平均成本非常低。Python 的 list 扩容用的就是这个思路只是倍率没那么激进更偏向省内存。实操心得不要在循环里用list.insert(0, x)来构建一个反序列表正确做法是用append后reverse()或者直接用collections.deque。一旦你亲手实现过顺序表你会特别理解 Python 为什么给出这些内置方法——很多语言层面的设计都是在帮你避开 O(n) 的操作。3. 手写一个 Python 顺序表——核心操作实现3.1 基础骨架初始化与判空我强烈建议每个学数据结构的人都动手写一遍顺序表哪怕你平时开发根本不会用到自己写的版本。因为只有自己写过你才会明白 insert 到底在做什么、delete 为什么要把末尾清空、复杂度分析里的每一步到底对应哪一行代码。先看一个最基础的手写版本。不像 CPython 不需要你手动 malloc 和 free但“预留容量”和“已用长度”这两个概念依然要自己维护class SeqList: def __init__(self, capacity10): self.capacity capacity # 当前最多能存多少元素 self.data [None] * capacity # 底层数组先占好坑 self.length 0 # 当前实际元素个数 def is_empty(self): return self.length 0 def is_full(self): return self.length self.capacity def __len__(self): return self.length def __getitem__(self, index): if index 0 or index self.length: raise IndexError(index out of range) return self.data[index] def __setitem__(self, index, value): if index 0 or index self.length: raise IndexError(index out of range) self.data[index] valueself.data [None] * capacity这行就是在内存里申请一段连续空间。None在这里不是元素值而是“空位”的意思这在 Python 里很重要。数据结构的逻辑长度和物理容量是两码事数组长度 10不代表里面有 10 个逻辑元素只有self.length个。3.2 插入操作的位移陷阱顺序表的插入逻辑一句话就能说完把插入位置及其后面的所有元素都往后挪一位再把新元素放进去。但这句话落到代码里有三个坑。第一个坑是移动方向。插入时要“从后往前”移动否则前面的元素会覆盖后面的元素。假设数组是[1, 2, 3, 4]要在下标 1 插入99如果从前往后搬2被搬到3的位置时其实先把3覆盖了数据就丢了。正确做法是从最后一个元素开始搬到后一个位置再搬倒数第二个直到把插入位置空出来。第二个坑是循环边界。可以这样理解假设当前长度是 4要在下标 1 插入那么下标 3 的元素要搬到下标 4下标 2 的搬到 3下标 1 的搬到 2。所以range要从self.length - 1一路递减到index。第三个坑是越界判断。插入允许的位置范围是0到self.length含两端因为插到末尾是合法操作。如果传个负索引或者比 length 还大的数得主动抛异常而不是让底层数组悄悄出错。完整的插入代码如下def insert(self, index, value): if index 0 or index self.length: raise IndexError(index out of range) if self.is_full(): self._resize() for i in range(self.length, index, -1): self.data[i] self.data[i - 1] self.data[index] value self.length 1我在上课和带新人时反复强调range(self.length, index, -1)是在从最后一个元素开始逐个往后挪。你可以在草稿纸上画一个小数组手动模拟一遍。这个过程看似简单但真的有人会漏掉self.length这个初始位置导致最后一个元素平白无故丢了。3.3 删除操作的内存管理删除操作和插入正好相反从删除位置开始后面的元素依次往前挪覆盖掉要删除的那个位置最后让length减一。还是那个例子删除下标 0 的元素就是把下标 1 搬到 02 搬到 13 搬到 2。但 Python 手写时有一个点特别微妙数组里最后一个位置在逻辑删除后仍然可能残留着之前的引用。比如self.length从 4 减到 3 之后self.data[3]还指向原来第 4 个元素。在 C 语言里这只是一个无效的散落数据等着被新数据覆盖但在 Python 里它会让对象一直被引用无法被垃圾回收。所以删除操作的最后一步最好把腾出来的位置重新设置为Nonedef delete(self, index): if index 0 or index self.length: raise IndexError(index out of range) value self.data[index] for i in range(index, self.length - 1): self.data[i] self.data[i 1] self.length - 1 self.data[self.length] None # 释放引用 return value提示这一步对初学者来说可能感觉“多此一举”但是我实测下来在写一个大循环反复增删的测试脚本时如果不把末尾置None内存占用会肉眼可见地增长。Python 的引用计数在这种情况下才不会帮你及时回收对象。删除时还有一个小技巧越界判断是index self.length不是index self.length。因为删除位置必须确实存在元素删除length那个位置本身就是非法的。这个边界条件和插入的边界是两个完全不同的判断标准千万别搞混。3.4 按下标查找与按值查找顺序表最爽的体验就是按下标查找。前面说过因为内存连续按下标访问理论上就是一次地址运算和元素的个数无关。这是所有 O(1) 复杂度操作中最直白的一个。def index_of(self, value): for i in range(self.length): if self.data[i] value: return i return -1按值查找就没办法快了在没有额外结构比如哈希索引的前提下只能从前往后一个元素一个元素比对最坏的情况下要遍历完整张表时间复杂度 O(n)。Python 内置的list.index()底层做的是同一件事它并不是用了什么魔法。这里要顺带提一个很重要的概念内部实现顺序表存储的元素如果是对象引用那按下标访问拿到的是引用本身不是拷贝。如果你在__getitem__里直接return self.data[index]外部拿到引用后可以原地修改这个对象从而绕过顺序表改掉内部数据。在真实项目中这是特性不是 bug但如果你写的是封装性很强的类就要考虑返回副本。这个细节很多资料不提但面试被问到如何防止外部修改内部数据时这就是考点。3.5 扩容动态顺序表自我成长的关键一步前面写插入时调用了_resize()这一步就是动态顺序表最关键的灵魂——当数组满了你不能拒绝写入而应该申请一块更大的连续空间把所有旧数据搬过去然后释放旧数组。def _resize(self): new_capacity self.capacity * 2 new_data [None] * new_capacity for i in range(self.length): new_data[i] self.data[i] self.data new_data self.capacity new_capacity这里我选择“扩容为原来的 2 倍”这是最经典的策略。为什么是 2 倍而不是“1 个位置”假设每次只多申请一个位置那连续插入 n 个元素需要搬迁大约 n²/2 次均摊下来每次 append 是 O(n)整体是灾难性的慢。翻倍扩容则能让均摊成本降到 O(1)。那是不是倍数越大越好也不是如果用 10 倍扩容大部分时间内存被白白占着利用率低空间浪费严重。2 倍是空间和时间比较经典的折中点。如果元素本身特别大、内存压力高有人会用 1.5 倍扩容来减少空间浪费但带来的代价是均摊操作偶尔要搬迁更多次。这属于工程上的取舍笔试面试被问到为什么用 2 倍时主线答均摊 O(1) 空间利用率折中就不会跑偏。在实际 CPython 的实现里扩容策略会刻意考虑内存池的分配粒度不会简单地每次精确乘 2而是在ob_item分配时使用类似按需分配整块内存 预留一部分的方式。但作为数据结构学习先理解 2 倍扩容的核心逻辑就足够遍历所有考点。4. 复杂度分析与性能对比4.1 时间复杂度速查表学这个章节最忌讳的就是只看结论不推过程。下面这张表的每一条你都应该能用前面的代码推出来。操作顺序表数组链表说明按下标访问O(1)O(n)数组直接地址运算按值查找O(n)O(n)都需要遍历但常数不同头部插入O(n)O(1)已知前驱数组要全表后移尾部插入O(1) 均摊O(1)数组扩容均摊后是常数中间插入O(n)O(1)已知位置数组要搬后半段头部删除O(n)O(1)数组要全表前移尾部删除O(1)O(n)单向链表单向链表找前驱也要遍历你可能会问链表尾部删除在双向链表下也是 O(1) 啊为什么表格写 O(n)这就是我强调要基于具体实现聊复杂度的原因。手写单链表时你根本没有办法直接定位到倒数第二个节点必须从头遍历过去。所以任何复杂度结论都必须绑定具体的数据结构和实现细节这才是数据结构这门课真正想训练你的思维方式。4.2 空间复杂度与扩容策略顺序表的空间复杂度主要看两部分一是底层数组本身占用的空间二是逻辑上存储 n 个元素时是否有额外浪费。在不扩容的情况下顺序表空间复杂度是 O(n)非常干净。但动态扩容的顺序表就没这么简单了——数组容量是当前元素数量的上界如果频繁使用插一个删一个的模式容量可能会一直维持在高位造成空间的闲置浪费。举个真实例子你往 list 里连续 append 了一万个元素然后执行while len(lst) 1: lst.pop()把元素删到只剩一个。这时候 Python list 的allocated容量可能仍然是万级。虽然 Python 内部会在列表明显缩小时缩容具体的触发条件与版本相关list_resize或list_clear会根据allocated与size的比例判断但如果你想立刻释放内存更可靠的做法是显式lst []或者lst.clear()甚至创建新列表来彻底释放旧数组。这在写长驻内存的服务时尤为重要。另外有一个经典面试题已知顺序表容量是 n里面实际元素 m n请问空间复杂度是多少标准答案是 O(n) 还是 O(m)要看题目考察的是已分配的空间还是有效使用的空间。底层数组确实占用了 O(n) 的空间但有效数据只占 O(m)。理论上空间复杂度通常以实际存储开销为衡量所以更严谨说是 O(n)因为数组整体被分配了。这个细节建议在回答时直接点明别等面试官追问。5. 实操中常见的坑与排查技巧实录5.1 越界问题index out of range 不等于数据不存在这是新手写顺序表时最常撞的墙。当你连续 insert 很多次之后有时明明length和capacity都对一访问却报IndexError。我排查过很多次这类问题最后发现绝大多数都出在初始化之后的data与length不同步上。比如你可能在初始化时写了self.data []然后在 insert 里用self.data[i] value——空列表根本没有下标i一赋值就报错。正确的做法是初始化时用[None] * capacity预分配好位置这样下标赋值才有效。这个在 Python 里显得不自然但这就是顺序表预先留坑的本质。另一种常见是我在 3.1 里展示的__getitem__边界判断没写对导致访问data[length]时不报错拿到一个不该出现的None这种“静默失败”比报错更可怕因为它会让 bug 潜伏到很后面才暴露。5.2 扩容后的引用失效问题很多从 C 语言转过来的人会特别担心一件事数组扩容后原来拿到的指针是不是就失效了在 C 里确实会realloc之后旧地址可能不再有效所有旧的指针和迭代器都会变成危险的野指针。但在 Python 里你无需关心这个问题因为底层的PyListObject会在扩容后更新ob_item指针而你手里拿到的 list 对象引用始终是同一个对象。你可以做个实验构造一个列表记录它的id()然后不断 append 直到扩容再打印id()你会发现 id 始终不变。但这不意味着没有隐患。隐患在另一个层面——如果你在自定义类中手动管理下标引用比如记下了self.data[index]的引用扩容不会让这个引用失效元素对象本身还活着但如果你想模仿 C 的指针数组 局部缓存思路错误地保存了旧数组对象那扩容后旧数组被替换掉你保存的旧引用就会一直占着内存导致扩容白扩了。也就是说Python 的扩容对使用者透明是好事但你仍然要管理好自己的外部缓存不要让旧数组对象被局部变量长时间引用。5.3 元素移动方向搞反的排查方法我自己带过不少人写顺序表最常见的代码错误就是移动方向反了。插入时从前往后搬结果后半段数据全部被覆盖成同一个值删除时从后往前搬结果开头几个元素被覆盖旧值残留尾端。这类 bug 的特点是小规模测试可能看不出问题元素一多立刻炸。我的排查方法很简单在关键的for循环里打印每一步移动的状态。for i in range(self.length, index, -1): print(fmove data[{i - 1}] - data[{i}]) self.data[i] self.data[i - 1]打印几轮后你就能非常直观地看到插入时一定是先处理最后一个元素删除时一定是先处理最前面的元素。等你把这段代码写顺了后面学插入排序、希尔排序这种依赖相邻交换的算法时会非常顺。5.4 尽量用 Pythonic 的写法但别忘原理最后我特别想提醒一点手写顺序表是为了理解原理但在日常开发里不要重复造轮子。Python 内置的 list 已经是一个高度优化的动态顺序表它的 append、pop、切片操作都是 C 级别实现的性能远超你手写的版本。你要做的是学会在合适的时候用合适的方法# 尾部追加O(1) lst.append(x) # 尾部弹出O(1) lst.pop() # 按位置插入O(n) lst.insert(2, x) # 按位置删除O(n) lst.pop(2) # 原地反转O(n) lst.reverse()真正值得你动手写的是一些内置 list 没法直接提供、但又建立在顺序表思想上的结构比如循环队列、固定容量缓存、基于数组的栈与队列。我自己的学习路径就是先用 Python 手写一遍顺序表再用 Python 分别实现基于顺序表的栈和队列然后做力扣上的数组类题目。这一套下来数组相关的数据结构和复杂度分析会打通百分之七八十。5.5 我踩过的一个印象深刻的坑讲一个我上个月实际遇到的现场。当时我在写一个批量数据处理脚本第一版用的是lst [None] * n预先占位后来需求变化要动态往中间插入我图省事直接用了lst.insert()处理几万行数据时明显卡顿。一查才发现我在一个循环里频繁对中间位置做插入时间全部耗在元素搬移上了。说白了顺序表的中间插入是 O(n)我就用了 O(n²) 的算法。后来我换了思路因为中间插入的位置其实是有规律的我改成先用 list 收集所有数据最后统一做一次分片重组整体耗时下降了不止一个数量级。这说明什么数据结构的理论不是考试用的是写代码时真正能救命的。写在最后算法与数据结构学久了你会慢慢发现最基础的东西往往最值得反复琢磨。顺序表看起来只是数组包装了一下但只有亲手实现了扩容、插入、删除你才会真正理解为什么 Python 的 list 某些操作特别快、某些操作特别慢也才能在写代码时下意识避开 O(n²) 的陷阱。我个人在实际学习中的体会是这类内容别只看文档和视频也别满足于看懂别人写的代码一定要自己在编辑器里敲一遍、跑一遍、故意写错一遍再排查一遍。写错的那一次才是你真正长记性的一刻。如果你现在正卡在顺序表或者 Python 列表的底层机制上希望这篇整理能帮你把那层窗户纸捅破。动手写别停。