単方向リスト【singly linked list】片方向リスト / 単方向連結リスト / 片方向連結リスト

概要

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

線形リストは連結リスト（linked list）の一種で、各要素が自身のデータと共に、隣の要素へのリンク（メモリなどにおける位置情報）を持ち、先頭から末尾まで要素が数珠繋ぎに並んでいる。

このうち、各要素が自身の「次」（後）の要素へのリンクを持ち、先頭から末尾に向かって順番にアクセスしていくことができるような構造のものを単方向リストという。各要素は自身の「前」の要素へのリンクは持たず、先頭方向に逆向きにたどることはできない。

一方、各要素が自身の「次」と「前」の両方の要素へのリンクを保持しており、先頭側から末尾側へも、その逆方向へもたどっていけるようになっている線形リストは「双方向リスト」（doubly linked list）という。

なお、要素が円環状に連結されている「循環リスト」（circular linked list）にも、各要素が一方の隣へのリンクしか持たない「単方向循環リスト」（circular singly linked list）あるいは「片方向循環リスト」が存在するが、単に「単方向リスト」といった場合は慣習上、単方向線形リストを指すことが多い。

(2021.12.17更新)