リスト（抽象データ型）

コンピュータサイエンスにおいて、リストまたはシーケンスとは、有限個の項目が特定の順序で集まったものです。リストのインスタンスとは、タプルまたは有限シーケンスという数学的概念をコンピュータで表現したものです。

リストには同じ値が複数回含まれる場合があり、各出現は個別の項目とみなされます。

リストという用語は、抽象的なリストを実装するために使用できるいくつかの具体的なデータ構造、特に連結リストや配列を指す場合にも使用されます。Lispプログラミングなどの文脈では、リストという用語は配列ではなく連結リストを指すこともあります。クラスベースプログラミングでは、リストは通常、汎用的な「リスト」クラスのサブクラスのインスタンスとして提供され、個別のイテレータを介して走査されます。

多くのプログラミング言語はリストデータ型をサポートしており、リストとリスト演算のための特別な構文とセマンティクスを備えています。リストは、多くの場合、括弧（「()」）、角括弧（「[]」）、中括弧（「{ } 」）、山括弧（「<>」）などの区切り文字で囲み、カンマ、セミコロン、またはスペースで区切られた項目を順番に記述することで作成できます。一部の言語では、リスト型を配列型のようにインデックス付けしたりスライスしたりできる場合があり、その場合のデータ型はより正確には配列として記述されます。

型理論と関数型プログラミングでは、抽象リストは通常、空のリストを生成するnilと、リストの先頭に項目を追加するconsという2つの操作によって帰納的に定義されます。 ^[1]

ストリームは潜在的に無限のリストのアナログである。^[2]^{: §3.5}

オペレーション

リストデータ構造の実装では、次の操作のいくつかが提供される場合があります。

作成する
空かどうかのテスト
先頭または末尾に項目を追加する
最初または最後の項目にアクセスする
インデックスでアイテムにアクセスする

実装

リストは通常、リンクリスト(単一または二重リンク) または配列(通常は可変長配列または動的配列) として実装されます。

リストを実装する標準的な方法は、プログラミング言語Lispに由来し、リストの各要素にその値と、リスト内の次の要素の位置を示すポインタの両方を持たせるというものです。この方法は、リストにネストされたサブリストがあるかどうかによって、連結リストまたはツリー構造になります。古い Lisp 実装の中には ( Symbolics 3600の Lisp 実装など)、特別な内部表現 (ユーザーには見えない) を持つ「圧縮リスト」( CDR コーディングを使用) もサポートしているものがありました。リストは反復処理または再帰処理を使って操作できます。前者は命令型プログラミング言語でよく使用され、後者は関数型言語で一般的に使用されています。

リストは、インデックスと値のペアを保持する自己バランス型二分探索木として実装することができ、任意の要素（例えば、すべてが周辺に存在し、内部ノードは検索をガイドするために使用される右端の子のインデックスを格納する）への均等な時間アクセスを提供し、リストのサイズの対数時間がかかりますが、あまり変化しない限り、ランダムアクセスの錯覚を提供し、対数時間でスワップ、プレフィックス、追加の操作を可能にします。^[3]

プログラミング言語のサポート

一部の言語ではリストデータ構造は提供されていませんが、連想配列や何らかのテーブルを用いてリストをエミュレートしています。例えば、 Luaはテーブルを提供しています。Luaは数値インデックスを持つリストを内部的には配列として保存しますが、辞書として表示されます。^[4]

Lispでは、リストは基本的なデータ型であり、プログラムコードとデータの両方を表すことができます。ほとんどの方言では、最初の3つの素数のリストはと記述できます(list 2 3 5)。Scheme を含むいくつかの Lisp 方言では、リストは値と次のペア（またはヌル値）へのポインタからなるペアの集合であり、単方向リンクリストを形成します。^[5]

アプリケーション

配列とは異なり、リストは拡張および縮小が可能です。

コンピューティングにおいては、リストの方が集合よりも実装が容易です。数学的な意味での有限集合は、追加の制約（つまり、重複要素は許可されず、順序は無関係）を伴うリストとして実現できます。リストをソートすると、特定の項目が集合内に既に存在するかどうかの判断は高速化されますが、順序を保証するためには、リストに新しい項目を追加するのに時間がかかります。しかし、効率的な実装では、集合はリストではなく、自己平衡二分探索木またはハッシュテーブルを用いて実装されます。

リストは、キュー、スタック、およびそれらのバリエーションを含む他の抽象データ型の基礎にもなります。

抽象的な定義

何らかの型E (単相リスト) の要素を持つ抽象リスト型L は、次の関数によって定義されます。

ゼロ: () → L

短所: E × L → L

最初：L → E

休憩：L → L

公理を用いて

まず (cons ( e , l )) = e

残り (cons ( e , l )) = l

任意の要素eと任意のリストlに対して、

定数 ( e , l ) ≠ l

cons ( e , l ) ≠ e

e ₁ = e ₂かつl 1 _{= l}₂の場合、cons ( e ₁ , l 1 ) = cons ( e ₂ , l ₂₎

first (nil()) と rest (nil()) は定義されていないことに注意してください。

これらの公理は、抽象スタックデータ型の公理と同等です。

型理論では、上記の定義は、より単純に、コンストラクタ nil と cons を用いて定義される帰納的型とみなされます。代数的に表現すると、これは 1 + E × L → Lという変換で表すことができます。first とrest は、 consコンストラクタのパターンマッチングとnilの場合の個別処理によって得られます。

リストモナド

リスト型は、次の関数を持つモナドを形成します (型Eの要素を持つ単相リストを表すために、LではなくE ^*を使用します)。

{\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}

{\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}

ここで、append は次のように定義されます。

{\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}

あるいは、モナドはreturn、fmap、joinという操作を使って次のように定義することもできます。

{\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}

{\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}

fmap、join、append、bind は、各再帰呼び出しで徐々に深い引数に適用されるため、明確に定義されていることに注意してください。

リスト型は加法モナドであり、nilがモナドのゼロ、appendがモナドの合計です。

リストは追加演算に関してモノイドを形成します。このモノイドの単位元は空リストnilです。実際、これはリスト要素の集合上の自由モノイドです。

参照

無料辞書のウィクショナリーでリストを調べてください。

配列データ型 – 要素（値または変数）の順序付けられたコレクションを表すデータ型
キュー – 抽象データ型
セット – 一意の値を格納するための抽象データ型
スタック – 抽象データ型
ストリーム – 時間の経過とともに利用可能なデータ項目のシーケンス

参考文献

^ ラインゴールド, エドワード; ニーバーゲルト, ユルグ; ナーシン, デオ (1977). 『組み合わせアルゴリズム：理論と実践』エングルウッド・クリフス, ニュージャージー: プレンティス・ホール. pp. 38– 41. ISBN 0-13-152447-X。
^ アベルソン、ハロルド、サスマン、ジェラルド・ジェイ (1996). 『コンピュータプログラムの構造と解釈』 MITプレス.
^ Barnett, Granville; Del tonga, Luca (2008). 「データ構造とアルゴリズム」(PDF) . mta.ca. 2014年11月12日閲覧。
^ レルサリムシ、ロベルト (2003 年 12 月)。 Lua でのプログラミング (初版) (初版)。 Lua.org。ISBN 8590379817. 2014年11月12日閲覧。
^ Steele, Guy (1990). Common Lisp (第2版). Digital Press. pp. 29– 31. ISBN 1-55558-041-6。