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

2019年11月25日データ構造入門,データ構造,連結リスト

連結リストとは

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

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

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

連結リストの具体例

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

連結リストの具体例

連結リストの種類

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

片方向リスト(Singly Linked List)

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

双方向リスト(Doubly Linked List)

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

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

循環リスト(Circular Linked List)

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

片方向リスト・双方向リスト・循環リストの図