双方向リスト【doubly linked list】双方向連結リスト

概要

双方向リスト（doubly linked list）とは、基本的なデータ構造の一つである線形リスト(linear linked list)のうち、各要素が自分の「次」と「前」の要素へのリンクを持ち、先頭側から末尾側へも、逆方向にも要素をたどっていくことができるもの。

線形リストは連結リスト（linked list）の一種で、各要素が自身のデータと共に、隣の要素へのリンク（メモリなどにおける位置情報）を持ち、先頭から末尾まで要素が数珠繋ぎに並んでいる。このうち、各要素が自身の次の要素と前の要素へのリンクを持ち、先頭から末尾へ、あるいは末尾から先頭へ順番にアクセスしていくことができるような構造のものを双方向リストという。

一方、各要素が自身の「次」の要素へのリンクしか持たず、先頭側から末尾側へ一方向にのみたどっていくことができるような線形リストは「単方向リスト」（singly linked list）あるいは「片方向リスト」という。

なお、要素が円環状に連結されている「循環リスト」（circular linked list）にも、各要素が両隣へのリンクを持ち、どちらの方向にも移動できる「双方向循環リスト」（circular doubly linked list）が存在するが、単に「双方向リスト」といった場合は慣習上、双方向線形リストを指すことが多い。

(2021.12.17更新)