リストとは

リスト（連結リスト）とは、各要素が次の要素の位置（ポインタ）を持ち、それをたどることで要素を順番につなげたデータ構造である。

要素の挿入や削除はポインタを付け替えるだけで済むため、配列のように要素をずらす必要が無い。一方、特定の位置の要素に直接アクセスできず、先頭から順にたどる必要がある。次の要素だけを指す単方向リスト、前後を指す双方向リスト、末尾が先頭につながる循環リストがある。