「リスト」を編集中

'''リスト'''（[[英語]]：list）とは、最も基本的な[[データ構造]]のひとつで、ある「[[データ]]」と「[[ポインタ]]」の組み合わせを一塊としたものである。
一部の[[プログラミング言語]]では[[シーケンス]]とも呼ばれるが、[[データベース]]用語のシーケンスと紛らわしいのでオススメできない。

==概要==
リストは「[[データ]]」と「[[ポインタ]]」の組み合わせである。
ポインタにより「次のデータ」を容易に特定できて嬉しい。

リストにはいくつかの種類がある。
* [[片方向リスト]]
* [[双方向リスト]]
* [[線形リスト]]
* [[循環リスト]]

また、ひとつリスト要素にポインタが複数個あり、[[ネスト]]したものを[[ツリー]]という。

==リストと配列==
リストは[[配列]]と非常によく似た[[データ構造]]である。
[[配列]]は特定の[[データ長]]（いわゆる[[固定長]]）で連続したメモリ空間を確保することにより、[[データ長]]と[[添字]]を掛け合わせることで動的にデータ位置を特定し、リストから「次のデータを示すポインタ」を排除することでメモリ使用効率を向上させたものと言える。
{| class="wikitable"
|-
|  データ[0]　　|| データ[1] 　　|| データ[2]　　 || データ[3]　　
|-
| || ↑ポインタ位置 || ||
|}
リストでランダムアクセスしようとすると頭から順番にポインタを辿らなければ目的の値に到達できないのに対して、配列は単純計算で位置を割り出せるという利点がある。

一方で、データを挿入する場合は、リストであればポインタを書き換えるだけで済むが、配列では新しい配列を作って古いデータをコピーするという非常に重たい処理をすることになる。

なお、最近の[[プログラミング言語]]の多くは配列とリストを区別していないものもが多く、そのほとんどはマニュアルなど対外的には「配列」をうたっているが、内部的に「リスト」となっているものばかりである。よって区別するだけ無駄であり、プログラミング言語の実装者でもないのにそのような些細なことを気にすると頭皮に悪影響を及ぼす恐れがある。

==関連項目==
*[[データ構造]]

==参考文献==
{{reflist}}

{{stub}}