連結リスト - 基本情報処理技術者試験に合格しよう

連結リストは最も基本的なデータ構造の1つでありデータ部とポインタ部で構成されます。ポインタ部には連結リストの種類により、次のデータや前のデータの格納場所が入っている為、それをたどることによってデータを取り出すことが出来ます。

最も単純な連結リストであり、データ毎に1つのをポインタを持っている。このポインタはリスト上の次のデータを指し、リストの最後尾ならNull値を格納するか、空のリストを指す。

データ毎に2つのリンクがあり1つが次のデータ、もう1つが後ろのデータを指す。リストの先頭のデータには後ろのデータがないので、後方ポインタにはNull値を格納するか、空のリストを指す。リストの最後尾のデータには次のデータがないので、前方ポインタにはNull値を格納するか、空のリストを指す。

先頭と最後尾のデータを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合は任意のデータから出発して、好きな方向にたどっていき、最初のデータに戻ってくるまで続ける。つまり、循環リストは先頭や最後尾といったものが存在しないリストと考えることもできる。