リスト
リスト(英語:list)とは、最も基本的なデータ構造のひとつで、ある「データ」と「ポインタ」の組み合わせを一塊としたものである。 一部のプログラミング言語ではシーケンスとも呼ばれるが、データベース用語のシーケンスと紛らわしいのでオススメできない。
概要
ファイル:Singly-linked-list.svg リストは「データ」と「ポインタ」の組み合わせである。 ポインタにより「次のデータ」を容易に特定でき、何かと嬉しい。
リストにはいくつかの種類がある。
また、ひとつリスト要素にポインタが複数個あり、ネストしたものをツリーという。
さらにリストからデータを出し入れする方法を規則的に縛ったものをスタックやキューという。
リストと配列
リストは配列と非常によく似たデータ構造である。 配列は特定のデータ長(いわゆる固定長)で連続したメモリ空間を確保することにより、データ長と添字を掛け合わせることで動的にデータ位置を特定し、リストから「次のデータを示すポインタ」を排除することでメモリ使用効率を向上させたものと言える。
データ[0] | データ[1] | データ[2] | データ[3] |
↑ポインタ位置 |
リストでランダムアクセスしようとすると頭から順番にポインタを辿らなければ目的の値に到達できないのに対して、配列は単純計算で位置を割り出せるという利点がある。
一方で、データを挿入する場合は、リストであればポインタを書き換えるだけで済むが、配列では新しい配列を作って古いデータをコピーするという非常に重たい処理をすることになる。
なお、最近のプログラミング言語の多くは配列とリストを区別していないものもが多く、そのほとんどはマニュアルなど対外的には「配列」をうたっているが、内部的に「リスト」となっているものばかりである。よって区別するだけ無駄であり、プログラミング言語の実装者でもないのにそのような些細なことを気にすると頭皮に悪影響を及ぼす恐れがある。