Python 算法基础篇之列表

一、列表的本质：动态数组

1.1 不要被名字迷惑

Python 的list不是链表（Linked List），而是动态数组（Dynamic Array）—— 是一段连续内存中存储的变长序列。

内存布局示意： 索引: 0 1 2 3 4 5 ┌──────┬──────┬──────┬──────┬──────┬──────┐ 值: │ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ └──────┴──────┴──────┴──────┴──────┴──────┘ ↑ ↑ 起始地址 已用末尾 ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐ 预分配: │ 已用 │ 已用 │ 已用 │ 已用 │ 已用 │ 已用 │ 空闲 │ 空闲 │ └──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘ 当前容量 capacity = 8

关键特性：

• 元素在内存中连续存储→ 支持 O(1) 随机访问
• 容量（capacity）≥ 长度（size）→ 预留空间减少扩容频率
• 扩容时重新分配内存+批量复制元素→ 均摊 O(1) 尾部插入

1.2 操作复杂度速查

⚠️关键警示：pop(0)和insert(0, x)是 O(n) 操作！频繁头部操作请用collections.deque。

二、基础操作：创建与访问

2.1 创建列表的六种方式

# 方式1：字面量（最常用）lst1=[1,2,3,4,5]# 方式2：list() 构造函数lst2=list(range(5))# [0, 1, 2, 3, 4]lst3=list("abc")# ['a', 'b', 'c']# 方式3：列表推导式（Pythonic）lst4=[x**2forxinrange(5)]# [0, 1, 4, 9, 16]# 方式4：乘法初始化（注意陷阱！）lst5=[0]*5# [0, 0, 0, 0, 0]# ⚠️ 陷阱：[[]] * 3 创建3个引用同一列表的引用wrong=[[]]*3wrong[0].append(1)# [[1], [1], [1]] —— 不是预期的[[1], [], []]！# 正确做法：列表推导式创建独立对象correct=[[]for_inrange(3)]correct[0].append(1)# [[1], [], []] ✅# 方式5：从可迭代对象生成lst6=list(map(int,["1","2","3"]))# [1, 2, 3]# 方式6：条件过滤lst7=[xforxinrange(10)ifx%2==0]# [0, 2, 4, 6, 8]

2.2 索引与切片：Python 最强大的序列操作

lst=[0,1,2,3,4,5,6,7,8,9]# 基础索引lst[0]# 0 —— 第一个lst[-1]# 9 —— 最后一个lst[3]# 3 —— 正数索引从0开始# 切片 [start:end:step]lst[2:5]# [2, 3, 4] —— 左闭右开lst[:3]# [0, 1, 2] —— 从头开始lst[7:]# [7, 8, 9] —— 到末尾lst[:]# [0..9] —— 复制整个列表lst[::2]# [0, 2, 4, 6, 8] —— 步长2lst[::-1]# [9, 8, ..., 0] —— 反转！lst[8:3:-1]# [8, 7, 6, 5, 4] —— 反向切片# 切片赋值（原地修改）lst[2:5]=[20,30]# [0, 1, 20, 30, 5, 6, 7, 8, 9]lst[::2]=[0,0,0,0,0]# 步长切片赋值，长度必须匹配# 删除切片dellst[2:5]# 删除索引2到4的元素

切片索引的心算公式：

lst[start:end:step] - step > 0：从左到右，取 start ≤ i < end - step < 0：从右到左，取 start ≥ i > end - 省略 start：step>0时从0开始，step<0时从末尾开始 - 省略 end：step>0时到末尾，step<0时到开头

三、添加与删除：算法场景中的选择

3.1 尾部操作：O(1) 的黄金区域

lst=[1,2,3]# 追加单个元素lst.append(4)# [1, 2, 3, 4] —— O(1) 均摊# 追加多个元素（可迭代对象）lst.extend([5,6])# [1, 2, 3, 4, 5, 6] —— O(k)，k为追加数量# 合并两个列表（创建新列表）new_lst=lst+[7,8]# O(n+k)，空间 O(n+k)# 弹出尾部last=lst.pop()# 返回 6，lst 变为 [1, 2, 3, 4, 5] —— O(1)

3.2 头部与中间操作：O(n) 的陷阱

lst=[1,2,3,4,5]# 头部插入：O(n) —— 所有元素后移lst.insert(0,0)# [0, 1, 2, 3, 4, 5]# 中间插入：O(n-i)，i为插入位置lst.insert(3,99)# [0, 1, 2, 99, 3, 4, 5]# 头部弹出：O(n)first=lst.pop(0)# 返回 0，O(n)# 中间删除：O(n-i)lst.pop(3)# 删除索引3的元素，返回 99# 按值删除：O(n) 查找 + O(n) 删除lst.remove(3)# 删除第一个值为3的元素，找不到抛 ValueError

算法场景中的替代方案：

3.3 删除所有匹配元素的正确姿势

# ❌ 错误：遍历中删除会导致索引错乱lst=[1,2,1,3,1]fori,xinenumerate(lst):ifx==1:lst.pop(i)# 漏删！索引后移导致跳过元素# ✅ 正确1：倒序删除（不影响前面元素的索引）lst=[1,2,1,3,1]foriinrange(len(lst)-1,-1,-1):iflst[i]==1:lst.pop(i)# [2, 3]# ✅ 正确2：列表推导式过滤（创建新列表）lst=[1,2,1,3,1]lst=[xforxinlstifx!=1]# [2, 3]# ✅ 正确3：while + remove（删除所有匹配，直到找不到）lst=[1,2,1,3,1]while1inlst:lst.remove(1)# [2, 3]，但 O(n²)，大数据量慎用

四、列表推导式：Python 的算法加速器

4.1 基础语法

# 基本形式[x**2forxinrange(5)]# [0, 1, 4, 9, 16]# 带条件过滤[xforxinrange(20)ifx%3==0]# [0, 3, 6, 9, 12, 15, 18]# 多重循环（笛卡尔积）[(i,j)foriinrange(3)forjinrange(3)]# [(0,0), (0,1), (0,2), (1,0), ..., (2,2)]# 带 else 的三元表达式["even"ifx%2==0else"odd"forxinrange(5)]# ['even', 'odd', 'even', 'odd', 'even']

4.2 算法中的应用

LeetCode 1. 两数之和：用列表推导式快速生成结果

deftwo_sum(nums:list[int],target:int)->list[int]:seen={}# 值 → 索引fori,numinenumerate(nums):complement=target-numifcomplementinseen:return[seen[complement],i]seen[num]=ireturn[]

矩阵转置：一行代码

matrix=[[1,2,3],[4,5,6]]transposed=[[row[i]forrowinmatrix]foriinrange(len(matrix[0]))]# [[1, 4], [2, 5], [3, 6]]

扁平化嵌套列表：

nested=[[1,2],[3,4],[5,6]]flat=[xforsublistinnestedforxinsublist]# [1, 2, 3, 4, 5, 6]

4.3 性能对比：推导式 vs 循环

importtime n=1_000_000# 方式1：for循环start=time.time()result1=[]foriinrange(n):result1.append(i*2)t1=time.time()-start# 方式2：列表推导式start=time.time()result2=[i*2foriinrange(n)]t2=time.time()-start# 方式3：mapstart=time.time()result3=list(map(lambdax:x*2,range(n)))t3=time.time()-startprint(f"for循环:{t1:.3f}s")print(f"列表推导:{t2:.3f}s")# 通常最快print(f"map:{t3:.3f}s")

结论：列表推导式通常比for循环快 1.5~2 倍（字节码优化），比map+lambda更易读。

五、排序与搜索：算法核心

5.1 内置排序：Timsort

lst=[3,1,4,1,5,9,2,6]# 原地排序（稳定排序，O(n log n)）lst.sort()# [1, 1, 2, 3, 4, 5, 6, 9]lst.sort(reverse=True)# [9, 6, 5, 4, 3, 2, 1, 1]# 按自定义key排序words=["banana","pie","Washington","book"]words.sort(key=len)# ['pie', 'book', 'banana', 'Washington'] —— 按长度# 返回新列表（不修改原列表）new_lst=sorted(lst,key=lambdax:-x)# 降序# 多条件排序students=[("Alice",25),("Bob",20),("Alice",20)]students.sort(key=lambdax:(x[0],x[1]))# 先按名字，再按年龄

Timsort 特性：

• 稳定排序（相等元素保持原相对顺序）
• 最坏 O(n log n)，最好 O(n)（已接近有序时）
• 混合了归并排序和插入排序

5.2 二分查找：bisect 模块

importbisect lst=[1,3,3,5,7,9]# 查找插入位置（保持有序）bisect.bisect_left(lst,3)# 1 —— 3的左侧插入位置bisect.bisect_right(lst,3)# 3 —— 3的右侧插入位置bisect.bisect(lst,3)# 3 —— 同 bisect_right# 插入并保持有序（O(n)，因为需要移动元素）bisect.insort_left(lst,4)# [1, 3, 3, 4, 5, 7, 9]bisect.insort_right(lst,3)# [1, 3, 3, 3, 4, 5, 7, 9]

应用场景：维护动态有序列表，频繁查询排名/前驱/后继。

六、深拷贝与浅拷贝：隐蔽的bug

importcopy# 浅拷贝：复制容器，不复制内部对象lst1=[[1,2],[3,4]]lst2=lst1.copy()# 或 lst1[:], list(lst1)lst2[0][0]=99print(lst1)# [[99, 2], [3, 4]] —— 被修改了！# 深拷贝：递归复制所有对象lst3=copy.deepcopy(lst1)lst3[0][0]=100print(lst1)# [[99, 2], [3, 4]] —— 不受影响# 不可变元素的列表，浅拷贝足够simple=[1,2,3]s_copy=simple.copy()s_copy[0]=99print(simple)# [1, 2, 3] —— 不受影响

判断标准：列表元素是否可变（列表、字典、对象）？是 → 需要深拷贝。

七、列表 vs 其他数据结构

八、算法实战：列表在 LeetCode 中的应用

8.1 双指针技巧

defremove_duplicates(nums:list[int])->int:""" 26. 删除有序数组中的重复项 双指针：慢指针指向写入位置，快指针扫描 """ifnotnums:return0slow=0forfastinrange(1,len(nums)):ifnums[fast]!=nums[slow]:slow+=1nums[slow]=nums[fast]returnslow+1# 新长度

8.2 前缀和

defsubarray_sum(nums:list[int],k:int)->int:""" 560. 和为 K 的子数组 前缀和 + 哈希表 """fromcollectionsimportdefaultdict count=defaultdict(int)count[0]=1prefix=0ans=0fornuminnums:prefix+=num ans+=count[prefix-k]count[prefix]+=1returnans

8.3 滑动窗口

defmax_sliding_window(nums:list[int],k:int)->list[int]:""" 239. 滑动窗口最大值 单调队列 """fromcollectionsimportdeque result=[]q=deque()# 存索引，保持单调递减fori,numinenumerate(nums):whileqandq[0]<=i-k:q.popleft()whileqandnums[q[-1]]<num:q.pop()q.append(i)ifi>=k-1:result.append(nums[q[0]])returnresult

九、核心心法

1. 复杂度条件反射
看到pop(0)立即想到 O(n)，看到append()想到 O(1) 均摊。这是写出高效 Python 算法的第一步。

2. 推导式优先
能用列表推导式就不用 for 循环，能用生成器表达式就不用列表推导式（大数据量时省内存）。

3. 选择正确的工具

• 只读序列 →tuple
• 频繁两端操作 →deque
• 频繁查找 →set/dict
• 有序维护 →bisect+list或sortedcontainers

4. 避免拷贝陷阱
[[]] * n是引用复制，lst.copy()是浅拷贝，嵌套结构需要deepcopy。

判断标准：当你能在写代码时自动规避pop(0)，本能地用推导式替代循环，并在看到"维护有序动态数组"时想到bisect——列表才真正成为你的本能。