リスト (抽象データ型)

リストとは

リストは、抽象データ型として、順序付けられたデータの集まりを扱うための構造です。一般的に、配列や連結リストといった具体的なデータ構造を用いて実装されます。特に連結リストは、その構造から「リスト」と呼ばれることもあります。

リストは、要素が順番に並んでいるという特性から、「シーケンス（列）」とも呼ばれます。連結リストと区別するために、この用語が用いられることもあります。

リストの操作

型を持たない可変リストは、主に以下の操作によって特徴付けられます。

コンストラクタ: 空のリストを生成します。
空判定: リストが空かどうかをチェックします。
要素追加: リストの先頭に新しい要素を追加します。（Lispの`cons`に相当）
先頭要素取得: リストの先頭の要素を取得します。（Lispの`car`に相当）
先頭以外取得: リストの先頭要素を除いた残りのリストを取得します。（Lispの`cdr`に相当）

リストの特性

リストは、以下のプロパティを持ちます。

サイズ: リストに含まれる要素の数を表します。
等価性:
オブジェクトの同一性として定義される場合があります。つまり、2つのリストが等しいとは、それらがメモリ上で同じオブジェクトを指している場合に限られます。
要素の構造的な等価性として定義される場合が一般的です。リストが型付けされている場合、要素の型も等価性に影響を与えることがあります。
型付け: リストの要素は、リストの型と互換性のある型を持つ必要があります。配列で実装されるリストは、通常型付けされています。
インデックス: リスト内の各要素は、0から始まる（または他の定義された値から始まる）インデックスを持ちます。
要素へのアクセス: 特定のインデックスを指定して、対応する要素を取得できます。
要素の走査: インデックスを順番に増やすことで、リスト内のすべての要素にアクセスできます。
要素の変更: 特定のインデックスにある要素の値を、他の要素に影響を与えずに変更できます。
要素の追加: 特定のインデックス位置に要素を追加できます。この際、後続の要素のインデックスは1ずつ増加します。
要素の削除: 特定のインデックスにある要素を削除できます。この際、後続の要素のインデックスは1ずつ減少します。
ソート: リストはソートされている場合もあれば、そうでない場合もあります。ソートされていると、要素の検索や追加の効率が向上します。

リストの実装

リストは、主に以下の2つの方法で実装されます。

連結リスト: 要素がポインタで繋がっているデータ構造です。
動的配列: 必要に応じてサイズが変更できる配列です。

Lispにおけるリスト

Lispでは、リストは基本的なデータ型であり、プログラム自体もリストで表現されます。例えば、最初の3つの素数のリストは`(list 2 3 5)`のように記述されます。Lispの方言によっては、リストは値とポインタのペアの集まりとして実装され、ポインタは次のペアを指します。リストがネストしている場合は木構造になりますが、そうでない場合は連結リストになります。

その他の言語におけるリスト

リストデータ構造が標準で提供されていない言語もありますが、連想配列やテーブルなどでリストをエミュレートすることができます。例えば、Luaでは、数値インデックスを持つテーブルが内部的には配列として格納されます。

リストの処理

リストの処理には、反復処理や再帰呼び出しが用いられます。反復処理は、末尾最適化がない言語や、リストに対する再帰処理が一般的ではない言語で好まれます。一方、再帰呼び出しは、関数型言語で好まれます。

数学におけるリストと集合

コンピュータ上では、リストは集合よりも実装が容易です。数学における有限集合は、重複した要素を許さない、順序を意味をなくすなどの制約を加えたリストとして実装することができます。リストがソートされていれば、集合の要素であるかどうかの判定が高速になりますが、ソート状態を維持するためのオーバーヘッドが発生します。そのため、効率的な実装では、集合はリストではなく、平衡2分探索木やハッシュテーブルで実装されることが一般的です。

各プログラミング言語のリスト

C++: `std::vector`, `std::list` (STL)
Java: `java.util.List`インタフェース, `ArrayList`クラス, `LinkedList`クラス
C# (.NET): `System.Collections.Generic.IList`インタフェース, `List`クラス, `LinkedList`クラス
Python: 組み込みのリスト型

関連項目

配列
線形リスト
タプル
列 (数学)
集合 (プログラミング)
* データ構造

もう一度検索