List の内部動作を擬似コードで理解しよう

2025年8月2日

---

TL;DR

• List<T> は「伸び縮みする配列」。中身は T[] と現在要素数 _size を持つだけ。 
• Add で容量オーバーすると 約 2 倍に拡張 → 新しい配列を確保して全要素をコピー。 
• RemoveAt は削除位置より後ろの要素をすべて左へシフトするので O(n)。 
• foreach で回すときは 値型(struct)の列挙子 が返り、ヒープ割り当てゼロ。 
• 容量を詰めたいときは TrimExcess()、クリアは Clear()（配列は残る）。

---

1. なぜ List<T> が便利なのか

• 配列と違い 要素数が動的
• 型安全・高速な インデックスアクセス O(1)
• LINQ / Sort / Reverse など高機能 API が充実

---

2. 内部フィールドを擬似コードで覗く

class List<T> 
{
    private T[]  _items;    // 実体となる配列
    private int  _size;     // 現在格納されている要素数
    private int  _version;  // 変更検出用 (foreach の安全性確保)
    // ... コンストラクタと各種メソッド
}

• 初期化直後の配列長は 0（.NET 6〜。昔は既定容量 4）。
• _version は列挙中の変更を検知して InvalidOperationException を投げるために使われる。

---

3. Addの流れを擬似コードで追う

void Add(T item) 
{
    if (_size == _items.Length)           // ① もう入らない？
        Grow(_size + 1);                  // ② 容量確保
    _items[_size++] = item;               // ③ 末尾に追加
    _version++;                           // ④ 変更を記録
}

void Grow(int minCapacity) 
{
    int newCap = Math.Max(_items.Length * 2, 4); // ★ほぼ 2倍
    if (newCap < minCapacity)
        newCap = minCapacity;
    T[] newArray = new T[newCap];
    Array.Copy(_items, newArray, _size);         // 旧⇒新 コピー
    _items = newArray;
}

• 拡張係数が約 2 倍 なのは、コピー回数とメモリ浪費をバランスさせた経験則。 
• 容量確保 (Grow) は 時々高コスト だが、ならすと Add は 平均 O(1)（amortized constant time）。

---

4. RemoveAt の内部

void RemoveAt(int index) 
{
    int moveCount = _size - index - 1;      // 後ろに残る要素数
    if (moveCount > 0)
        Array.Copy(_items, index + 1,
                   _items, index, moveCount); // 左へシフト
    _items[--_size] = default;              // 終端を null / 既定値に
    _version++;
}

• シフトで 要素 n 個を丸ごとコピー ⇒ 時間計算量 O(n)。 
• 先頭 (index = 0) を大量に削除すると遅い。キュー用途なら Queue<T> を使うほうが安全。

---

5. Insert も似た仕組み

void Insert(int index, T item) 
{
    if (_size == _items.Length) Grow(_size + 1);   // 容量確保
    Array.Copy(_items, index,
               _items, index + 1,
               _size - index);                     // 右へシフト
    _items[index] = item;
    _size++;
    _version++;
}

• 右シフト → O(n)。頻繁に真ん中へ挿入するなら LinkedList<T> が候補。

---

6. インデクサ (this[int i]) ― 読み書き O(1)

T this[int i] 
{
    get => _items[i];    // 範囲外なら IndexOutOfRangeException
    set { _items[i] = value; _version++; }
}

配列と同じスピードでアクセスできるのが List<T> の最大の強み。

---

7. 列挙子（foreach の裏側）

struct Enumerator : IEnumerator<T> 
{
    private readonly List<T> _list;
    private int   _index;          // -1 から開始
    private int   _version;        // 変更検出用
    private T     _current;

    bool MoveNext() {
        if (_version != _list._version) throw ...; // 同時変更チェック
        if (++_index < _list._size) {
            _current = _list._items[_index];
            return true;
        }
        return false;
    }
    T Current => _current;
    void Dispose() {}              // 値型なので空実装
}

• 値型 (struct) 列挙子 → GC ヒープに載らず高速。 
• _version が違えば即例外。これが「列挙中に変更できません」の正体。

---

8. 容量を操る API

メソッド	作用	典型的な利用シーン
Capacity プロパティ	物理配列の長さを取得/設定	事前に要素数が分かるときに一気に確保
TrimExcess()	要素が 90% 未満なら 配列を縮小	大量削除後にメモリを解放したい
Clear()	_size = 0 にして 要素を論理削除	再利用前提で高速に空にする

※ Clear() は配列を残すので GC は走らない（参照型 T は null クリアで解放対象になる）。

---

9. 速度チューニングのポイント

1. 追加だけなら問題なし：平均 O(1)。
2. 頻繁に 先頭削除 → Queue<T> / Deque（自作）で置き換え。
3. 大量追加が読めるなら new List<T>(capacity) で先に確保。
4. LINQ チェーンで ToList() を多用すると無駄コピーになりがち。

---

10. まとめ

• List<T> の核は “サイズ付き配列”。操作ごとの内部コピー・容量拡張を意識すると、速度低下の原因が見える。
• 動作を擬似コードに落とすと「どこでコピーが走るか」「どこが O(n) か」が一目瞭然。
• 練習課題
  1. 本記事の擬似コードを参考に MyList<T> を実装し、BenchmarkDotNet で Add, Insert, RemoveAt の速度を測定。
  2. Queue<T> や LinkedList<T> と比較し、ワークロード別の最適コレクションを考察。

内部構造を知れば「なぜ遅いのか／どう直すか」を論理的に説明できるようになります。ぜひコードと一緒に動かしてみてください。