連結リスト
連結リストとは各ノードに別のノードへのリンクを持つことによりデータ間を連結していくデータ構造になっています。
リンクリストとも呼ばれます。
又、連結リストにはいくつか種類があります。
今回の記事では線形リストについて説明していきます。
連結リストの種類
- 片方向リスト
- 双方向リスト
連結リストの基本的な構造には2種類があります。
連結リストの特徴
連結リストは使い勝手のいいデータ構造なのですが、メリットとデメリットがあります。
メリット
- 配列と違って可変な長さを持てる(半無限的にデータを追加可能)
- ノードの挿入、削除に掛かるコストが小さい(リストの種類や使い方にもよる)
デメリット
- 配列と比べて検索やソートの処理に掛かるコストが大きい
- リンクの情報を持つ分だけ配列よりデータ量が多くなる
他にもありますが、大きくはこんな感じになるかと思います。
連結リストの仕組み
連結リストの各種類について実装を説明していきます。
片方向リスト
片方向リストとは各ノードが次のノードへのリンクのみ持っているリスト構造です。
※単方向リストとも呼ばれます。
ノード上に値(データ)とリンクを持っています。
各ノードは次のノードへのみ参照可能です。
このリストでは手前のノードに対して参照はできません。
双方向リスト
双方向リストとは各ノードが前後両方のリンクを持っているリスト構造です。
片方向と同じで値(データ)とリンクを持っています。
ただし、各ノードは前後のノードへの参照が可能です。
遡って参照が可能なので便利ですが、その分リンクの情報が増えます。