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