線形リスト | Programming Place Plus　用語集

名称

• 線形リスト　【linear linked list】

解説

連結リストの分類の１つで、要素の列に先頭と末尾が存在するもののことです。

リスト内の要素を辿っていくと、いつか末尾に行き着き、それ以上は進めなくなります。同様に、逆方向に辿ったとすると、いつか先頭に行き着き、それ以上は進めなくなります。

線形リストに対して、先頭と末尾の概念がなく、要素が円環状に接続されている連結リストは、循環リストと呼ばれます。

また、連結リストをほかの観点で分類する考え方があり、後続の要素への参照情報のみをもつものを単方向リスト、前後の要素への参照情報をもつものを双方向リストと呼びます。たとえば、先頭と末尾の概念があり、前後の要素への参照情報がある連結リストは、線形リストであり双方向リストです（合わせて、双方向線形リストのように表現される場合もあります）。

連結リストの考え方や実装方法を、アルゴリズムとデータ構造編【データ構造】第３章、アルゴリズムとデータ構造編【データ構造】第４章で解説しています。