【C#データ構造】ListとLinkedListの違い

はじめに

paiza　で連結リストの問題が出てきたので気になって調べました。
C#の List<T> と LinkedList<T> はどちらもコレクションを表現するためのデータ構造ですが、その内部構造や用途が異なります。それぞれの違いをまとめました。

1. 内部構造

LinkedList<T> の内部構造

LinkedList<T> は、**連結リスト（doubly-linked list, 両方向連結リスト）**として実装されています。この構造では、各要素（ノード）が以下のようなデータを持っています。

1. 値（Value）: ノードに格納されるデータ。
2. 前のノードへの参照（Previous）: 自分の前のノードを指すポインタ。
3. 次のノードへの参照（Next）: 自分の次のノードを指すポインタ。

これにより、以下の操作が効率的になります：

• あるノードを削除する際は、その前後のノード同士を直接つなぎ直すだけで済む。（両方向連結リストのため）
• ノードを挿入する際は、挿入位置の前後のノードとリンクを設定するだけで済む。（両方向連結リストのため）

List<T> の内部構造

List<T> は**動的配列（dynamic array）**として実装されています。この構造では以下のようなデータを持っています。

1. すべての要素は連続したメモリに格納されます。
2. 配列サイズが不足すると、新しい大きな配列を確保してすべての要素をコピーする必要があります。

これにより、以下の挙動が発生します：

• 挿入: 特定の位置に要素を挿入する場合、その位置以降のすべての要素を1つずつ後ろにずらす必要があります（O(N)）。
• 削除: 特定の位置から要素を削除する場合、その位置以降のすべての要素を1つずつ前に詰める必要があります（O(N)）。

内部構造の比較まとめ

特徴	List<T>	LinkedList<T>
基盤	配列（動的にサイズを拡張可能）	連結リスト（各要素がノードとしてリンク）
ストレージ	連続したメモリ領域	メモリ上で分散しているノード
データ保持	インデックスを使ってランダムアクセス可能（O(1)）	各ノードが次と前のノードへのポインタを保持

2. パフォーマンスと操作の違い

パフォーマンスの違いまとめ

操作	List<T> パフォーマンス	LinkedList<T> パフォーマンス
末尾への追加	O(1)（容量不足時は O(N)）	O(1)
先頭への追加	O(N)	O(1)
中間への追加	O(N)	O(1)（ノード探索時間を除く）
末尾の削除	O(1)	O(1)
先頭の削除	O(N)	O(1)
中間の削除	O(N)	O(1)（ノード探索時間を除く）
ランダムアクセス	O(1)	O(N)
要素の検索（特定の値）	O(N)	O(N)

LinkedList<T>の挿入・削除が速い理由

LinkedList<T> はノード間をポインタで結びつけているため、リンクを更新するだけで済むため効率的です。具体的には以下の手順で操作が行われます。

挿入操作

1. 挿入する位置のノードを見つける $O(N)$。
2. 挿入したいノードを新たに作成。
3. 挿入位置の前後のノードを新しいノードにリンク付けし直す $O(1)$。

削除操作

1. 削除するノードを見つける $O(N)$。
2. 削除するノードの前後のノードを直接リンク付けする $O(1)$。
3. 削除するノードを削除。

3. 主な用途

用途	List<T>	LinkedList<T>
要素の頻繁な追加・削除	- 主に末尾での操作が多い場合に最適（スタックやキュー用途）。	- 頻繁な先頭/中間での追加・削除に適している。
ランダムアクセス	- 要素をインデックスで頻繁にアクセスする場合に適している。	- 順次データ処理に使用する場合に適している。
メモリ効率	- メモリは連続して使用されるため効率が良い。	- ポインタを保持する分、メモリオーバーヘッドが大きい。
データの順序が重要な場合	- 既存順序を維持する。	- 順序を動的に変更したり、データの再編成が必要な場合に便利。

4. 使用例

List<T>

• 使用場面: ランダムアクセスが必要な場合、要素を頻繁に並び替えたい場合、大量のデータを扱う場合。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> list = new List<int> { 1, 2, 3, 4, 5 };
        list.Add(6);           // 末尾に追加
        list.RemoveAt(2);      // インデックスで削除
        Console.WriteLine(list[1]); // ランダムアクセス
    }
}

LinkedList<T>

• 使用場面: 頻繁な挿入/削除が必要な場合、データが動的に変更される場合。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        LinkedList<int> linkedList = new LinkedList<int>();
        linkedList.AddLast(1);      // 末尾に追加
        linkedList.AddFirst(0);     // 先頭に追加
        linkedList.Remove(1);       // 要素を削除

        foreach (var item in linkedList) // 順次処理
        {
            Console.WriteLine(item);
        }
    }
}

5. 長所と短所

データ構造	長所	短所
List<T>	- ランダムアクセスが高速。	- 頻繁な挿入/削除でコストが高い。
	- メモリ使用が効率的。	- 容量超過時の再確保で時間がかかる。
LinkedList<T>	- 挿入/削除が柔軟かつ高速（先頭/末尾）。	- ランダムアクセスが遅い。
	- 動的データに適している。	- ポインタ保持によるメモリオーバーヘッド。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5