連結リスト(Linked List)のデータ構造

連結リストとは

連結リストはノードと呼ばれるデータの塊が、複数繋がってできたデータ構造です。

1つのノードは、格納する値自体と、次のノードへのアドレスを保持します。先頭から各ノードを辿ることで、線形に連結リストを探索することができます。

最初のノードはHeadと呼ばれるものがアドレスを保持し、連結リストの最後はNullで終了します。

\(3,11,24,5,2,18\)を並べた連結リストの具体例が以下のようになっています。

連結リストにはバリエーションがあり、使用するアルゴリズムによって使い分ける必要があります。

先程までの説明は全て片方向リストの説明です。Headから始まり、Nullで終わりますが、ノードを逆に戻ることはできません。

片方向リストのノードが持つアドレスは、次のノードのものだけでした。

双方向リストのノードは、1つ前のノードのアドレスも保持するので、逆方向にも連結リストを辿ることができます。

循環リストは最後がNullへとつながるのではなく、先頭のノードへ戻っていく循環したデータ構造です。