広告 コンピュータ

リスト構造とは

リスト構造

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

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

リスト構造のイメージ例

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

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

データの挿入

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

リストにデータ挿入前

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

リストデータ挿入後

データの削除

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

データ削除前

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

データ削除後

リストの種類

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

単方向リスト

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

単方向リストのイメージ例

双方向リスト

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

双方向リストのイメージ例

循環リスト

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

循環リストのイメージ例

helpful