リスト (抽象データ型)
C++ - STLのstd::vector, std::list
Java - java.utilパッケージのListインタフェース, ArrayListクラス, LinkedListクラス
C# (.NET) - System.Collections.Generic名前空間のIList<T>インタフェース, List<T>クラス, LinkedList<T>クラスなど
Pythonなど、組み込みのデータ型のひとつとしてリストを提供する言語もある。
リストは以下のプロパティを持つ。
リストのサイズ - リスト内にいくつの要素があるかを示す。
リストの等価性 数学的には、リストの等価性は単純にオブジェクトの同一性として定義されることがある。つまり、2つのリストが等しいとは、2つが同じオブジェクトであるということでありかつその場合に限る。 現代のプログラミング言語では、リストの等価性は通常、要素同士の構造の等価性として定義される。リストが型付けされているのなら、その型も影響するかもしれない。
リストの型付け - リストの要素はリストの型と互換の型を持たなければならない。リストが配列を用いて実装されているときは型付けされているのが普通である。
リスト中のすべての要素はインデックスを持つ。最初の要素はインデックス0(または他の定義された整数値)を持つ。続く要素は前の要素より1大きいインデックスを持つ。最後の要素は (頭のインデックス) + (リストのサイズ) - 1 というインデックスを持つ。 特定のインデックスを指定して要素を得ることができる。 インデックスが増加する順でリストの中身をなめることができる。 特定のインデックスにある要素の値を、他の要素に影響することなく、変更することができる。 特定のインデックスに要素を追加することができる。後ろの要素のインデックスは1ずつ増える。 特定のインデックスの要素を取り除くことができる。後ろの要素のインデックスは1ずつ減る。
リストはソートされていることもいないこともある。ソートによって要素の探索や追加を高速化できる(二分探索など)。