リスト(抽象データ型)

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ

コンピューター サイエンスではリストまたはシーケンス、同じ値が複数回発生する可能性のある有限数の順序付けられた値を表す抽象的なデータ型です。リストのインスタンスは、タプルまたは有限シーケンスの数学的概念のコンピューター表現です。リストの (潜在的に) 無限の類似物はストリームです。[1] : §3.5 リストはコンテナの基本的な例であり、他の値が含まれています。同じ値が複数回発生する場合、各発生は別個のアイテムと見なされます。

単一リンクのリスト構造で、3 つの整数要素を持つリストを実装します。

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

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

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

運営

リスト データ構造の実装により、次の操作の一部が提供される場合があります。

  • 空のリストを作成するためコンストラクター。
  • リストが空かどうかをテストする操作。
  • エンティティをリストの先頭に追加する操作
  • エンティティをリストに追加する操作
  • リストの最初のコンポーネント (または「ヘッド」) を決定するための操作
  • リストの最初の要素を除くすべての要素からなるリストを参照するための操作 (これをリストの「テール」と呼びます)。
  • 特定のインデックスで要素にアクセスするための操作。

実装

リストは通常​​、リンクされたリスト(1 つまたは 2 つのリンク) または配列(通常は可変長配列または動的配列)として実装されます

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

リストは、インデックスと値のペアを保持する自己均衡バイナリ検索ツリーとして実装でき、任意の要素への等しい時間アクセスを提供します (たとえば、フリンジに存在するすべての要素と、検索をガイドするために使用される最も右の子のインデックスを格納する内部ノード) 、リストのサイズで対数時間をとりますが、それがあまり変わらない限り、ランダムアクセスの錯覚を提供し、対数時間でもスワップ、プレフィックス、および追加操作を有効にします。[3]

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

リストのデータ構造を提供しない言語もありますが、リストをエミュレートするために連想配列またはある種のテーブルを使用できます。たとえば、Luaはテーブルを提供します。Lua は数値インデックスを持つリストを内部的に配列として保存しますが、それでも辞書として表示されます。[4]

Lisp ではリストは基本的なデータ型であり、プログラム コードとデータの両方を表すことができます。ほとんどの方言では、最初の 3 つの素数のリストは次のように記述できます(list 2 3 5)Schemeを含む Lisp のいくつかの方言では、リストは値と次のペア (または null 値) へのポインタで構成されるペアのコレクションであり、単方向リンク リストを作成します。[5]

アプリケーション

名前が示すように、リストは要素のリストを格納するために使用できます。ただし、従来の配列とは異なり、リストは拡張および縮小でき、メモリに動的に格納されます。

コンピューティングでは、リストはセットよりも実装が簡単です。数学的な意味での有限集合は、追加の制限付きのリストとして実現できます。つまり、要素の重複は許可されず、順序は関係ありません。リストを並べ替えると、特定のアイテムが既にセットに含まれているかどうかを判断する速度が上がりますが、順序を確認するには、新しいエントリをリストに追加するためにより多くの時間を必要とします。ただし、効率的な実装では、セットはリストではなく、 自己均衡二分探索木またはハッシュ テーブルを使用して実装されます。

リストは、 queuestack、およびそれらのバリエーション を含む他の抽象データ型の基礎も形成します。

抽象的な定義

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

無: () → L
短所:E × LL
最初:LE
レスト:LL

公理で

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

任意の要素eおよび任意のリストlに対して。暗黙のうちに

cons ( e , l ) ≠ l
cons ( e , l ) ≠ e
cons ( e 1 , l 1 ) = cons ( e 2 , l 2 ) if e 1 = e 2 and l 1 = l 2

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

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

型理論では、上記の定義はより単純に、コンストラクタ ( nilcons ) で定義された帰納型と見なされます。代数的には、これは変換 1 + E × LLとして表すことができますfirstrestは、consコンストラクターでパターン マッチングを行い、 nilケース を個別に処理することによって取得されます。

リストモナド

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

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

別の方法として、モナドは操作returnfmap、およびjoinに関して次のように定義することもできます

fmapjoinappend、およびbindは、再帰呼び出しごとに段階的に深い引数に適用されるため、明確に定義されていること に注意してください。

リスト型は加算モナドであり、nilはモナドのゼロ、appendはモナドの和です。

リストは、追加操作の下でモノイドを形成します。モノイドの恒等要素は空のリストnilです。実際、これは一連のリスト要素 の自由なモノイドです。

も参照

参考文献

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