列表的优势
列表：你的第一个数据结构
一个列表（在某些语言中称为数组）按特定顺序存储项目。你可以：
- 按位置访问任何项目：names[0] 获取第一项。O(1) — 瞬间。
- 在末尾添加项目：names.append("Zoe")。O(1) — 瞬间。
- 按顺序遍历每个项目：for name in names。O(N) — 访问每个项目一次。
列表保留你放入项目的顺序。第一项保持第一。最后一项保持最后。
# A list of pets
pets = ["cat", "dog", "cat", "fish", "dog"]
print(pets[0]) # "cat" — O(1) instant
print(pets[3]) # "fish" — O(1) instant
print(len(pets)) # 5 — duplicates kept注意："cat" 出现了两次。"dog" 出现了两次。列表允许重复。 它按你给定的顺序精确存储你给定的内容。
但列表有个弱点。看看当你问："fish" 是否在这个列表中？
# Membership check — is "fish" in the list?
if "fish" in pets: # scans ["cat", "dog", "cat", "fish"...] one by one
print("found!") # had to check 4 items before finding it计算机检查 "cat" — 否。"dog" — 否。"cat" — 否。"fish" — 是！它扫描了 4 个项目才找到答案。有 1,000 个项目时，它可能会扫描全部 1,000 个。那个成员检查花费 O(N)。
预测扫描成本
你有 500 个学生姓名存储在一个随机顺序的列表中。
students = ["Alex", "Maria", ..., "Zara", ...] # 500 names
if "Zara" in students:
print("enrolled")集合的工作方式有何不同
集合：为成员检查而构建
一个集合使用称为哈希的技术存储唯一项目。当你添加一个项目时，计算机计算一个哈希（一个数字指纹），告诉它正好在哪里存储该项目。
当你检查成员资格时，计算机计算相同的哈希并直接跳到正确的位置。无需扫描。
# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}
print(pets) # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique items注意与列表相比的三个差异：
1. 无重复。 "cat" 在输入中出现了两次，但集合只保留一份副本。
2. 无保证的顺序。 集合可能以任何方式打印项目。
3. 无索引访问。 你不能写 pets[0] — 集合没有位置。
权衡：你失去了顺序和重复。你获得了 O(1) 成员测试 — 检查项目是否存在花费相同的时间，无论集合有 5 个项目还是 500 万个。
# Membership check — is "fish" in the set?
if "fish" in pets: # hash("fish") → jump to bucket → found
print("found!") # checked exactly 1 spot, not 4集合与列表成员检查
你将 500 个学生姓名存储在一个集合中，而不是列表。
students = {"Alex", "Maria", ..., "Zara", ...} # 500 names
if "Zara" in students:
print("enrolled")并排比较
操作速查表
在以下情况下使用列表：
- 项目处于特定顺序（播放列表、食谱、队列）
- 按位置访问 (items[3])
- 保留重复（"cat" 出现 3 次 = 3 只猫）
在以下情况下使用集合：
- 快速成员检查（"我之前见过这个吗？"）
- 自动去重
- 不关心顺序
当你需要顺序和快速查找时使用两者：
seen = set() # O(1) membership checks
result = [] # preserves insertion order
for item in data:
if item not in seen: # O(1) check
seen.add(item) # O(1) add
result.append(item) # O(1) append
# Total: O(N) — one pass, each step O(1)这个 "集合 + 列表" 模式为你提供两者的优点：有序结果加快速去重检测。
选择正确的结构
三个问题。对于每一个，决定：列表、集合，还是两者？
1. 你需要按用户添加歌曲的顺序存储播放列表中的歌曲。
2. 你需要快速检查用户名是否已被占用。
3. 你需要从邮件列表中删除重复的电子邮件，但保持它们注册的顺序。
去重问题
问题：删除重复项，保留顺序
你收到一份电子邮件注册列表。有些人注册了两次。你需要给每个人发送一封电子邮件，按他们第一次注册的顺序。
尝试 1：仅列表（缓慢）
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
if email not in unique: # O(N) scan of unique list
unique.append(email)
# Works! But: O(N) check × N items = O(N²)有 100 个注册，这做约 5,000 次检查。有 10,000 个注册：约 50,000,000 次检查。
尝试 2：集合 + 列表（快速）
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
if email not in seen: # O(1) hash lookup
seen.add(email) # O(1) add to set
unique.append(email) # O(1) append to list
# O(1) check × N items = O(N)相同结果。相同顺序。但：10,000 个注册现在需要约 10,000 次检查，而不是约 50,000,000 次。
计算加速
仅列表版本以 O(N²) 运行。集合+列表版本以 O(N) 运行。
你有 10,000 个电子邮件注册 要去重。
查找共同元素
问题：查找两个列表中的项目
你有两个班级名单。你需要找到两个班级中都注册的学生。
缓慢方法：嵌套循环 O(N × M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a: # N iterations
if student in class_b: # M scans each time
both.append(student)
# O(N × M) — each student scanned against all of class_b快速方法：将一个列表转换为集合 O(N + M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b) # O(M) to build
both = []
for student in class_a: # N iterations
if student in class_b_set: # O(1) each time
both.append(student)
# O(N + M) — build the set once, check N times at O(1) each或者更简单地使用 Python 的内置集合交集：
both = set(class_a) & set(class_b) # O(N + M)& 操作符找到出现在两个集合中的所有项目。
重写以加速
一所学校有两个俱乐部，各有 200 个成员。这个代码找到两个俱乐部中的学生：
chess_club = [...] # 200 names
art_club = [...] # 200 names
both_clubs = []
for student in chess_club:
if student in art_club:
both_clubs.append(student)决策框架
你的数据结构决策框架
每次你写代码存储项目集合时，问：
1. 我需要项目有顺序吗？ → 列表
2. 我需要快速成员检查吗？ → 集合
3. 我既需要顺序又需要快速检查吗？ → 集合 + 列表一起
4. 我需要重复吗？ → 列表（集合丢弃重复）
---
本课程的关键洞察： 相同的程序，解决相同的问题，只需选择正确的数据结构就可以快 1,000 倍到 1,000,000 倍。无需聪明的技巧。无需复杂的数学。只需问：我的代码最常做什么操作？ 然后选择在这些操作中花费 O(1) 而不是 O(N) 的结构。
本课程涵盖了列表和集合。其他数据结构存在（字典、树、堆）解决其他问题。决策框架保持不变：理解你的操作，然后选择使它们便宜的结构。
---
想要更深入？ 我们的大O课程详细涵盖增长率和扩展计算。查看 大O：多快才足够快？。我们的 unhamming 课程涵盖真实世界的缺陷（MOAD-0001），其中这个确切的列表到集合修复在生产软件中产生了 1,000 倍加速。查看 缺失的章节：算法复杂度。
调试这个代码
一个学生写了这个代码来计算一本书中有多少个独特的单词：
words = book.split() # list of all words
unique_count = 0
checked = []
for word in words: # N words
if word not in checked: # scans checked list
checked.append(word)
unique_count += 1
print(unique_count)这本书有 100,000 个单词。