連結リスト
リストの各要素が次および前の要素へのリンク(参照)を持つデータ構造を連結リストといいます。
要素へのリンクがひとつ(次)だけなら単方向リストと呼ばれ、リンクをふたつ(次と前を)もつ連結リストは双方向リストと呼ばれます。さらに終端の要素のリンクが先頭の要素へのリンクなら循環リストになります。
特徴
連結リストの特徴は要素を参照するのにリンクを順にたどっていくシーケンシャルアクセスしかできないことです。いっぽう配列はインデックスを指定するランダムアクセスが可能です。また連結リストは要素がリンクを持たねばならずその分メモリを消費することになります。
ちょっと不便に思える連結リストがなぜ使われるのでしょう？それは要素の挿入や削除が簡単に行えるからです。
例えば要素を挿入する場合、単純なリスト(配列)は挿入位置から後ろの要素をすべてずらさなければなりません。これに対し連結リストは挿入位置のリンク(参照)を書き換えるだけで済みます。
連結リストの種類
単方向リスト - Singly-linked list
連結リストの中で一番シンプルなのが単方向リストです。各要素はひとつのリンクを持ちます。リンクはリスト中の次の要素を指します。最後の要素のリンクには null を用いて終端をあらわします。
循環リスト - Circularly-linked list
単方向リストの終端の要素に先頭のリンクを持たせたのが循環リストです。終端が来ても先頭に戻れるので環状に並んだデータ構造になります。
双方向リスト - Doubly-linked list
双方向リストは各要素が前後の要素を示すリンクを持つデータ構造です。終端から先頭へのリンクを設定すれば循環リストになります。
