はじめに：List<T>は「リスト」ではない？
C#のList<T>は非常によく使われるコレクションクラスですが、その実装を理解している人は意外と少ないかもしれません。特に注意すべき点として、List<T>はデータ構造の「連結リスト（Linked List）」ではなく、動的配列（Dynamic Array）であるということです。
他の言語ではArrayListやVectorと呼ばれるデータ構造に相当します。もし連結リストが必要な場合は、.NETではLinkedList<T>を使用します。
勘違いした解説も散見されるため、注意しましょう。
基本構造
List<T>の核となるフィールドは以下の3つです。
internal T[] _items; // 要素を格納する配列
internal int _size; // 実際に格納されている要素数
internal int _version; // 変更検知用のバージョン番号
重要なポイントは、内部で配列を使用しているということです。これにより、以下の特性が得られます。
- インデックスアクセスが O(1) で高速
- メモリ上で連続した領域に配列が確保される
- 容量（Capacity）と要素数（Count）が異なる
容量の拡張の仕組み
初期容量
private const int DefaultCapacity = 4;
List<T>は初期状態では空の配列を持ち、最初の要素が追加される際に容量4の配列を確保します。
拡張の仕組み
容量が不足すると、GetNewCapacityメソッドで新しい容量が計算されます。
private int GetNewCapacity(int capacity)
{
int newCapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;
if ((uint)newCapacity > Array.MaxLength)
newCapacity = Array.MaxLength;
if (newCapacity < capacity)
newCapacity = capacity;
return newCapacity;
}
容量は2倍ずつ拡張される
これにより、要素追加の償却計算量がO(1) になります。
例：
- 容量0 → 4 → 8 → 16 → 32 → 64...
頻繁な再確保による計算量の増加を避けつつ、メモリの無駄遣いも抑えるバランスの取れた仕組みです。
容量拡張時のコピーコスト
重要なのは、容量を拡張する際には全要素のコピーが発生するという点です。GrowメソッドとCapacityのsetterを見てみましょう。
internal void Grow(int capacity)
{
Capacity = GetNewCapacity(capacity);
}
public int Capacity
{
set
{
if (value != _items.Length)
{
if (value > 0)
{
T[] newItems = new T[value];
if (_size > 0)
{
Array.Copy(_items, newItems, _size); // 全要素をコピー！
}
_items = newItems;
}
}
}
}
容量拡張のプロセス：
- 新しい大きな配列を確保
- 既存の全要素を新しい配列にコピー
- 古い配列を破棄（GCの対象に）
例えば、要素が100個ある状態で容量が不足した場合：
- 新しい容量200の配列を確保
- 100個の要素をすべてコピー（O(n)の操作）
- その後、新しい要素を追加
償却O(1)の意味
1回の追加操作だけを見ると、容量拡張時はO(n)のコストがかかります。しかし、容量を2倍にする仕組みにより、拡張の頻度が指数的に減少します。
- 1個目追加：拡張（0→4）
- 5個目追加：拡張（4→8）、4個コピー
- 9個目追加：拡張（8→16）、8個コピー
- 17個目追加：拡張（16→32）、16個コピー
n個の要素を追加する際の総コピー回数は約 4 + 8 + 16 + ... ≈ 2n となり、1要素あたり平均O(1)に収まります。
パフォーマンスへの影響
多数の要素を追加することがわかっている場合は、コンストラクタで初期容量を指定するか、EnsureCapacityを使うことで、不要なコピーを避けられます。
// 悪い例：何度も容量拡張とコピーが発生
var list = new List<int>();
for (int i = 0; i < 10000; i++)
{
list.Add(i);
}
// 良い例：最初から十分な容量を確保
var list = new List<int>(10000);
for (int i = 0; i < 10000; i++)
{
list.Add(i); // コピーは一切発生しない
}
要素の追加
Add メソッド
public void Add(T item)
{
_version++;
T[] array = _items;
int size = _size;
if ((uint)size < (uint)array.Length)
{
_size = size + 1;
array[size] = item;
}
else
{
AddWithResize(item);
}
}
最適化のポイント
- 容量に余裕がある場合は単純に配列に追加（高速パス）
- 容量不足の場合のみ
AddWithResizeを呼び出す -
AddWithResizeはNoInlining属性により、Addのコード品質を保つ
Insert メソッド
挿入位置以降の要素をすべてシフトする必要があるため、O(n)の操作です。
public void Insert(int index, T item)
{
if (_size == _items.Length)
{
GrowForInsertion(index, 1); // 拡張と要素移動を同時に実行
}
else if (index < _size)
{
Array.Copy(_items, index, _items, index + 1, _size - index);
}
_items[index] = item;
_size++;
_version++;
}
GrowForInsertionは、配列の拡張と要素の移動を1回で行う最適化された実装です。
internal void GrowForInsertion(int indexToInsert, int insertionCount = 1)
{
int requiredCapacity = checked(_size + insertionCount);
int newCapacity = GetNewCapacity(requiredCapacity);
T[] newItems = new T[newCapacity];
// 挿入位置より前の要素をコピー
if (indexToInsert != 0)
{
Array.Copy(_items, newItems, length: indexToInsert);
}
// 挿入位置より後の要素を、挿入スペースを空けてコピー
if (_size != indexToInsert)
{
Array.Copy(_items, indexToInsert, newItems,
indexToInsert + insertionCount, _size - indexToInsert);
}
_items = newItems;
}
最適化のポイント
通常の拡張では「全要素をコピー」→「要素をシフト」の2段階になりますが、GrowForInsertionでは、
- 新しい配列に挿入位置より前をコピー
- 挿入位置より後を、挿入スペースを空けてコピー
各要素ごとに1回のコピー操作で完了します。これにより、挿入時のパフォーマンスが向上します。
要素の削除
RemoveAt メソッド
public void RemoveAt(int index)
{
_size--;
if (index < _size)
{
Array.Copy(_items, index + 1, _items, index, _size - index);
}
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
_items[_size] = default!; // GCのために参照をクリア
}
_version++;
}
削除後の要素をシフトするため、こちらもO(n)の操作です。参照型の場合は、メモリリークを防ぐために削除位置の参照をクリアします。
RemoveAll メソッド
条件に一致する要素をすべて削除する効率的な実装です。
public int RemoveAll(Predicate<T> match)
{
int freeIndex = 0;
// 削除不要な要素を見つける
while (freeIndex < _size && !match(_items[freeIndex]))
freeIndex++;
if (freeIndex >= _size) return 0;
int current = freeIndex + 1;
while (current < _size)
{
// 残す要素を前に詰める
while (current < _size && match(_items[current]))
current++;
if (current < _size)
{
_items[freeIndex++] = _items[current++];
}
}
// 参照のクリアとサイズ更新
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
Array.Clear(_items, freeIndex, _size - freeIndex);
}
int result = _size - freeIndex;
_size = freeIndex;
_version++;
return result;
}
1回のパスで削除を完了するため、素朴な実装（削除の繰り返し）よりも効率的です。
バージョン管理による列挙中の変更検知
internal int _version;
_versionは、コレクションが変更されるたびにインクリメントされます。Enumeratorはこれを利用して、列挙中にコレクションが変更されたかを検知します。
public bool MoveNext()
{
if (_version != _list._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
// ...
}
これにより、以下のようなコードは例外をスローします。
foreach (var item in list)
{
list.Add(newItem); // InvalidOperationException!
}
TrimExcess：メモリの最適化
public void TrimExcess()
{
int threshold = (int)(((double)_items.Length) * 0.9);
if (_size < threshold)
{
Capacity = _size;
}
}
要素数が容量の90%未満の場合、配列を縮小してメモリを節約します。要素の追加が終わった後に呼び出すと効果的です。
パフォーマンス特性のまとめ
| 操作 | 計算量 | 備考 |
|---|---|---|
インデックスアクセス list[i]
|
O(1) | 配列なので高速 |
末尾への追加 Add
|
償却O(1) | 容量拡張時のみO(n) |
先頭・中間への挿入 Insert
|
O(n) | 要素のシフトが必要 |
削除 Remove/RemoveAt
|
O(n) | 要素のシフトが必要 |
検索 Contains/IndexOf
|
O(n) | 線形探索 |
ソート Sort
|
O(n log n) | Array.Sortを使用 |
List vs LinkedList
List（動的配列）を使うべき場合
- インデックスアクセスが頻繁
- 末尾への追加が主な操作
- メモリの局所性が重要（キャッシュ効率）
- 要素数が予測可能
LinkedList（連結リスト）を使うべき場合
- 先頭や中間への挿入・削除が頻繁
- 要素数が大きく変動する
- インデックスアクセスが不要
実際には、ほとんどのケースでListの方が高速です。現代のCPUはキャッシュ効率が重要であり、連続したメモリ配置は大きなアドバンテージになります。
まとめ
List<T>は「リスト」という名前ですが、内部実装は動的配列です。
- 高速なインデックスアクセス
- メモリ効率の良い連続配置
- 末尾への追加は高速
- 中間への挿入・削除は低速
この特性を理解して使用することで、より効率的なコードを書くことができます。用途に応じて適切なコレクションを選択しましょう。