リスト (抽象データ型)
出典: フリー百科事典『ウィキペディア（Wikipedia）』
抽象データ型としてのリスト(list)は、順序つきのデータコンテナとして定義される。例えば、型のないミュータブルなリストはコンストラクタと4つの操作によって特徴付けられる:
- 空のリストを作るコンストラクタ
- リストが空かどうかを確かめる操作
- リストの先頭に要素を追加する操作（Lispの
cons） - リストの先頭要素("head")を求める操作（Lispの
car） - リストの先頭を除く部分リスト("tail")を求める操作（Lispの
cdr）
リストはたいてい配列や連結リストを使って実装される。これは配列や連結リストと似た特性を持っているからである。また連結リストのことを単にリストと呼ぶこともある。順序を持つ点を強調してシーケンス(列; sequence)と呼び、連結リストと区別することもある。
目次 |
[編集] 特性
リストは以下のプロパティを持つ。
- リストのサイズ - リスト内にいくつの要素があるかを示す。
- リストの等価性
- リストの型付け - リストの要素はリストの型と互換の型を持たなければならない。リストが配列を用いて実装されているときは型付けされているのが普通である。
- リスト中のすべての要素はインデックスを持つ。最初の要素はインデックス0（または他の定義された整数値）を持つ。続く要素は前の要素より1大きいインデックスを持つ。最後の要素は
(頭のインデックス) + (リストのサイズ) - 1というインデックスを持つ。- 特定のインデックスを指定して要素を得ることができる。
- インデックスが増加する順でリストの中身をなめることができる。
- 特定のインデックスにある要素の値を、他の要素に影響することなく、変更することができる。
- 特定のインデックスに要素を追加することができる。後ろの要素のインデックスは1ずつ増える。
- 特定のインデックスの要素を取り除くことができる。後ろの要素のインデックスは1ずつ減る。
リストはソートされていることもいないこともある。ソートによって要素の探索や追加を高速化できる（二分探索など）。
[編集] 実装
リストの実装方法には主に2つある。連結リスト（片方向または双方向）と動的配列である。詳細はそれぞれの項目を参照されたい。
Lispにおいてリストはその基盤を成すデータ型であり、プログラムとデータの両方を表現する。最初の3つの素数のリストは多くの方言で(list 2 3 5)と書ける。いくつかの、Schemeを含む、方言ではリストは値とポインタのペアの集まりであり、ポインタは次のペア（またはnull)を指している。
値とポインタのペアの集まりとしてリストを実装する標準的な方法であり、リストがネストしていれば木構造に、していなければ連結リストになる。しかし、Lisp処理系によっては（Symbolics 3600のLispなど）配列を"compressed list"と呼んで使うものもあった。
言語によってはリストデータ構造が用意されていないものもある。しかしそのような言語では連想配列やなんらかのテーブルでリストを実現する手段が提供されている。例えば、Luaはテーブルを提供している。Luaでは数値のインデックスを持つリストを内部的に配列として格納しているのだが、インタフェースはテーブルのままである。
リストは反復や再帰呼び出しを使って処理することもできる。前者は末尾最適化のない言語やリストに対する再帰処理が何らかの理由で一般的でない言語で好まれる。後者は一般的に関数型言語で好まれる。なぜなら、反復は配列との組み合わせで使われることが多く、また命令型とみなされることが多いからである。
コンピュータ上では、リストは集合よりも実現が簡単なため、数学における有限集合は制限を加えたリストで実現することができる。制限とは、重複した要素を許さない、順序の意味をなくすことなどである。リストがソート済みならばオブジェクトが集合の要素かどうかの判定が高速になるが、ソート状態を維持するためにリストに要素を追加する処理の時間が増えてしまう。このため、効率的な実装では集合はリストではなく平衡2分探索木やハッシュテーブルを使って実装される。
