動態陣列：格子滿了，就換一個兩倍大的（C# List<T> 與 Go slice）

一般的陣列（array）讀取很快，但一建好長度就固定，塞不下就沒辦法了。動態陣列的做法是：底下還是一個普通陣列，塞滿時就換一個兩倍大的新陣列，把資料搬過去。C# 的 List<T>、Java 的 ArrayList、Go 的 slice 都是這種結構。

名字裡雖然有「List」，但它跟鏈結串列（Linked List）沒有關係：裡面只有一個陣列，沒有節點、沒有指標。ArrayList 的意思是「用陣列（Array）做出來的清單（List）」。

一句話：格子滿了，就換一個兩倍大的新陣列，把舊的全部搬過去。偶爾搬一次很貴，但平均下來，每次加東西還是很便宜。

總覽：4 格滿了還要放 e → 開 8 格的新陣列 → 抄過去 → 放 e（點圖可放大）

五個名詞就夠

（GC＝垃圾回收：程式自動把「沒人在用的記憶體」收回去，你不用自己釋放。）

第一步：List<T> 就是「陣列＋計數」

把 List 想成一個有固定格數的收納盒：盒子有幾格是 Capacity，裡面放了幾個是 Count。

圖 A：陣列長度固定；List 在陣列外多記一個 Count（點圖可放大）

.NET 原始碼裡就是兩個欄位：_items（真正的陣列）和 _size（就是 Count）。所以大部分的 Add 只做兩件事：寫進下一格、Count ＋1，O(1)。

這段在講：List 不是什麼新結構，它只是幫你管一個陣列，順便記著用了幾格。

第二步：滿了就搬家，每次變兩倍

new List<int>() 一開始一格都不開（Capacity 0）。第一次 Add 才開 4 格，之後每次滿了就翻倍：4 → 8 → 16 → 32 …

圖 B：一步一步看 Add。放滿 4 格 → 開 8 格 → 抄過去 → 繼續放（動畫會循環，點圖可放大）

.NET 原始碼（List.cs 的 GetNewCapacity）的重點就這一行：

// DefaultCapacity = 4
int newCapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;

兩倍還不夠時（例如 AddRange 一次塞一大批），就直接開到需要的大小。

這段在講：剛好滿的那一次 Add 要搬家，是 O(n)；其他的 Add 都是 O(1)。

第三步：搬家很貴，為什麼平均還是 O(1)？

因為翻倍讓搬家越來越少見。把 33 次 Add 途中的搬家量接起來看：

圖 C：翻倍時，搬家量接起來永遠短於 2n；每次只多 4 格的話，搬家量越堆越多（點圖可放大）

為什麼一定短於 2n？每次搬的量都是上一次的兩倍，所以之前全部加起來，還比最後一次少（4＋8＋16＝28，比 32 少）。最後一次搬的量又不超過 n，所以總和不到 2n。

n 次 Add ＝ n 次寫入 ＋ 不到 2n 次搬運，總共 O(n)，平均每次 O(1)。這叫攤銷 O(1)（amortized）：像每 100 天繳一次 900 元年費，繳費那天很痛，平均每天只多 9 元。

代價是空間：剛搬完時新陣列只用了一半，最多空著約一半的格子。

一句話：翻倍讓偶爾的大搬家，平均攤到每次 Add 只剩一點點。這是數學保證，不是碰運氣。

第四步：Go slice＝把 List 的欄位攤開給你看

Go 的 slice 是一個三格的小表頭：指向底層陣列的 ptr、長度 len、容量 cap。資料本身放在表頭指著的那個陣列裡。

圖 D：slice 表頭是一個小的「值」，指派或傳進函式時會複製一份；但兩份表頭指著同一個陣列（點圖可放大）

為什麼 Go 一定要寫 s = append(s, x)？因為表頭是值：append 會改 len，還可能換新陣列（ptr 變了），新的表頭是用回傳值給你的，不接住就丟了。C# 的 List 是同一個物件、自己改自己，所以不用接。

Go 的成長規則（runtime/slice.go）：cap 小於 256 時翻倍，之後每次約多 1/4，倍率慢慢降到約 1.25 倍，再依記憶體配置的固定尺寸微調。只要是「乘上一個大於 1 的倍數」，append 就一樣是攤銷 O(1)。

坑：從同一個 slice append 兩次，互相蓋掉

cap 還有空位時，append 不搬家，直接寫進共用的底層陣列。所以從同一個 a append 兩次，兩次都寫到同一格：

圖 E：上半是 bug，42 蓋掉 99；下半把 cap 鎖死，append 只好各自搬家（點圖可放大）

解法是三個數字的切片 a[low:high:max]：第三個數字把 cap 設成 max − low。a[:3:3] 的 cap 是 3、沒有空位，下一次 append 一定搬到新陣列，大家就互不干擾。

一句話：slice 會共用底層陣列；不想讓別人的 append 動到你，就把 cap 鎖成 len。

常見的坑

• 在中間插入或刪除是 O(n)。陣列是連在一起的，不能插隊，後面的元素全部要挪一格（.NET 原始碼就是一行 Array.Copy 把尾巴整段搬移）。要常在開頭或中間插刪，就該換別的資料結構。

圖 F：中間插入，後面的人全部往後挪（點圖可放大）

• 知道大概要放多少，就先講。C# new List<T>(n)、Go make([]T, 0, n)，一次開好，省掉沿路搬家（練習 3 會看到差多少）。注意：設定 Capacity 這個屬性本身是 O(n)，因為會重開陣列並複製。
• C# 的 foreach 走到一半，不能改那個 List。
  • 會怎樣：在 foreach (var x in list) 裡面呼叫 list.Add、list.Remove，甚至 list[0] = 9，下一步就會丟出 InvalidOperationException（「集合已修改」）。
  • 它怎麼發現的：List 身上有一個「改過幾次」的計數器（原始碼裡叫 _version），每改一次就 ＋1。foreach 開始時先抄下這個數字，之後每走一步就對一次；數字變了，就代表走到一半有人改了清單。
  • 為什麼要這麼兇：像點名點到一半，有人插隊、有人離開，名單就對不上了，可能漏點或重複點。與其給你一份半新半舊的錯誤結果，不如當場喊停。
  • 要改怎麼辦：改用 for (int i = 0; …) 用索引走，或先收集要刪的、迴圈結束再刪（例如 list.RemoveAll(…)）。
  • Go 不一樣：for range 不會報錯。迴圈開始時就先決定好要走幾格，中途 append 進來的新元素不會被走到。
• 切一小段，大陣列卻收不掉。常見誤會：「切出來的是一小份新資料」。其實 Go 的切片不會複製，只是開一扇窗看原陣列：
  • header := data[:10]，手上只用 10 bytes，但 data 那 100 MB 因為還被指著，GC 收不掉。
  • 要長期留著一小段，就複製出來：slices.Clone(data[:10])。
  • C# 平常不會：arr[..10]、GetRange、Substring 都是複製。只有 Memory<T>、ArraySegment<T> 會共用，同樣要小心。

動手做

先開一個練習資料夾：

mkdir lab_slice && cd lab_slice && go mod init lab_slice

下面每個實驗放一個子資料夾，做三個小實驗。每個都先猜、再跑、再對答案。下面的輸出是在 Go 1.25.5、.NET 10 實際跑出來的。

練習 1：看 cap 怎麼長、總共搬了多少

建檔在 lab_slice 裡執行，會建好資料夾並開一個新檔：

mkdir grow && code grow/main.go

建檔指令裡的 code 是用 VS Code 開新檔；沒有 VS Code 的話，改用 touch 檔名 建空檔，再用你慣用的編輯器打開。

把這段程式貼進去、存檔：

package main

import "fmt"

func main() {
	var s []int
	copied := 0 // 搬家時總共複製了幾個元素
	for i := 0; i < 1000; i++ {
		oldCap := cap(s)
		s = append(s, i)
		if cap(s) != oldCap { // cap 變了 = 剛剛換了一個新陣列
			copied += len(s) - 1 // 舊陣列裡的元素全部被抄過去
			fmt.Printf("第 %4d 次 append：cap %4d → %4d（搬了 %d 個）\n",
				i+1, oldCap, cap(s), len(s)-1)
		}
	}
	fmt.Printf("加了 %d 個元素，搬家總共複製 %d 個（2n = %d）\n", len(s), copied, 2*len(s))
}

先猜append 1000 次，cap 會怎麼變？搬家總共複製的元素，會比 2000 多還是少？

執行在 lab_slice 裡：

go run ./grow

你會看到256 以前每次翻倍；之後 512 → 848 → 1280，倍率變小了。搬家總共只複製 1868 個，比 2n 少。

這證明圖 C 的道理在真的程式裡成立：搬家量加總不到 2n，所以 append 是攤銷 O(1)。

小註：一開始就是 cap 4 而不是 1。我把 slice 存到全域變數再跑，就變回 1 → 2 → 4，可見跟編譯器的最佳化有關（Go 1.25 讓更多 slice 的底層陣列可以先放在 stack 上）。確切規則官方沒寫細，這點我不確定。別背這些數字，記「小時翻倍、大了倍率變小」就好。

練習 2：重現「兩次 append 互相蓋掉」，再修好

建檔在 lab_slice 裡執行，會建好資料夾並開一個新檔：

mkdir share && code share/main.go

把這段程式貼進去、存檔：

package main

import "fmt"

func main() {
	a := make([]int, 3, 10) // len 3、cap 10：後面還有 7 個空位
	b := append(a, 99)
	c := append(a, 42)
	fmt.Println("有 bug：b =", b, " c =", c)

	safe := a[:3:3] // 第三個數字把 cap 鎖成 3，沒有空位
	b2 := append(safe, 99)
	c2 := append(safe, 42)
	fmt.Println("修好後：b2 =", b2, " c2 =", c2)
}

先猜b 和 c 的最後一個數字各是多少？

執行在 lab_slice 裡：

go run ./share

你會看到b 明明 append 的是 99，卻印出 42。

這證明圖 E：cap 有空位時 b、c 寫進同一格；鎖住 cap 後各自搬家。再試一次：把 safe := a[:3:3] 改成 safe := a，bug 會回來。

練習 3：先講好容量，記憶體配置差幾次（寫成測試）

建檔在 lab_slice 裡執行，會建好資料夾並開一個新檔：

mkdir prealloc && code prealloc/prealloc_test.go

把這段程式貼進去、存檔：

package prealloc

import "testing"

var sink []int // 放到全域，逼 slice 真的配置在 heap 上，數字才看得到

func TestAllocs(t *testing.T) {
	const n = 10000
	grow := testing.AllocsPerRun(100, func() {
		var s []int
		for i := 0; i < n; i++ {
			s = append(s, i)
		}
		sink = s
	})
	pre := testing.AllocsPerRun(100, func() {
		s := make([]int, 0, n) // 先講好要裝 n 個
		for i := 0; i < n; i++ {
			s = append(s, i)
		}
		sink = s
	})
	t.Logf("沒預留：每輪配置 %.0f 次記憶體", grow)
	t.Logf("有預留：每輪配置 %.0f 次記憶體", pre)
}

先猜放 10000 個 int，不預留要配置記憶體幾次？預留呢？

執行在 lab_slice 裡：

go test ./prealloc/ -v

你會看到19 次對 1 次。

這證明每次搬家＝配置一個新陣列；先講好容量，就一次開完。sink 是為了讓 slice 真的放到一般的動態記憶體（heap）上，測量才準。

var list = new List<int>();
int last = -1;
for (int i = 0; i < 40; i++)
{
    list.Add(i);
    if (list.Capacity != last)
    {
        Console.WriteLine($"Count={list.Count,-3} Capacity={list.Capacity}");
        last = list.Capacity;
    }
}

try
{
    foreach (var x in list)
        if (x == 3) list.Add(999);   // 一邊走訪一邊加
}
catch (InvalidOperationException e)
{
    Console.WriteLine("丟出例外：" + e.Message);
}

Count=1   Capacity=4
Count=5   Capacity=8
Count=9   Capacity=16
Count=17  Capacity=32
Count=33  Capacity=64
丟出例外：Collection was modified; enumeration operation may not execute.

✔ 過關標準

能不看筆記回答下面 5 題，這篇就過了。

1. Count 和 Capacity 差在哪？Add 什麼時候會搬家？看答案收合

   Count 是放了幾個，Capacity 是總共幾格。Count 等於 Capacity（滿了）時再 Add，就要開新陣列、把舊的抄過去。
2. 搬家是 O(n)，為什麼還說 Add 平均是 O(1)？如果每次只多 4 格會怎樣？看答案收合

   因為翻倍讓搬家量加總不到 2n，平攤到每次只剩常數。每次只多 4 格的話，搬家量會是 4＋8＋12＋…，大約跟 n² 成正比，平均每次就變 O(n)。
3. Go 為什麼一定要寫 s = append(s, x)？看答案收合

   slice 表頭是值，append 用回傳值把新的表頭交給你。len 一定變了，ptr 也可能變（換了新陣列），不接住就還在用舊的表頭。
4. 從同一個 slice append 兩次，為什麼會互相蓋掉？怎麼修？看答案收合

   cap 有空位時 append 不搬家，兩次都寫進共用陣列的同一格。用 a[:len(a):len(a)] 把 cap 鎖成 len，下一次 append 就一定搬到自己的新陣列。
5. 為什麼在 List 開頭 Insert 很慢，在尾巴 Add 很快？看答案收合

   陣列連在一起不能插隊。插在開頭，後面 n 個都要挪一格，是 O(n)；加在尾巴不用挪，是 O(1)（除非剛好要搬家）。

下一篇

雜湊表：不用從頭找，用 key 直接算出位置。C# 的 Dictionary 和 Go 的 map 都靠它。

參考來源

• dotnet/runtime — List.cs（_items／_size、DefaultCapacity＝4、GetNewCapacity 翻倍、Insert 的 Array.Copy、_version）
• Microsoft Learn — List<T>.Capacity（Capacity ≥ Count、設定 Capacity 是 O(n)）
• The Go Programming Language Specification（append 何時重用底層陣列、三個數字的切片、range 只算一次）
• Go blog — Go Slices: usage and internals（slice 表頭、共用底層陣列、切一小段留住大陣列）
• golang/go — runtime/slice.go（nextslicecap：256 以下翻倍、之後漸近 1.25 倍）
• Go 1.25 Release Notes（編譯器在更多情況下把 slice 底層陣列放在 stack）