👋
【C#データ構造】ListとLinkedListの違い
はじめに
paiza で連結リストの問題が出てきたので気になって調べました。
C#の List<T> と LinkedList<T> はどちらもコレクションを表現するためのデータ構造ですが、その内部構造や用途が異なります。それぞれの違いをまとめました。
1. 内部構造
LinkedList<T> の内部構造
LinkedList<T> は、**連結リスト（doubly-linked list, 両方向連結リスト）**として実装されています。この構造では、各要素（ノード）が以下のようなデータを持っています。
- 値（Value）: ノードに格納されるデータ。
- 前のノードへの参照（Previous）: 自分の前のノードを指すポインタ。
- 次のノードへの参照（Next）: 自分の次のノードを指すポインタ。
これにより、以下の操作が効率的になります：
- あるノードを削除する際は、その前後のノード同士を直接つなぎ直すだけで済む。（両方向連結リストのため）
- ノードを挿入する際は、挿入位置の前後のノードとリンクを設定するだけで済む。（両方向連結リストのため）
List<T> の内部構造
List<T> は**動的配列（dynamic array）**として実装されています。この構造では以下のようなデータを持っています。
- すべての要素は連続したメモリに格納されます。
- 配列サイズが不足すると、新しい大きな配列を確保してすべての要素をコピーする必要があります。
これにより、以下の挙動が発生します：
- 挿入: 特定の位置に要素を挿入する場合、その位置以降のすべての要素を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> はノード間をポインタで結びつけているため、リンクを更新するだけで済むため効率的です。具体的には以下の手順で操作が行われます。
挿入操作
- 挿入する位置のノードを見つける
O(N) - 挿入したいノードを新たに作成。
- 挿入位置の前後のノードを新しいノードにリンク付けし直す
O(1)
削除操作
- 削除するノードを見つける
O(N) - 削除するノードの前後のノードを直接リンク付けする
O(1) - 削除するノードを削除。
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> | - 挿入/削除が柔軟かつ高速（先頭/末尾）。 | - ランダムアクセスが遅い。 |
| - 動的データに適している。 | - ポインタ保持によるメモリオーバーヘッド。 |
おすすめ・参考書籍
問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
Discussion