この記事での学習内容 ITパスポート 基本情報 応用情報

リストの考え方、その操作を理解する。

用語例：線形リスト、単方向リスト、双方向リスト、環状リスト、リンク付きリスト

配列のデメリットとリスト

配列では、要素の追加・挿入をする場合に、挿入する位置以降のすべての要素を１つずつずらす処理が必要になるため、要素の数が大量の場合は処理に時間がかかります。
つまり、要素の追加や削除が非効率という欠点があります。

この欠点を踏まえ、追加や削除を効率良く行うことが出来るように工夫されたデータ構造が「リスト」です。

リスト（線形リスト）

リストは同じ型のデータを集めて、それぞれに「自分の次のデータがどれか」という情報（＝ポインタ）を持たせて連結したものです。データは物理的に順番に並んでいる必要はありません。

リストの中のデータは、データ部とポインタ部からなります。
データ部には実際のデータが、ポインタ部には次のデータの格納場所が入っています。ポインタ部に入っているメモリ城の格納場所のことをアドレス（番地）といいます。

なお、リスト構造には配列のような添字という概念はありません。そのため、配列のように添え字を使って任意の要素にアクセスする、ということが出来ません。

単方向リストと双方向リスト

リストには、次へのポインタのみを持つ単方向リストと、前後へのポインタを両方持つ双方向リストがあります。

単方向リストは先頭からデータを探すことしか出来ないので、後ろの方のデータを見つけるには時間がかかります。

双方向リストは両方向のポインタを持つため、単方向リストよりもサイズは大きくなりますが、各データの前後、およびリストの先頭、末尾を示すポインタを持っているので、データを後ろから探索することも出来ます。

リスト構造への追加と削除

リスト構造のデータはポインタを保つ必要があるため、配列よりも大きくなりますが、データの挿入や削除をする際、その前後のポインタを書き換えるだけで済むので、データを頻繁に更新する場合に適しています。

環状リスト

単方向リストでは、末尾のデータの「次へのポインタ」は空になります。また、双方向リストでは、先頭のデータの「前へのポインタ」と、末尾のデータの「次へのポインタ」は空になります。
これらを空にせずに、データが環状につながっているようにしたものが環状リストです。

環状リストにはポインタを1つ持つ単方向リストを基にするものと、ポインタを2つ持つ双方向リストを基にするものとがあります。