線形リスト【linear linked list】

概要

線形リスト（linear linked list）とは、基本的なデータ構造の一つで、要素を数珠繋ぎにした連結リスト(linked list)のうち、先頭と末尾が存在するもの。連結リストのことを線形リストと呼ぶこともある。

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

線形リストは先頭の要素が2番目の要素を指し示し、2番目の要素が3番目を指し示し…という具合に、末尾まで一列に要素を連結した構造になっている。末尾の要素の「次」を表すリンクをどうするかは実装によるが、Null値など不存在を表す特別な値とすることが多い。

線形リストのうち、それぞれの要素が「次」（後）の要素へのリンクを持ち、先頭側から末尾側へ一方向にのみ要素をたどることができるものを「単方向リスト」（singly linked list）あるいは「片方向リスト」、これに加えて「前」の要素へのリンクも持ち、末尾側から先頭側へもたどることができるものを「双方向リスト」（doubly linked list）という。

一方、すべての要素が円環状に連なっており、先頭や末尾が存在しない（あるいは、先頭と末尾が連結されている）ような連結リストもあり、「循環リスト」（circular linked list）と呼ばれる。

(2021.12.17更新)