使列表有用的原因
列表：您的第一個數據結構
列表（在某些語言中稱為數組）按特定順序存儲項目。您可以：
- 按位置訪問任何項目：names[0] 獲取第一個項目。O(1) — 立即。
- 在末尾添加項目：names.append("Zoe")。O(1) — 立即。
- 按順序遍歷每個項目：for name in names。O(N) — 訪問每個項目一次。
列表保持您放入項目的順序。第一個項目保持第一個。最後一個保持最後一個。
# 寵物列表
pets = ["cat", "dog", "cat", "fish", "dog"]
print(pets[0]) # "cat" — O(1) 立即
print(pets[3]) # "fish" — O(1) 立即
print(len(pets)) # 5 — 保留重複項注意："cat" 出現了兩次。"dog" 出現了兩次。列表允許重複。它們按您給定的順序存儲您給定的內容。
但列表有一個弱點。看看當您問以下問題時會發生什麼："fish" 在這個列表中嗎？
# 成員檢查 — "fish" 在列表中嗎？
if "fish" in pets: # 逐個掃描 ["cat", "dog", "cat", "fish"...]
print("found!") # 在找到它之前必須檢查 4 個項目計算機檢查 "cat" — 否。"dog" — 否。"cat" — 否。"fish" — 是！它掃描了 4 個項目才找到答案。有 1,000 個項目，它可能掃描全部 1,000 個。該成員檢查花費 O(N)。
預測掃描成本
您有一個隨機順序的 500 個學生姓名的列表。
您想檢查列表中是否出現了 "Zara"。
students = ["Alex", "Maria", ..., "Zara", ...] # 500 個姓名
if "Zara" in students:
print("enrolled")集合如何不同地工作
集合：為成員資格問題而構建
集合使用稱為雜湊的技術存儲唯一項目。當您添加項目時，計算機計算一個雜湊（數字指紋），告訴它將該項目存儲在哪裡。
當您檢查成員資格時，計算機計算相同的雜湊並直接跳到正確的位置。無需掃描。
# 寵物集合
pets = {"cat", "dog", "cat", "fish", "dog"}
print(pets) # {"cat", "dog", "fish"} — 重複項已移除
print(len(pets)) # 3 — 僅唯一項目注意與列表的三個區別：
1. 無重複。 "cat" 在輸入中出現了兩次，但集合只保留一個副本。
2. 無保證的順序。 集合可能以任何順序打印項目。
3. 無索引訪問。 您不能寫 pets[0] — 集合沒有位置。
折衷方案：您失去了順序和重複。您獲得了O(1) 成員資格測試 — 檢查項目是否存在無論集合有 5 個項目還是 5 百萬個項目都花費相同的時間。
# 成員檢查 — "fish" 在集合中嗎？
if "fish" in pets: # hash("fish") → 跳轉到桶 → 找到
print("found!") # 恰好檢查了 1 個位置，而不是 4 個集合與列表成員資格
您有 500 個學生姓名存儲在集合中而不是列表中。
students = {"Alex", "Maria", ..., "Zara", ...} # 500 個姓名
if "Zara" in students:
print("enrolled")並排比較
操作速查表
什麼時候使用列表：
- 項目需要按特定順序（播放列表、食譜、隊列）
- 按位置訪問（items[3]）
- 保留重複項（"cat" 出現 3 次 = 3 隻貓）
什麼時候使用集合：
- 快速成員檢查（"我之前見過這個嗎？"）
- 自動去除重複
- 不關心順序
什麼時候同時使用兩者：
seen = set() # O(1) 成員檢查
result = [] # 保留插入順序
for item in data:
if item not in seen: # O(1) 檢查
seen.add(item) # O(1) 添加
result.append(item) # O(1) 追加
# 總計：O(N) — 一次遍歷，每一步 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) 掃描 unique 列表
unique.append(email)
# 有效！但：O(N) 檢查 × N 項目 = 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() # O(M) 來構建
unique = []
for email in signups:
if email not in seen: # O(1) 雜湊查找
seen.add(email) # O(1) 添加到集合
unique.append(email) # O(1) 追加到列表
# O(1) 檢查 × N 項目 = 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 次迭代
if student in class_b: # 每次 M 次掃描
both.append(student)
# O(N × M) — 每個學生掃描 class_b 的所有項快方法：將一個列表轉換為集合 O(N + M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b) # O(M) 來構建
both = []
for student in class_a: # N 次迭代
if student in class_b_set: # O(1) 每次
both.append(student)
# O(N + M) — 構建集合一次，檢查 N 次每次 O(1)或者甚至更簡單，使用 Python 的內置集合交集：
both = set(class_a) & set(class_b) # O(N + M)& 運算符找到出現在兩個集合中的所有項目。
重寫以加速
一所學校有兩個俱樂部，每個俱樂部有 200 名成員。此代碼找到同時在兩個俱樂部的學生：
chess_club = [...] # 200 個名字
art_club = [...] # 200 個名字
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) 的結構。
本課涵蓋了列表和集合。還有其他數據結構（字典、樹、堆）解決其他問題。決策框架保持相同：理解您的操作，然後選擇使它們便宜的結構。
---
想要深入？ 我們的 Big O 課程詳細涵蓋了增長率和縮放計算。參見 Big O：多快才算夠快？。我們的 unhamming 課程涵蓋了真實的缺陷（MOAD-0001），其中這個確切的列表到集合修復在生產軟件中產生了 1,000 倍的加速。參見 遺漏的章節：算法複雜性。
調試此代碼
學生編寫了這段代碼來計算書中出現多少個唯一單詞：
words = book.split() # 所有單詞的列表
unique_count = 0
checked = []
for word in words: # N 個單詞
if word not in checked: # 掃描 checked 列表
checked.append(word)
unique_count += 1
print(unique_count)這本書有 100,000 個單詞。