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

出典:wikipedia