教很多次了学习顺序表之前先搞清楚“你在学什么”比什么都重要。顺序表在Python里几乎是无处不在的一个基础结构你天天在用list但很多人真到面试或者自己动手封装数据结构的时候突然就说不清楚它的底层是怎么回事了。这篇内容就专门把顺序表这件事讲透——从Python的list到底长什么样、内存怎么分配、扩容为什么会抖一下到怎么从零手写一个类似list的顺序表类再到实际写代码时最常见的坑和面试题怎么答。适合正在学数据结构与算法的学生、准备面试的开发者以及想补一补底层知识的Python使用者。1. 顺序表到底在学什么先搞清楚这个问题再动手1.1 数组、顺序表和Python list的关系顺序表的本质就一句话用一段连续的内存空间按顺序存储一系列相同类型的数据元素。它和“数组”基本是一回事只是“数组”更偏语言层面的概念而“顺序表”是数据结构层面的叫法。C语言里的int a[10]是数组Java里的int[] arr是数组Python里的list也是数组只不过它是个更高级的、能自动扩容的数组。很多人被绕晕是因为Python的list看起来不像传统数组。它能存整数、字符串、对象、还能混合存看着像“什么都能装”于是就觉得它和数组完全是两码事。但实际上Python的list从数据结构的角度看就是一个动态顺序表它只是在元素类型上做了泛化——它内部存的不直接是元素本身而是指向元素对象的指针所以看起来“什么都能装”。拿这个概念去套所有数据结构题很容易面试官问“Python list的底层结构是什么”答“动态数组顺序表对象引用”就比只回一个list要专业得多。顺序表是所有后续数据结构的地基它不只是一个存储方式更是一整套“如何管理连续内存”的方法论。1.2 为什么顺序表是数据结构入门第一课学树、图、哈希表之前大家都会先学顺序表和链表。原因是它俩代表了两条完全不同的存储思路连续存储和链式存储。顺序表靠地址连续实现随机访问链表靠指针相连实现灵活插入。两类结构的所有后续内容——栈、队列、堆、字符串匹配、邻接表全都能归到这两条主线里。顺序表的优势是随机访问快访问第i个元素复杂度O(1)。这也是它被广泛用于实现栈、队列、优先队列底层存储的根本原因。缺点也明显插入和删除尤其是中间位置的插入删除要搬移元素最坏O(n)而且空间需要预先分配或动态扩容扩容那一下代价不低。如果你理解了顺序表这套底层逻辑后面学Python的list为什么尾部append快、头部insert(0, x)慢、为什么切片会产生新列表、为什么pop()尾部是O(1)而pop(0)是O(n)就都不会是死记硬背而是自然推论。1.3 学习顺序表最需要建立的“地址思维”顺序表一个容易被忽略、但非常核心的概念是地址计算。所有顺序表的操作效率分析都跑不出一个公式第i个元素的存储地址 首地址 i × 单个元素占用的字节数我学的时候犯过一个典型的糊涂想当然认为元素越大访问越慢。后来才明白顺序表里访问任何位置的速度和元素本身的大小基本无关因为不管元素多大它的地址都是通过首地址加偏移量算出来的CPU直接通过这个算好的地址取数一次内存访问就完成不需要逐个找。这就是“随机访问”的意思——任意位置都是算术运算一次定位跟下标无关的距离。这个地址思维特别重要很多算法题例如用顺序表实现循环队列、用连续数组模拟堆结构本质上都是在用下标算地址。你在看别人代码时如果看到(rear 1) % capacity这种取模运算就该意识到这和顺序表地址计算是一家人。先把“元素和地址”这对关系建立起来顺序表的所有操作细节都会清楚很多。2. Python里list的存储结构自增容背后的设计取舍2.1 连续内存和非连续内存的本质差异C语言的数组一旦声明内存大小就固定了int a[100]; // 一旦创建a最多存100个intPython的list却可以随时append从来不用你操心容量。这是因为它背后是一个动态管理的连续数组Python解释器会在底层帮你申请内存、扩容、释放。但正是因为有了自动扩容很多人就不去关心内存的实际排布了。下面用Python的id()粗略验证一下连续内存的存在感data [10, 20, 30, 40] for i, v in enumerate(data): print(id(v))如果你运行这段代码会看到相邻元素的id(v)并不相邻。这就容易让初学者误以为list不是连续存储。这里要拆开看list容器本身连续地存着一批指针每个指针再指向一个“PyObject对象”而这些对象本身是分散在堆上的。所以list的“连续”不是指对象数据连续而是指那份存储指针的内存是连续的。数据结构里的顺序表学的是这个结构容器内部有一段连续的空间每个位置放了一个元素或者指向元素的指针。至于元素本体是不是紧挨着的那是Python对象模型的事和顺序表的逻辑模型不冲突。2.2 list扩容到底怎么发生的动态顺序表都会面临一个问题初始分配容量不够用了怎么办答案是——申请一块更大的新内存把旧元素整体搬过去。Python的list在初始化时会有一个容量当插入导致容量不够时它会按一定策略过度分配over-allocate申请比实际需要更大的空间这样下次追加就不用立刻再扩容。具体扩容倍数不是固定的2倍解释器会根据元素数量计算出一个近似值整体上趋近于在“空间浪费”和“频繁扩容”之间找平衡。可以粗略地理解成新容量 ≈ 原容量 原容量 3即增长约1/8整体约1.125倍我实际测试过往一个空list里连续append100万个元素中间扩容的次数大概在几十次量级均摊下来每次append的时间复杂度依然接近O(1)。这就是常说的均摊O(1)。这个扩容设计很聪明。如果每次append都精准分配“只够一个元素”的空间那么每加入一个元素都要搬一次家插入n个元素的总代价会变成O(n^2)。而一次容量翻倍或增加1/8让前面很多次append都不需要搬移总代价摊到每次操作上就是常数级别。2.3 为什么Python list里存的是指针而不是元素本体C语言数组int a[10]里每个格子直接放整数本身而Pythonlist里每个格子放的是一个8字节的指针64位系统上指针再指向真实对象。这个设计带来一个很直接的结果Python list不能像C数组那样存原始类型值一切都被包成了对象。但指针带来的另一个优势是类型不再受限。因为每个格子都是指针指针本身不区分类型指向的是整数还是字符串还是自定义对象都行。代价是多了一层间接寻址访问比C数组稍慢每个元素都是PyObject内存开销明显增大对数值计算不友好所以科学计算会用numpy.ndarray代替list面试里如果被问到底层区别能说到这个层次就很稳了list是“类型可泛化的顺序表”而array.array和numpy.ndarray是“更贴近C数组的紧凑顺序表”。理解了这些很多实际问题例如“为什么大列表用numpy存能省那么多内存”、“为什么Python list存几百万个整数会占很多内存”瞬间就有答案了。3. 手写一个可用的顺序表类从0到1复现list核心逻辑3.1 先定义容量和长度的关系看代码之前先分清两个概念容量capacity底层连续内存当前最多能放多少元素长度length / size当前实际存放的元素个数新手写顺序表最容易只记得维护长度、忘记容量。没有容量这个变量你将无法判断什么时候该扩容、什么时候下标访问越界。所以顺序表类的第一件事就是把这两个东西分开。class SeqList: def __init__(self, capacity10): self.capacity capacity # 当前容量 self.length 0 # 当前元素个数 self._data [None] * capacity # 预分配固定容量的存储区这里用[None] * capacity做一个预分配。在Python里这只是拿同一个None重复填充但作为占位符完全没问题。真实的list内部其实也是类似思路先申请一段空内存真正填值的时候才往里面塞对象。3.2 按下标读写与越界检查顺序表第一个核心操作是“随机访问”——按下标读取和修改。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] value这里的判断条件是检查index self.length而不是index self.capacity。原因很直接长度是“有效元素”的终点容量只是“能装多少”的天花板。一个容量10、长度3的list下标3、4、5这些位置虽然内存是存在的但对你来说它们还不是有效元素不允许读写。实际用的时候会有一个容易忽略的小点Python原生的list支持负数下标比如a[-1]取最后一个元素。手写的顺序表如果想要支持负数下标可以在入口处做一次转换def _normalize_index(self, index): if index 0: index self.length if index 0 or index self.length: raise IndexError(index out of range) return index这样既保留了Python风格又不破坏边界检查的逻辑。我在自己实现的时候通常都会加这个因为很多场景往顺序表里传负下标是硬需求。3.3 插入和删除的搬移过程插入操作是顺序表的核心难点。理解了一句话就全通了从后往前搬。如果要在下标pos处插入新元素value为了保证连续存储必须把原来pos到最后的所有元素整体往后挪一位空出pos位置再放入value。为什么从后往前搬因为从前往后搬的话前面的元素还没挪走后面的位置就已经被覆盖了数据就丢了。def insert(self, pos, value): if pos 0: pos 0 if pos self.length: pos self.length if self.length self.capacity: self._resize(self.capacity * 2 1) # 扩容 for i in range(self.length, pos, -1): self._data[i] self._data[i - 1] # 从后往前搬 self._data[pos] value self.length 1range(self.length, pos, -1)就是从length倒着走到pos 1每次把前一个位置的值赋给当前空位。等全部搬完pos位置就空出来了。删除操作正好相反从前往后搬。删掉pos位置后要把后面的元素整体往前挪一位把空位补上最后把最后一个位置置空并减少长度。def remove(self, pos): if pos 0 or pos self.length: raise IndexError(index out of range) value self._data[pos] for i in range(pos, self.length - 1): self._data[i] self._data[i 1] # 从前往后搬 self.length - 1 self._data[self.length] None # 释放最后一个位置的引用 return value删除后把末尾位置设为None是很有必要的。如果不置空这个位置仍然持有旧对象引用可能导致对象无法被垃圾回收造成内存迟迟不释放的问题。实际Python的list删除元素后有时也会把空出的槽位清理掉保持引用干净。3.4 扩容策略翻倍、加1还是加固定值插入前检查容量如果满了必须扩容。常见的扩容策略有三种策略行为均摊复杂度空间浪费每次加1容量每次只能多放1个元素O(n)几乎不浪费每次加固定值k容量增加固定额度O(n)中等每次翻倍或乘系数容量按比例增加O(1)均摊较多为什么“每次加1”的均摊复杂度是O(n)因为每插一个元素都要扩容一次、搬移所有旧元素n次插入累计搬移约12...n O(n^2)均摊到每次就是O(n)。实践中没人这么写只是为了教学对比。翻倍策略的均摊复杂度是O(1)因为扩容次数大约只有log n次且每次扩容后都能支撑一批新插入。空间上最多浪费一半如果翻倍但换取的是极低的插入代价。Python的list没采用严格翻倍而是采用约1.125倍的过分配策略目的是在内存利用率和扩容次数之间做更好的平衡。手动实现的话我建议直接翻倍甚至1.5倍逻辑简单且效果好def _resize(self, new_capacity): 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这里有一个想当然的坑扩容时用new_data self._data [None] * (new_capacity - self.capacity)能不能替代循环能但语义上和“新建空间逐元素拷贝”效果相同本质上都是O(n)。如果追求可读性直接用循环更规矩因为它把“逐块搬运”这个核心过程显式暴露出来比拼接花活更贴近数据结构教材里的做法。4. 增删查改的复杂度与实操中的效率差异4.1 各操作的时间复杂度表顺序表的所有复杂度都建立在“连续存储”这个前提上。总体结论先放这儿操作平均时间复杂度说明按下标访问O(1)地址直接计算与位置无关按下标修改O(1)同访问尾部插入 append均摊O(1)大部分时候直接写末尾偶尔扩容搬移头部插入 insert(0)O(n)所有元素整体后移中间插入O(n)平均移动n/2个元素尾部删除 pop()O(1)长度减一即可头部删除 pop(0)O(n)所有元素整体前移按下标删除O(n)平均移动n/2个元素查找某个值O(n)顺序遍历除非额外建立索引这个表很值得背但要理解着背。所有O(n)操作都来自同一个根源——为了保持“地址连续”你不得不搬移元素。只要存储逻辑还是顺序表这个代价就躲不掉。4.2 为什么Python的append快、insert(0)慢用上面这张表去解释Python的实际表现几乎是零成本lst [] for i in range(100000): lst.insert(0, i) # 很慢每次insert(0, i)都要把所有元素往后挪一位10万次插入的总移动次数大约是12...100000 ≈ 5×10^9这个量级即便在Python底层C代码上也扛不住。而lst [] for i in range(100000): lst.append(i) # 很快这是每次都往尾部塞一个元素大多数时候直接在末尾写指针就行偶尔扩容一次搬移全部均摊下来每次操作非常便宜。实操中一个高频反模式是“用list模拟队列”queue [] # 入队 queue.append(x) # 出队 head queue.pop(0) # 每次O(n)元素少时无所谓一旦队列到几万条数据出队的耗时就会肉眼可见地卡起来。标准替代方案是collections.deque它内部用块状链表实现popleft()是O(1)from collections import deque queue deque() queue.append(x) # 入队 head queue.popleft() # 出队 O(1)4.3 切片为什么会是新列表复制的那点事儿另外一个经常被忽略的复杂度坑是切片a list(range(100000)) b a[:] # 复制出整个新listO(n) c a[50000:] # 后半段复制约O(n/2)切片操作在Python里会创建一个新列表并把范围内的元素指针一个一个地拷贝过去。这意味着a[:]的复杂度不是O(1)而是O(n)。如果你只是为了“看一眼子区间”却生成了整个切片列表在超大列表上代价不小。不想复制的话可以改用itertools.islice做惰性迭代只在真正需要数据时才取出来。同时要注意切片复制的是指针不是对象本身。所以切片后修改元素内容有时会影响原列表中的对象a [[1, 2], [3, 4]] b a[:] b[0][0] 99 print(a[0][0]) # 99因为b和a共享内层list对象这属于“浅拷贝”的经典表现。真正要做“深拷贝”得用copy.deepcopy但代价更大通常不推荐轻易使用。5. 顺序表的真正用武之地什么时候就该选它5.1 优先选择顺序表的三大场景顺序表不是万能的但以下三类场景它几乎是默认最优解第一需要高频随机访问。比如按索引读取第i个元素无论i多大都能一次定位。实现“数组模拟栈”、“数组模拟队”、“邻接矩阵”这些基础算法顺序表天生合适。第二需要连续遍历且频繁尾插尾删。维护一个动态缓冲、日志队列、待处理任务列表时核心操作几乎都发生在尾部顺序表的“尾部追加尾部弹出”组合几乎完美均摊O(1)。第三元素数量可预估且申请后很少发生中部插入删除。比如读配置文件时一行一个配置项处理完就结束数量在加载前就能估算。此时顺序表省去了链表每节点维护指针的额外空间。实际项目中一个典型例子是“维护排行榜”榜单固定显示前50名每次插入新成绩后需要排序排序时因为随机访问是O(1)各种快排、堆排都能直接利用顺序表的高效访问特性。换成链表排序快排反而很难跑起来因为链表访问中间元素是O(n)。5.2 顺序表和链表怎么选不要只背“插入删除选链表”教科书喜欢说“链表适合插入删除顺序表适合随机访问”。这个说法方向没错但容易误导人。真正实操时链表的“插入删除O(1)”是指在已知节点位置的前提下的O(1)而顺序表的“插入删除O(n)”是包括“查找位置”在内的最坏代价。如果你插入位置已经确定了例如维护一个队列尾部的指针那链表尾插确实是O(1)。但如果你要“找到某个值再删除”链表需要先遍历找到目标一样是O(n)。这种情况下顺序表和链表的第一步都是O(n)查找但顺序表还有随机访问的优势排序、二分查找都更方便。所以更贴近工程的说法是元素数量变化大、频繁在中间插入删除 → 优先考虑链表元素规模大且需要随机访问、排序、二分 → 优先顺序表两者边界模糊时 → 测一下真实性能别凭记忆背结论5.3 Python开发里最常见的三个顺序表坑第一个坑是用list存海量数值。前面提过每个元素是独立对象内存开销极大。10万个整数看起来不多实际每个PyObject可能占用28字节左右加一起就是2.8MB而同样数量的C数组只要0.4MB。如果数据量上百万差距更大。改进方式是换array.array(i)或numpy.ndarray它们才是真正的紧凑顺序表。第二个坑是频繁insert(0, ...)。很多业务里需要“最新数据放最前”直接insert(0, item)写起来顺手但到数据规模变大时性能雪崩。替代办法是反过来append最后取用时再reverse或切片反转或者直接用deque。第三个坑是误用list做固定大小的环形缓冲。有些场景希望队列满了以后覆盖最旧数据用顺序表实现时如果不控制长度一直append会导致无限增长。正确姿势是预先分配固定空间用头尾指针取模来模拟环形队列。这种实现格外考验“地址计算”那节课的基本功。6. 面试和笔试里的顺序表高频考点与答题模板6.1 手写题最常考的三种存活面试中顺序表类手写题出镜率很高主要围绕三个题型题型一实现动态数组类。要求提供push_back、pop_back、insert、remove、size、capacity等接口并保证扩容正确。答题时注意容量变化必须和长度分开维护insert时越界缩小到首尾扩容用循环搬运而非直接复制有些语言直接复制也行但体现不出你理解过程。题型二使用顺序表实现栈。栈只需要尾插尾删顶元素访问用顺序表实现是天然匹配。关键点是判断“栈空”用length 0而“入栈时是否需要扩容”用length capacity。class Stack: def __init__(self, capacity10): self._data [None] * capacity self._capacity capacity self._length 0 def push(self, value): if self._length self._capacity: self._resize(self._capacity * 2) self._data[self._length] value self._length 1 def pop(self): if self._length 0: raise IndexError(pop from empty stack) self._length - 1 value self._data[self._length] self._data[self._length] None return value题型三顺序表的合并与去重。合并两个有序顺序表要求结果依然有序。经典双指针做法从两个表头依次比较较小的先放入新表。注意最后要处理一个表剩余的元素。def merge_sorted(a, b): i j 0 result [] while i len(a) and j len(b): if a[i] b[j]: result.append(a[i]) i 1 else: result.append(b[j]) j 1 result.extend(a[i:]) result.extend(b[j:]) return result6.2 复杂度分析题会怎么挖坑面试官常把复杂度问到两个容易出错的细节第一个是“尾部append的均摊复杂度为什么是O(1)”。答题关键是讲清“扩容次数少 每次扩容分摊到大量元素上”。假设初始容量1按2倍扩容到n扩容次数约log n每次搬移的元素总数不超过2n因此总代价O(n)均摊每个append的代价O(1)。第二个是“为什么删除中间元素也是O(n)”。注意顺序表的删除本身已经包含“搬移后续所有元素”这一步和“查找”无关。如果题目是“删除指定值的元素”那还得叠加一次O(n)的查找总复杂度依然是O(n)但前后两个O(n)不是一个含义。答这种题要拆开步骤讲先找再删两步都是O(n)总体O(n)。还有一个容易忽略list的index(value)查找是O(n)。就算Python底层优化得很快它本质还是线性扫描。如果需要在大量数据里频繁按值查找正确解法是额外维护一个哈希索引dict把时间复杂度从O(n)降到O(1)平均。别指望顺序表本身提供快速查找能力。6.3 在纸上手写顺序表时容易忽略的三个细节参加笔试手写顺序表很多人逻辑对但小错误不断。我最常看到的三类是扩容后忘记更新capacity。_resize里更新了新数组但容量没同步下次插入时又触发扩容性能就崩了。插入和删除时的边界条件写错。插入时允许pos length即插入尾部删除时不允许pos length。这个不对称经常被搞混。删除后没有清空末尾引用。对Python这种带垃圾回收的语言来说末尾残留引用可能导致内存暂不释放。虽然逻辑结果上长度已经变化访问不到那个位置但底层引用还在数据量大时会有内存问题。纸上写码时我建议养成三步检查习惯先看长度和容量的判断、再看循环搬运的边界、最后看是否同步更新了length与capacity。这三个地方至少有一个出错几乎是所有顺序表bug的高发区。7. 顺序表的进阶玩法不只是入门课的一张“简单表”7.1 用顺序表实现循环队列本质是一套地址回转循环队列为什么和顺序表有关因为它是“固定容量顺序表 头尾指针绕圈”的组合。数组长度固定头尾指针移动后用取模运算实现“转圈”class CircularQueue: def __init__(self, capacity): self._data [None] * (capacity 1) self._capacity capacity 1 self._head 0 self._tail 0 def enqueue(self, value): if (self._tail 1) % self._capacity self._head: raise RuntimeError(queue is full) self._data[self._tail] value self._tail (self._tail 1) % self._capacity def dequeue(self): if self._head self._tail: raise RuntimeError(queue is empty) value self._data[self._head] self._head (self._head 1) % self._capacity return value常见实现里故意浪费一个空间来区分“空”和“满”。如果不用这招就得额外维护一个size变量。面试时两种方案都能说但一定要说清楚你如何判断“空/满”这比背代码更重要。循环队列看起来比普通顺序表复杂本质就是在地址计算上做取模。一旦理解顺序表的“首地址偏移量”公式循环队列就是给偏移量套了个环形的取模而已。7.2 连续数组模拟堆结构完全二叉树的层序存放二叉堆常被实现成“顺序表”形式堆顶在arr[0]某个节点在下标i则左孩子在下标2*i1右孩子在2*i2父节点在(i-1)//2。这种存储方式完全不靠指针只靠下标关系把树“压扁”进数组。def parent(i): return (i - 1) // 2 def left(i): return 2 * i 1 def right(i): return 2 * i 2为什么堆适合顺序表因为堆的核心操作是上浮和下沉每次都只需要访问当前节点和它的父子节点而这些节点的下标都是可算的。不需要随机访问“任意”节点但需要频繁根据父/子下标跳到指定位置这正是顺序表的强项。如果用链表存堆父子关系虽然也能表达但每次交换都得重新指向节点代码复杂很多而且节点分散在内存各处缓存友好性差。因此绝大多数语言里优先队列heapq的底层都是顺序表。7.3 平衡时间与空间的取舍缩容要不要做很多顺序表实现只关心扩容不关心缩容。比如一个大列表曾经装过1000万元素后来清空到只剩几个底层仍然保留着一大块申请来的内存。这块内存如果一直不释放对长驻进程来说就是个隐患。所以标准的动态数组设计应该考虑当length降到capacity的某个比例以下时触发缩容比如1/4。缩容不是缩小一半就完比较好用的策略是if self.length self.capacity // 4 and self.capacity 16: self._resize(self.capacity // 2)注意加了capacity 16这个下限。如果容量已经很小还反复缩容扩容会导致抖动——刚缩完又追加元素马上又扩容白白造成内存搬移。给缩容设置一个阈值可以让扩容和缩容之间留出足够缓冲。Python的list实际也有类似机制但它的缩容并不总是一下子释放解释器会综合考虑性能和内存占用。手写数据结构时这套“缩容阈值下限”的逻辑一定要加上不然就是只进不出。8. 在Python里写顺序表代码的工程注意事项8.1 避免用while循环搬移元素时的索引错误手写搬移循环时很容易出现差一错误。以删除为例正确的搬移范围是pos到length - 2把data[i1]赋给data[i]。如果写成range(pos, self.length)最后一次会尝试读取data[length]而那个位置可能越界。如果实在拿不准边界我用过一个笨但有效的验证法写完后构造一个小列表如[1, 2, 3, 4]手动在纸上推演插入/删除到第0位、第末尾、中间三个位置把每一步的下标变化写出来。推演过两三遍之后边界就基本不会错了。8.2 不要用拼接来扩容有一个看起来挺好用但实际有隐患的写法self._data self._data [None] * extra表面效果没问题但它生成了一个新列表并且需要先复制旧列表的所有指针。虽然逻辑上等价于“扩容”但表达上不如显式的_resize清晰。更重要的是如果你是在原列表上做self._data [None] * extra这个操作在Python里是原地扩展虽然效率高一些但通常不用于数据结构教学里的“扩容”演示因为它隐藏了“重新申请内存并搬运”这个关键过程。学数据结构时显式的搬迁代码有价值它能让你直观感受到扩容的代价。工程上你用哪个都行但面试和写教学代码时建议用_resize这种清晰的做法。8.3 类型提示和接口设计让顺序表看起来像内置list写顺序表类时我习惯把它做的像个“嫡系list”实现__len__、__getitem__、__setitem__、__iter__、__contains__这些魔法方法。这样使用者可以直接用len(obj)、obj[i]、for x in obj而无须调用一堆自定义方法。对读者来说这种体验也更接近原生list。class SeqList: ... def __len__(self): return self.length def __iter__(self): for i in range(self.length): yield self._data[i] def __contains__(self, value): return value in self._data[:self.length]加上__iter__后顺序表就能直接用于遍历和列表推导seq SeqList(5) seq.append(1) seq.append(2) seq.append(3) squares [x * x for x in seq]这样做的好处是代码可读性大幅提升也更贴近Python生态的风格。数据结构不该只是“会做题”更应该能顺手用在真实项目里。9. 看着“简单”的顺序表为什么值得写一整个完整实现9.1 写过一遍之后list的很多行为自然就理解透了很多人问我“list不香吗为何要自己写一遍顺序表”我的回答永远是自己写一遍以后你对Python list的很多奇怪行为就不再会觉得奇怪了。例如为什么a b是对比元素值而非内存地址因为list实现了__eq__而顺序表类比着实现类似逻辑也很顺手。为什么b a后修改b会影响a因为赋值的只是引用底层数据还是同一个对象。为什么c a[:]后修改c的元素不影响a但修改c里嵌套对象的字段会影响a因为切片复制了指针嵌套对象还是同一个。这些问题的答案如果只是背结论很快会忘。但当你把SeqList从0到1实现一遍你会清晰地看到每个操作的“搬运”和“复制”动作发生在哪里上述所有行为全部能自己推导出来。9.2 一次完整的实现代码参考最后给一个相对完整的SeqList参考实现其中包含前面提到的容量管理、扩容、缩容、遍历、切片的简单支持可以直接用来练习或作为面试手写题的参考底稿class SeqList: def __init__(self, capacity10): if capacity 1: raise ValueError(capacity must be positive) self.capacity capacity self.length 0 self._data [None] * capacity def _normalize_index(self, index): if index 0: index self.length if index 0 or index self.length: raise IndexError(index out of range) return index def _resize(self, new_capacity): new_data [None] * new_capacity move_len min(self.length, new_capacity) for i in range(move_len): new_data[i] self._data[i] self._data new_data self.capacity new_capacity def __len__(self): return self.length def __getitem__(self, index): return self._data[self._normalize_index(index)] def __setitem__(self, index, value): self._data[self._normalize_index(index)] value def append(self, value): if self.length self.capacity: self._resize(self.capacity * 2 1) self._data[self.length] value self.length 1 def insert(self, pos, value): if pos 0: pos max(0, self.length pos) pos min(pos, self.length) if self.length self.capacity: self._resize(self.capacity * 2 1) for i in range(self.length, pos, -1): self._data[i] self._data[i - 1] self._data[pos] value self.length 1 def remove(self, pos): pos self._normalize_index(pos) value self._data[pos] for i in range(pos, self.length - 1): self._data[i] self._data[i 1] self.length - 1 self._data[self.length] None if self.capacity 16 and self.length self.capacity // 4: self._resize(self.capacity // 2) return value def pop(self): return self.remove(self.length - 1) def __iter__(self): for i in range(self.length): yield self._data[i] def __repr__(self): return fSeqList({[self._data[i] for i in range(self.length)]})这个实现不算很长但扩容、缩容、边界处理、魔法方法都有。把它跑通一遍顺手写几个测试s SeqList(4) for i in range(8): s.append(i) assert len(s) 8 assert s[0] 0 and s[-1] 7 s.insert(0, 99) assert s[0] 99 and s[1] 0 s.remove(0) assert s[0] 0 print(all tests passed)这些测试覆盖了扩容、负数索引、头部插入、头部删除几个关键路径跑通后你的实现基本不会有太明显的问题。9.3 写完之后还能做哪些有趣的扩展如果基础版跑通了你还有余力可以考虑几个有意思的扩展第一个是增加“按值查找”def index(self, value): for i in range(self.length): if self._data[i] value: return i raise ValueError(value not in sequence)第二个是支持切片返回新对象def __getitem___slice(self, start, stop, step): # 返回一个新的SeqList或list indices range(start, stop, step) result SeqList(len(indices)) for i in indices: result.append(self._data[self._normalize_index(i)]) return result第三个是增加元素去重、排序后合并等算法操作。这些题都是经典笔试题目在自建顺序表类上练习一次对后续学习排序和二分查找都很有帮助。我自己在实际项目中并不会频繁去手写顺序表但每次写完一个基础数据结构的完整实现再回头读源码或者做算法题手感都会明显不一样。这东西就像打地基——你当然可以永远用现成的list但地基打得越扎实上层建筑盖得越轻松。磨刀不误砍柴工顺序表这一个完整实现值得花一个下午认认真真写一遍。