リスト (抽象データ型)
リストの実装方法には主に2つある。連結リスト(片方向または双方向)と動的配列である。詳細はそれぞれの項目を参照されたい。
Lispにおいてリストはその基盤を成すデータ型であり、プログラムとデータの両方を表現する。最初の3つの素数のリストは多くの方言で(list 2 3 5)と書ける。いくつかの、Schemeを含む、方言ではリストは値とポインタのペアの集まりであり、ポインタは次のペア(またはnull)を指している。
値とポインタのペアの集まりとしてリストを実装する標準的な方法であり、リストがネストしていれば木構造に、していなければ連結リストになる。しかし、Lisp処理系によっては(Symbolics 3600のLispなど)配列を"compressed list"と呼んで使うものもあった。
言語によってはリストデータ構造が用意されていないものもある。しかしそのような言語では連想配列やなんらかのテーブルでリストを実現する手段が提供されている。