定義
連結リストは、各ノードがデータと次のノードへのポインタを持つデータ構造です。 配列と異なりメモリに連続して格納されないため、中間への挿入/削除が効率的です。
主な特性
- ✓動的サイズ: 配列と異なりサイズが固定されず、必要に応じて増えます。
- ✓ノード構造: 各ノードは[データ | nextポインタ]で構成されます。
- ✓head/tail: リストの先頭(head)と末尾(tail)を指すポインタがあります。
- ✓順次アクセス: インデックスで直接アクセスできず、headから順番に探索する必要があります。
活用事例
こんな場面で使われます:
🔄
頻繁な挿入/削除
中間にデータを頻繁に追加/削除する場合、配列より効率的です。
📚
スタック/キュー実装
連結リストでスタック(LIFO)とキュー(FIFO)を効率的に実装できます。
🎵
音楽プレイリスト
前/次の曲への移動がある再生リストに適しています(双方向連結リスト)。
↩️
Undo機能
エディタの元に戻す機能の実装に連結リストが使用されます。
主な操作
主な操作:
append(value)
O(1)リストの末尾(tail)に新しいノードを追加します。
prepend(value)
O(1)リストの先頭(head)に新しいノードを追加します。
insert(index, value)
O(n)特定のインデックス位置に新しいノードを挿入します。その位置までの探索が必要です。
delete(index)
O(n)特定のインデックスのノードを削除します。前のノードのポインタを修正します。
search(value)
O(n)特定の値を持つノードを探します。headから順番に探索します。
計算量
時間計算量
最良
O(1)
平均
O(n)
最悪
O(n)
空間計算量
O(n)
可視化でより深く理解する
ステップごとのアニメーションとコード実行を通じて、アルゴリズムの動作を直接確認してください。
可視化を開始