列表

什么是列表

列表（list）是 Python 中最基础也最常用的数据结构之一。简单来说，它就像是一个有序的收纳盒，你可以把各种东西按顺序放进去，随时取用、添加或删除。

在 Python 中，创建一个列表非常简单：

shopping_list = ['牛奶', '鸡蛋', '面包']

想象一下你有一个购物清单：

• 牛奶
• 鸡蛋
• 面包

这个清单就是列表——有顺序（牛奶排第一）、可以修改（今天不想买面包了，换成苹果）、可以重复（牛奶买两盒）。

当你第一次学 Python 时，最先接触的容器大概就是 list。用 [1, 2, 3] 创建一个列表，然后 append、pop、index，这些操作看起来非常简单直观的。但如果你以为 list 只是"存放数据的地方"，那就错过了一个很重要的世界。

list 是 Python 最常用的容器，但它也是被误解最深的。大多数人用它存储数据，却不一定了解它在底层是如何工作的。为什么索引访问是 O(1)？为什么在中间插入是 O(n)？为什么 [[0]*3]*3 会出问题？这些问题背后，都藏着 list 的设计哲学。

理解 list，不只是记住它的 API，而是理解它的内存模型、时间复杂度、以及它和其他容器的关系。这些知识在写高性能代码、排查 bug、应对面试时，都会派上大用场。

列表的内存模型

Python 的 list 到底是什么？在语义上，它是一个"有序、可变、可重复"的序列。但这个描述只告诉我们"能做什么"，没有告诉我们"怎么做"。

当你写下 nums = [10, 20, 30] 时，Python 会在内存中分配一块连续的空间。但这块空间存放的不是整数本身，而是指向这些整数对象的"指针"。

这个设计初看可能觉得奇怪——为什么不能直接存放整数？原因是 Python 的万物皆对象模型。整数 10 是一个完整的对象，它有自己的内存布局和元数据。如果直接把对象放进列表，列表就需要处理各种大小不一的对象，这会让内存管理变得极其复杂。而用指针链接，所有元素的"大小"就统一了——都是一个指针的宽度。

连续内存加指针结构这个模型，解释了很多 list 的行为特征。索引访问之所以快，是因为知道了起始地址，加上索引乘以指针宽度，就能直接算出目标地址，这个计算是常数时间。而中间插入或删除时，需要把目标位置之后的所有元素整体向后或向前移动，移动成本和列表长度成正比。

索引访问

list 支持两种访问方式：正索引和负索引。正索引从 0 开始，nums[0] 获取第一个元素，nums[-1] 获取最后一个元素。

但不管是哪种索引，底层都是同一个计算公式。假设列表的起始地址是 base，每个指针占 8 个字节（64位系统），那么 nums[i] 的物理地址就是 base + i * 8。这个计算本身是 O(1)，所以索引访问是 O(1)。

nums = [10, 20, 30, 40, 50]

print(nums[0])   # 10，首元素
print(nums[4])    # 50，尾元素
print(nums[-1])   # 50，负索引等同于 len(nums)-1

切片访问

切片（slicing）是 Python 列表中非常强大且灵活的特性，它允许你快速提取列表的子集。切片的基本语法是 list[start:end:step]，其中 start 是起始索引（包含），end 是结束索引（不包含），step 是步长。

切片操作 nums[1:4] 会创建一个新的列表，但这个创建过程本身是 O(n) 的，因为它需要复制 n 个指针。如果你的代码里有很多切片操作，要意识到每一步切片都是有成本的。

nums = [1, 2, 3, 4, 5]

sub = nums[1:4]  # 创建新列表 [2, 3, 4]
print(type(sub))  # <class 'list'>

动态扩容机制

list 是如何增长的？很多人以为每次 append 都会重新分配空间，其实不是。Python 使用的是"预分配 + 扩容因子"策略。

当你创建一个空列表时，它实际上分配了一小块初始空间。当你不断 append 元素时，空间用完之前都不需要重新分配。只有当空间不够时，Python 才会申请一块更大的内存（通常是原来的 1.125 倍左右），把原有元素拷贝过去，然后释放旧空间。

这就解释了为什么单次 append 可能很慢（需要扩容时），但平均来看每次 append 都是 O(1)。这个概念叫做"均摊时间复杂度"。

扩容的具体策略在不同的 Python 版本中略有差异，但核心思想是一样的：用空间换时间，通过预分配减少重新分配的次数。这意味着你在创建列表时如果能预估大小，用 list([0] * n) 预先分配空间会比多次 append 稍微高效一点。

import sys

a = []
print(sys.getsizeof(a))  # 初始容量大约 56 字节

a.append(1)
print(sys.getsizeof(a))  # 扩容后变大

for i in range(100):
    a.append(i)
print(sys.getsizeof(a))  # 继续扩容

面试时经常被问到"为什么 list 的 append 是 O(1)"，正确的回答是"均摊 O(1)"。如果不解释清楚这个"均摊"二字，就还没有真正理解 list 的扩容机制。

添加元素的各种方式

向 list 添加元素有三种主要方式：append、extend、insert。

append 将一个元素添加到列表末尾，是最常用的方式。extend 接收一个可迭代对象，将其中的每个元素依次添加到列表末尾。insert 在指定位置插入元素。

nums = [1, 2]

nums.append(3)           # [1, 2, 3]
nums.extend([4, 5])      # [1, 2, 3, 4, 5]
nums.insert(0, 100)      # [100, 1, 2, 3, 4, 5]

一个容易犯的错误是把 append 和 extend 混用。如果你想添加 [6, 7] 这个列表本身而不是它的元素，应该用 append：

nums = [1, 2, 3]
nums.append([4, 5])
print(nums)  # [1, 2, 3, [4, 5]]，嵌套列表

insert 的时间复杂度是 O(n)，因为需要在中间位置插入元素时，被插入位置之后的元素都需要向后移动一位。在需要频繁在头部插入元素的场景下，应该考虑使用 deque。

删除元素的方式

从 list 删除元素有四种方式：remove、pop、del、clear。

remove 按值删除，会找到第一个匹配的元素并删除。如果元素不存在，会抛出 ValueError。

pop 按索引删除并返回被删除的元素。默认删除最后一个元素，传参可以指定任意索引。

del 是 Python 的语法，可以删除指定索引的元素或者切片，不返回值。

nums = [1, 2, 3, 2, 4]

nums.remove(2)    # 删除第一个 2，结果 [1, 3, 2, 4]
print(nums.pop()) # 删除并返回最后一个，结果 4，列表变为 [1, 3, 2]
del nums[0]       # 删除索引 0 的元素，结果 [3, 2]
nums.clear()      # 清空列表，结果 []

从时间复杂度来看，删除末尾元素是 O(1)，因为只需要移动一个指针。删除中间元素是 O(n)，因为后续所有元素都需要向前移动。删除头部元素更是 O(n)，因为需要移动所有剩余元素。

面试中常问的一个问题是"list 和 deque 的区别"，核心答案就在于头部操作。list 的头部操作是 O(n)，而 deque 的头部操作是 O(1)。

查找与统计

list 提供 index 和 count 两个查找方法。index 返回指定元素第一次出现的索引，如果不存在会抛出 ValueError。count 返回指定元素出现的次数。

nums = [1, 2, 3, 2, 2, 3]

print(nums.index(2))    # 1
print(nums.count(2))    # 3
print(nums.index(100))  # ValueError

这两个方法的时间复杂度都是 O(n)，因为需要遍历列表才能找到目标。如果需要频繁查找，应该考虑使用 set 或 dict 来存储数据，它们的时间复杂度是 O(1)。

排序的原理

list 有两种排序方式：sort 是原地排序，修改原列表；sorted 是返回一个新的已排序列表，不修改原列表。

nums = [3, 1, 4, 1, 5, 9, 2]

nums.sort()          # 原地排序，nums 变为 [1, 1, 2, 3, 4, 5, 9]
print(sorted(nums))  # 返回新的已排序列表

Python 的 list.sort 使用的是 Timsort 算法，这是一种混合排序算法，结合了归并排序和插入排序的优点。Timsort 的特点是：对部分有序的数据表现极佳，最坏时间复杂度是 O(n log n)，而且是稳定排序。

稳定排序的意思是：两个相等的元素，排序后它们的相对位置保持不变。这在很多场景下很重要，比如先按年龄排序再按姓名排序，稳定排序能保证同年龄的人仍然按姓名排序。

students = [("Tom", 85), ("Jerry", 90), ("Alice", 85)]

students.sort(key=lambda x: x[1])  # 按分数排序

print(students)
# [('Tom', 85), ('Alice', 85), ('Jerry', 90)]
# Tom 和 Alice 的相对位置保持不变

sort 方法的 key 参数很重要，它指定了排序的依据。Python 只会对每个元素调用一次 key 函数来获取排序关键字，这是一个重要的性能优化点。

一个常见的误用是链式调用 sorted(nums).sort()，这是错误的，因为 sorted 返回的是新列表，新列表没有 sort 方法（除非你用 list.sort()）。正确写法是 nums.sort() 或者 sorted(nums)。

切片不只是拷贝

切片操作 list[start:end] 创建一个新的列表。但这不是简单的内存拷贝——它拷贝的是指针，而不是对象本身。这就是所谓的"浅拷贝"。

data = [[1, 2], [3, 4], [5, 6]]

copy = data[:]  # 浅拷贝

copy[0].append(100)

print(data)  # 原列表也被修改了！
# [[1, 2, 100], [3, 4], [5, 6]]

原因是 copy 和 data 指向的是相同的子列表对象。当你通过 copy 修改子列表时，data 也能看到变化。

如果想实现深拷贝，需要使用 copy.deepcopy：

import copy

data = [[1, 2], [3, 4]]

deep = copy.deepcopy(data)

deep[0].append(100)
print(data)  # 不受影响
# [[1, 2], [3, 4]]

这是 Python 面试的高频陷阱。面试官可能会问你"list 的拷贝有哪几种方式"，正确答案是：切片拷贝 [:]、copy.copy()、copy.deepcopy()，以及列表推导式 [x for x in original]。但只有 deepcopy 才是真正的深拷贝。

列表推导式的本质

列表推导式是 Python 的一种语法糖，它用一种更简洁的方式创建列表：

squares = [x ** 2 for x in range(10)]

底层执行流程和 for 循环加 append 几乎一样：创建空列表、获取迭代器、不断调用 next()、执行表达式、append 结果。唯一的区别是列表推导式在 C 层实现，减少了 Python 字节码的开销，所以通常更快一点。

numbers = [1, 2, 3, 4, 5]

# 列表推导式
squared = [x ** 2 for x in numbers]

# 等价的 for 循环
squared = []
for x in numbers:
    squared.append(x ** 2)

推导式可以加条件过滤，只保留满足条件的元素：

evens = [x for x in range(10) if x % 2 == 0]
# [0, 2, 4, 6, 8]

还可以嵌套，模拟嵌套循环：

points = [(x, y) for x in range(3) for y in range(3)]
# [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]

但要注意，列表推导式的主要目的是创建列表，不是做复杂的逻辑处理。如果推导式变得过于复杂，应该考虑使用普通的 for 循环来提高可读性。

乘法初始化的陷阱

用乘法初始化列表是一个常见技巧，但也是常见陷阱：

# 这个是安全的
nums = [0] * 5
print(nums)  # [0, 0, 0, 0, 0]

# 这个有问题
matrix = [[0] * 3 for _ in range(3)]
print(matrix)  # 正确：三个独立的子列表

# 错误写法
matrix = [[0] * 3] * 3
print(matrix)  # [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
# 看起来正常，但修改一下试试
matrix[0][0] = 1
print(matrix)  # [[1, 0, 0], [1, 0, 0], [1, 0, 0]]，全部被修改了！

问题在于 [[0] * 3] * 3 创建的是一个包含三个引用指向同一个列表的列表。修改任何一个子列表，另外两个也会被修改。

这是 Python 面试中出现频率极高的一道题。背后的原理是：* 操作符对于列表，复制的是引用而不是对象。

列表与迭代器

list 是一个可迭代对象，支持 for x in list 遍历。但 list 本身不是迭代器，每次遍历都需要调用 iter() 获取迭代器。

nums = [1, 2, 3]

for x in nums:  # 内部调用 iter(nums)
    print(x)

如果你需要显式控制迭代过程，应该使用迭代器：

it = iter(nums)
print(next(it))  # 1
print(next(it))  # 2
print(next(it))  # 3
print(next(it))  # StopIteration

range() 函数返回一个 range 对象，它也是一个可迭代对象，但每次遍历时会动态生成数字，不占用额外内存。这和 list 不同，list 需要预先把所有元素加载到内存。

# range 惰性生成，不占内存
for i in range(1000000):
    pass

# list 需要预先占用内存
for i in list(range(1000000)):
    pass

在处理大数据时，应该优先考虑使用 range 或生成器表达式，而不是 list。

内存占用分析

list 的内存占用包括三个部分：头部信息（包含长度、容量等元数据）、元素指针数组、元素对象本身。指针数组是连续内存，每个指针占 8 字节（64位系统）。

import sys

a = [1, 2, 3]
print(sys.getsizeof(a))  # 列表本身（不含元素）大约 64 字节

b = [1, 2, 3, 4, 5]
print(sys.getsizeof(b))  # 更大一些，因为指针数组更长

但要注意，sys.getsizeof 只计算列表对象本身占用的内存，不计算元素对象的内存。这是因为元素对象可能被多个引用共享。

如果你想分析内存使用的细粒度分布，可以使用 sys.getsizeof 结合元素逐个分析：

import sys

data = [1, 2, 3]

total = sys.getsizeof(data)
for i, item in enumerate(data):
    total += sys.getsizeof(item)

print(f"列表对象: {sys.getsizeof(data)} 字节")
print(f"估算总内存: {total} 字节")

性能特征总结

理解 list 的性能特征是 Python 工程师的基本功：

操作	时间复杂度	说明
索引访问 nums[i]	O(1)	直接计算地址
索引赋值 nums[i] = x	O(1)	直接写入地址
尾部 append	均摊 O(1)	扩容时 O(n)
尾部 pop	O(1)	只需移动指针
中间 insert	O(n)	需移动后续元素
中间 pop	O(n)	需移动后续元素
删除末尾	O(1)	只需移动指针
x in nums	O(n)	线性查找
nums.index(x)	O(n)	线性查找
nums.count(x)	O(n)	线性查找
切片 nums[a:b]	O(n)	需复制 n 个指针
nums.sort()	O(n log n)	Timsort

关键理解是：list 本质上是数组，不是链表。头部操作是 O(n)，尾部操作是 O(1)。这和很多教学中的"列表是链表"说法完全不同——那是其他语言的叫法，在 Python 里 list 是动态数组。

常见误区大盘点

第一个误区是混淆浅拷贝和深拷贝。list[:] 和 copy.copy() 都是浅拷贝，只复制一层引用。如果列表元素是不可变对象（数字、字符串、元组），浅拷贝和深拷贝效果相同。但如果列表里有可变对象，就需要用 deepcopy。

第二个误区是在循环中修改列表。试图一边遍历一边删除元素，通常会导致意外行为或索引错误：

nums = [1, 2, 3, 4, 5]

# 错误写法
for i in nums:
    if i > 2:
        nums.remove(i)

print(nums)  # 结果不确定

正确的做法是遍历副本：

nums = [1, 2, 3, 4, 5]

for i in nums[:]:  # 遍历副本
    if i > 2:
        nums.remove(i)

第三个误区是误用 list * n 创建嵌套列表。前面已经讲过，这是创建了 n 个指向同一个对象的引用。

第四个误区是认为排序是 O(n) 的。字符串排序或其他对象排序，时间复杂度是 O(n log n)，这是排序算法的信息论下限，不可能更快。

与其他容器的选择

Python 提供了多种容器类型，list 不是万能的。当需要频繁在头部插入或删除时，应该用 deque。当需要快速查找而不是顺序访问时，应该用 set 或 dict。当需要存储不可变数据时，应该用 tuple。

例如，频繁在末尾追加和删除时 list 是最佳选择。但如果需要频繁在队列两端操作，deque 是更好的选择：

from collections import deque

# list 在头部插入是 O(n)
a = [1, 2, 3]
a.insert(0, 0)  # O(n)

# deque 在头部插入是 O(1)
d = deque([1, 2, 3])
d.appendleft(0)  # O(1)

理解这些容器的底层差异，才能在写代码时做出正确的选择。