[C#] System.Collections.Generic.LinkedList<T> — 双方向連結リストの仕組みと使いどころ

System.Collections.Generic.LinkedList<T> は、双方向連結リスト を実装したジェネリックコレクションです。配列ベースの List<T> と違い、要素はノードオブジェクトとして個別にヒープ上に確保され、隣接ノードへの前後リンクで繋がっています。「連続したインデックスアクセス」よりも「任意位置への高速な挿入・削除」を重視する場面で活躍します。

`LinkedList<T>` とは

名前空間：System.Collections.Generic
内部構造：双方向連結リスト（LinkedListNode<T> のチェイン）
各ノードは値・前ノード・次ノードを保持
インデックス（list[i]）はサポートしない
既知のノード経由の挿入・削除は O(1)

var list = new LinkedList<string>();
list.AddLast("apple");
list.AddLast("banana");
list.AddFirst("cherry");

LinkedListNode<string> banana = list.Find("banana")!;
list.AddBefore(banana, "blueberry");
list.AddAfter(banana, "blackberry");

foreach (var s in list)
    Console.WriteLine(s); // cherry, apple, blueberry, banana, blackberry

サポートするインターフェース

インターフェース	役割
`ICollection<T>`	`Count` / `Add` / `Remove` / `Contains` / `CopyTo`
`IReadOnlyCollection<T>`	読み取り専用の `Count`
`IEnumerable<T>`	`foreach` で先頭から末尾の順に列挙
`ICollection`	非ジェネリック版（互換）
`IEnumerable`	非ジェネリック版（互換）
`ISerializable` / `IDeserializationCallback`	バイナリシリアライズ

IList<T> は実装しない 点に注意してください。インデックスでのランダムアクセスをサポートしないためです。これは LinkedList<T> の設計思想を表しています。

各インターフェースの詳細は次を参照してください。

ICollection: ArrayList の記事
IEnumerable / IEnumerator: IEnumerable と IEnumerator の記事

`LinkedListNode<T>`

LinkedList<T> の操作は ノード（LinkedListNode<T>）を経由する のが特徴です。Find でノードを取得すれば、その前後への挿入・そのノード自身の削除がすべて O(1) で行えます。

public sealed class LinkedListNode<T>
{
    public LinkedList<T>?     List     { get; }
    public LinkedListNode<T>? Previous { get; }
    public LinkedListNode<T>? Next     { get; }
    public T                  Value    { get; set; }
}

ノードは 常にどれか 1 つのリストに属する。AddLast(node) などで他のリストに渡そうとすると例外。移動したいときは値を取り出して新しいノードを作ります。

主な API と計算量

操作	API	計算量
先頭追加	`AddFirst(value)`	O(1)
末尾追加	`AddLast(value)`	O(1)
任意位置挿入	`AddBefore(node, v)` / `AddAfter(node, v)`	O(1)
ノード削除	`Remove(node)`	O(1)
値で検索	`Find(value)` / `FindLast(value)`	O(n)
値で削除	`Remove(value)`	O(n)
含有判定	`Contains(value)`	O(n)
列挙	`foreach`	O(n)
インデックスアクセス	（非対応）	—

「ノード参照を持っている」状態なら挿入・削除は O(1)。ノードが手に入れば嬉しいが、値から探すのは O(n) という性能トレードオフを理解しておきましょう。

`List<T>` との比較

観点	`List<T>`	`LinkedList<T>`
内部構造	動的配列	双方向連結リスト
インデックスアクセス	O(1)	非対応
末尾追加	O(1) 償却	O(1)
先頭追加	O(n)	O(1)
任意位置挿入（位置既知）	O(n)	O(1)（ノード既知時）
任意位置削除（位置既知）	O(n)	O(1)（ノード既知時）
メモリオーバーヘッド	小（配列のみ）	大（ノード毎に前後ポインタ）
キャッシュ局所性	高	低（ノードが点在）

実は 大量要素の単純な挿入・削除でも List<T> のほうが速いことが多い。連結リストは「ノード割り当て」「前後ポインタ更新」「キャッシュミス」のコストが意外に重く、List<T> のメモリコピーが現代の CPU では非常に速いためです。

LinkedList<T> を選ぶべきは、「ノード参照を保持していて、その場で挿入・削除する」 ような特殊な用途に限られます。

使いどころ

1. LRU キャッシュ

「最近使われたものを末尾に動かす」「容量超過時に先頭を捨てる」を すべて O(1) で行うには、Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> と LinkedList<KeyValuePair<TKey, TValue>> の組み合わせが定番です。

public sealed class LruCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly LinkedList<KeyValuePair<TKey, TValue>> _list = new();
    private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> _map = new();

    public LruCache(int capacity) => _capacity = capacity;

    public bool TryGet(TKey key, out TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            _list.Remove(node);
            _list.AddLast(node);              // ノード再利用：O(1)
            value = node.Value.Value;
            return true;
        }
        value = default!;
        return false;
    }

    public void Put(TKey key, TValue value)
    {
        if (_map.TryGetValue(key, out var existing))
        {
            _list.Remove(existing);
            _map.Remove(key);
        }
        if (_list.Count >= _capacity)
        {
            var oldest = _list.First!;
            _list.RemoveFirst();
            _map.Remove(oldest.Value.Key);
        }
        var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(new(key, value));
        _list.AddLast(node);
        _map[key] = node;
    }
}

2. 双方向に走査するイテレーション

ノードから前後どちらにも進める性質を活かし、双方向リスト構造そのものをモデル化 したい場面（テキスト編集の行管理、タイムラインの前後移動など）で素直に書けます。

3. 頻繁な中間挿入・削除＋ノード参照の保持

ゲームのエンティティリスト、エフェクトの管理キューなどで、ノード参照を別 Dictionary などに保持しておくと O(1) で取り外せます。

向かないケース

インデックスでの参照が必要 → List<T>
末尾追加と末尾参照だけ → List<T> で十分
要素数が少ない → List<T> のほうが定数倍で勝つ
シンプルな FIFO / LIFO → Queue<T> / Stack<T>

注意点

null 要素も格納可能（T が参照型または Nullable<T> の場合）。Find は null を渡せる。
同一ノードを別のリストに渡すと例外。値を取り出して新しいノードを作る。
スレッドセーフではない。読み取りすら同時アクセスは安全でない。
列挙中の変更で InvalidOperationException。

まとめ

LinkedList<T> は 双方向連結リスト。インデックスアクセスはなく、ノード経由の操作が中心。
ICollection<T> / IEnumerable<T> を実装。IList<T> は実装しない。
ノード既知での挿入・削除は O(1)、値から探すと O(n)。
実務では List<T> のほうが速い場面が多い。LinkedList<T> の真価は LRU キャッシュなど「ノード参照を持って O(1) で取り外したい」場面 で発揮される。

LinkedList<T> とは