【図解】双方向循環リスト

現在取り組んでいる「push_swap」というアルゴリズムの課題で、「双方向循環リスト」を使う予定なので、「双方向循環リスト」についてまとめてみたい。

双方向循環リスト

まず、「双方向」とはどういうことかというと、1つの構造体がnextポインタとprevポインタを両方持っており、nextポインタが次の構造体を指し、prevポインタが一つ前の構造体を指している。

「循環」というのは、最後の構造体のnextポインタが、最初の構造体を指すようにし、構造体が循環させることを指す。

特徴としては、要素の検索には時間がかかるものの、 挿入、並べ替えや削除を高速で行うことができるので、名簿などのリスト管理によく使われる。

また「双方向連結リスト」とも呼ばれることもある。

番兵ノード(sentinel node)

双方向循環リストを作る際に、必須ではないのだが、「番兵ノード」というものをを設定する場合がある。

「番兵ノード」は、NULL（nilともいう）に相当するノードのことで、このノードがあることでリストを順に見ていっても、無限ループに陥らずに済ませることができる。

番兵ノードを使用しない場合は、常に先頭の要素を覚えておけば大丈夫だ。

図解

番兵ノードを加えた3つの構造体を有した「双方向循環リスト」を図解すると、以下のようになる。