最基本、用最多的容器。靠「編號(index)」直接抓資料,一步到位 —— Python 的 list 和 str。
list)就是一排連在一起、編了號的格子。給它一個編號(index),它就能直接跳到那一格拿資料,不用從頭找 —— 這是 O(1)。但也因為「連在一起」,在中間插入或刪除時,後面全部得搬家,是 O(n)。字串則是一排不能改的字元陣列。
1. 連續記憶體 —— 陣列每一格大小一樣,而且在記憶體裡緊緊排在一起。
2. 用算的找位置 —— 電腦記得「起始位置」,要第 i 格就算 起始位置 + i × 格子大小,一步算出地址。
3. 所以 arr[0] 和 arr[9999999] 一樣快 —— 都是「算一下、跳過去」,跟前面有幾格完全無關。
4. 代價 —— 傳統陣列開多大要先講好;Python 的 list 幫你自動長大,但底層還是這排連續的格子。
在前面或中間插入 —— 為了騰出位子,插入點後面的每一格都要往右搬一格,搬的次數大約是 n。
刪除也一樣 —— 刪掉中間一格會留下一個洞,後面每一格要往左遞補。
只有「加在最尾巴」便宜 —— append 到最後不用搬別人,平均 O(1)(這叫攤還 amortized)。
下面的視覺化就是在演這件事 —— 直取一步到位,插入前端卻要搬一整排。
arr[i]。算一下地址直接跳過去,前面幾格都不影響。append / pop()。不用搬動別人,平均一步到位。collections.deque,兩頭都是 O(1)。一樣能用編號直取 —— s[0] 拿第一個字,跟 list 一樣 O(1)。
但字串不可變(immutable) —— 你不能 s[0] = 'x' 去改某個字,只能「產生一個新字串」。
所以在迴圈裡狂用 + 接字串很慢 —— 每次都複製一整份。要接很多段,請先收集再用 ''.join(list)(見範例 9)。
記得號碼就直接走到那格開,不用一個一個試 —— 這就是 index 直取 O(1)。
要在第 3 個位子硬插一個人進去,後面每個人都得往旁邊挪一格 —— 這就是插入要搬家。
想在中間加掛一節,得先把後面整段拆開推開 —— 一樣是搬家成本。
同一個陣列 [5, 8, 2, 9, 4],比較三種操作的成本。直取某一格一步到位;但在最前面插入或刪除,後面每一格都得搬。紫色是正在搬的那格、綠色是放好的、淡掉的是暫時空出來的洞。選一個操作,按「下一步」慢慢看。
從 list 的日常操作、切片、推導式、二維陣列,到字串處理五招與雙指標,都是刷題和實務最常用的。
❌ index 超出範圍 —— arr[len(arr)] 會 IndexError。最後一格是 arr[len(arr)-1],或直接用 arr[-1]。
❌ 在前端頻繁 insert(0, x) / pop(0) —— 每次都 O(n),資料一多就卡。改用 deque。
❌ 用 [[0]*3]*3 建二維陣列 —— 三列其實共用同一份參照,改一個全變。要用 [[0]*3 for _ in range(3)]。
❌ 迴圈裡邊走邊刪 list —— 索引會亂掉、漏刪。改成用推導式產生新 list,或反著走。
[7, 3, 9, 1] 做 arr.insert(0, 5),總共要「搬動」幾格?為什麼 append 到尾巴就不用搬?arr[0] 和 arr[1000000] 讀取一樣快,都是 O(1)?電腦是怎麼「一步」找到第 i 格的?s = 'abc',為什麼 s[0] = 'x' 會出錯?要得到 'xbc' 該怎麼寫?把答案打到對話裡,我幫你對。