循環リスト【circular linked list】環状リスト

概要

循環リスト（circular linked list）とは、基本的なデータ構造の一つで、要素を数珠繋ぎにした連結リスト(linked list)のうち、先頭や末尾が存在せず、円環状に要素が繋がれているもの。

連結リストは複数のデータを格納するデータ構造の一つで、各要素がデータ（値やデータ構造など）の他に、隣の要素へのリンク（メモリなどにおける位置情報）を持っているようなものを指す。リンクをたどっていくことで各要素の順番にアクセスすることができる。

循環リストは先頭も末尾もなく、各要素が全体で円環をなすように連結されており、ある要素を起点に隣の要素を次々にたどっていくと、もとの要素に戻ってくる。実装上は便宜上の「先頭」と「末尾」が設定され、先頭の次を末尾、あるいは末尾の前を先頭とするようにリンクを設定することが多い。

循環リストのうち、それぞれの要素が「次」（後）の要素へのリンクを持ち、ある特定の一方向にのみ要素をたどることができるものを「単方向循環リスト」（circular singly linked list）あるいは「片方向循環リスト」、これに加えて「前」の要素へのリンクも持ち、逆方向にもたどることができるものを「双方向循環リスト」（circular doubly linked list）という。

(2021.12.17更新)