連結リストとは、ノードと呼ばれるデータ要素の集まりで、各ノードが次のノードを指し示すチェーンのような構造を形成するデータ格納方法です。
連結リストの例え
宝探しを想像してみてください。
それぞれの場所で、次の場所につながる手がかりを見つける手順を踏みます。最初のヒントからスタートし、次のヒント、さらにその次のヒントとたどっていき、最終的に宝までたどり着くます。各ヒントごとに次の行き先は一箇所に向かう形になります。
連結リストはこの宝探しに似ています。宝探しの各ヒントが次の場所を指しているように、アイテムそれぞれが次のアイテムを指しているということです。
ノードとは
プログラミングでは、それぞれの「手がかり」や「場所」はノードと呼ばれます。
すべてのノードには2つの主要な部分があります。
- Data: ノードが保持する実際の値や情報
- Next: シーケンス内の次のノードへのポインタ（または手がかり）
連結リストの例
好きな果物の連結リストがあるとします。最初のノードには以下が含まれています。
- Data = リンゴ
- Next = 次の果物を指す
2番目のノードには以下が含まれています。
- Data = バナナ
- Next = 次の果物を指す
3番目のノードが「さくらんぼ」で、他の果物を指していなければそのリストは終わりです。
視覚的には次のように考えます。
リンゴ->バナナ->さくらんぼ
リンゴから始めてさくらんぼを見つけたい場合は、宝探しのヒントと同じように、まずバナナを通過しなければなりません。
連結リストのバリエーション
連結リストにはバリエーションがあります。
- 二重連結リスト: 1つのヒントが前方を指す代わりに、後方を指すヒントが追加されます。すべてのノードがデータ、次のノードへのポインタ、前のノードへのポインタを持っています。
- 円形連結リスト: 最後の場所/手がかりが最初の場所に戻ることを指し示します。
連結リストのメリット・デメリット
プログラミングでは、連結リストは動的なサイズ変更を可能にするのでよく利用されます。
サイズが固定されている配列とは異なり、連結リストは必要に応じて簡単に大きくしたり小さくしたりできます。しかし、その代償として、連結リストの途中の要素にアクセスする際に、最初から始めて目的の項目に到達するまで手がかり（またはポインタ）をたどる必要があるため、時間がかかることがあります。