リスト構造とは

リスト構造

リストはデータ構造のひとつです。リスト構造のデータには、次のデータがメモリ上のどの位置にあるかを示す「ポインタ」と呼ばれる情報が付与されています。

以下はリスト構造のイメージ図です。

リスト構造のデータには「ポインタ」が付与されており、この「ポインタ」をたどることで、リスト内の各データにアクセスすることができます。

リストの特徴はデータの追加・挿入・削除を容易に行うことができるところです。（ポインタを書き換えるだけで、いくらでもデータをつなぎ替えることができる）

データの挿入

例えば、次のリストの2番目と3番目（※先頭を1番目として数える）の間にデータ（メモリ上のアドレス：50、データ：データ5）を挿入してみます。

「データ2」と「データ3」の間に挿入するので、次の図のように「データ2」のポインタを「30→50」に書き替え、挿入する「データ5」のポインタを「30」にします。

データの削除

次のリスト構造からリストの3番目（※先頭を1番目として数える）のデータを削除してみます。

「データ3」を削除するので、次の図のように「データ2」のポインタを「30→20」に書き替えます。

リストの種類

リスト構造には「単方向リスト」「双方向リスト」「循環リスト」などがあります。

単方向リスト

単方向リストとは、リスト構造の基本的な形であり次のデータへのポインタを持つリストのことです。

双方向リスト

双方向リストとは、次のデータへのポインタと、前のデータへのポインタを持つリストのことです。単方向リストとは違い、次のデータと前のデータのポインタを持っているのが特徴です。

循環リスト

循環リストとは、単方向リストと同じで次のデータへのポインタを持つリストのことです。単方向リストとの違いは最後尾のデータが先頭データへのポインタを持っているところです。