|
|
| 1行目: |
1行目: |
| − | [[File:Singly-linked-list.svg|thumb|right|リストの例 - 3つの整数値からなる線形リスト]]
| + | {{テンプレート:20180815sk}} |
| − | [[抽象データ型]]としての'''リスト'''({{lang|en|list}})は、順序つきの[[コンテナ (データ型)|データコンテナ]]として定義される。
| |
| − | | |
| − | リストはたいてい[[配列]]や[[連結リスト]]を使って実装される。これは配列や連結リストと似た特性を持っているからである。また連結リストのことを単にリストと呼ぶこともある。順序を持つ点を強調して'''シーケンス'''([[列 (数学)|列]]; {{lang|en|sequence}})と呼び、連結リストと区別することもある。
| |
| − | | |
| − | == 操作 ==
| |
| − | 型のない[[ミュータブル]]なリストは[[コンストラクタ]]と4つの操作によって特徴付けられる:
| |
| − | * 空のリストを作るコンストラクタ
| |
| − | * リストが空かどうかを確かめる操作
| |
| − | * リストの先頭に要素を追加する操作（[[LISP|Lisp]]の<code>cons</code>）
| |
| − | * リストの先頭要素("{{Lang|en|head}}")を求める操作（Lispの<code>car</code>）
| |
| − | * リストの先頭を除く部分リスト("{{Lang|en|tail}}")を求める操作（Lispの<code>cdr</code>）
| |
| − | | |
| − | == 特性 ==
| |
| − | リストは以下のプロパティを持つ。
| |
| − | * リストの'''サイズ''' - リスト内にいくつの要素があるかを示す。
| |
| − | * リストの'''等価性'''
| |
| − | ** 数学的には、リストの[[等式|等価性]]は単純に[[オブジェクト (プログラミング)|オブジェクト]]の[[同一性]]として定義されることがある。つまり、2つのリストが等しいとは、2つが同じオブジェクトであるということでありかつその場合に限る。
| |
| − | ** 現代の[[プログラミング言語]]では、リストの等価性は通常、要素同士の[[構造の等価性]]として定義される。リストが型付けされているのなら、その型も影響するかもしれない。
| |
| − | * リストの'''型付け''' - リストの要素はリストの型と互換の[[データ型|型]]を持たなければならない。リストが配列を用いて実装されているときは型付けされているのが普通である。
| |
| − | * リスト中のすべての要素は'''インデックス'''を持つ。最初の要素はインデックス0（または他の定義された整数値）を持つ。続く要素は前の要素より1大きいインデックスを持つ。最後の要素は <code>(頭のインデックス) + (リストのサイズ) - 1</code> というインデックスを持つ。
| |
| − | ** 特定のインデックスを指定して要素を得ることができる。
| |
| − | ** インデックスが増加する順でリストの中身をなめることができる。
| |
| − | ** 特定のインデックスにある要素の値を、他の要素に影響することなく、変更することができる。
| |
| − | ** 特定のインデックスに要素を追加することができる。後ろの要素のインデックスは1ずつ増える。
| |
| − | ** 特定のインデックスの要素を取り除くことができる。後ろの要素のインデックスは1ずつ減る。
| |
| − | | |
| − | リストは[[ソート]]されていることもいないこともある。ソートによって要素の探索や追加を高速化できる（[[二分探索]]など）。
| |
| − | | |
| − | == 実装 ==
| |
| − | リストの実装方法には主に2つある。[[線形リスト|連結リスト]]（片方向または双方向）と[[動的配列]]である。詳細はそれぞれの項目を参照されたい。
| |
| − | | |
| − | Lispにおいてリストはその基盤を成すデータ型であり、プログラムとデータの両方を表現する。最初の3つの素数のリストは多くの[[方言 (プログラミング言語)|方言]]で<code>(list 2 3 5)</code>と書ける。いくつかの、[[Scheme]]を含む、方言ではリストは値と[[ポインタ (プログラミング)|ポインタ]]のペアの集まりであり、ポインタは次のペア（または[[null]])を指している。
| |
| − | | |
| − | 値とポインタのペアの集まりとしてリストを実装する標準的な方法であり、リストがネストしていれば[[木構造 (データ構造)|木構造]]に、していなければ[[線形リスト|連結リスト]]になる。しかし、Lisp処理系によっては（[[シンボリックス|Symbolics]] 3600のLispなど）配列を"{{Lang|en|compressed list}}"と呼んで使うものもあった。
| |
| − | | |
| − | 言語によってはリストデータ構造が用意されていないものもある。しかしそのような言語では[[連想配列]]やなんらかの[[テーブル (情報)|テーブル]]でリストを実現する手段が提供されている。例えば、[[Lua]]はテーブルを提供している。Luaでは数値のインデックスを持つリストを内部的に配列として格納しているのだが、インタフェースはテーブルのままである。
| |
| − | | |
| − | リストは[[ループ (プログラミング)|反復]]や[[再帰呼び出し]]を使って処理することもできる。前者は[[末尾再帰|末尾最適化]]のない言語やリストに対する再帰処理が何らかの理由で一般的でない言語で好まれる。後者は一般的に[[関数型言語]]で好まれる。なぜなら、反復は配列との組み合わせで使われることが多く、また[[命令型プログラミング|命令型]]とみなされることが多いからである。
| |
| − | | |
| − | [[コンピュータ]]上では、リストは[[集合 (プログラミング)|集合]]よりも実現が簡単なため、数学における有限[[集合]]は制限を加えたリストで実現することができる。制限とは、重複した要素を許さない、順序の意味をなくすことなどである。リストがソート済みならばオブジェクトが集合の要素かどうかの判定が高速になるが、ソート状態を維持するためにリストに要素を追加する処理の時間が増えてしまう。このため、効率的な実装では集合はリストではなく[[平衡2分探索木]]や[[ハッシュテーブル]]を使って実装される。
| |
| − | | |
| − | == 各プログラミング言語のリスト ==
| |
| − | * [[Java]] - [[インタフェース (情報技術)|インタフェース]]{{Javadoc:SE|java/util|List}}, [[クラス (コンピュータ)|クラス]]{{Javadoc:SE|java/util|ArrayList}}, {{Javadoc:SE|java/util|LinkedList}}
| |
| − | * [[C Sharp|C#]] - <code>System.Collections.Generic</code>名前空間の<code>List<T></code>クラス,<code>LinkedList<T></code>クラス
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * [[配列]]
| |
| − | * [[線形リスト]]
| |
| − | * [[タプル]]
| |
| − | * [[列 (数学)]]
| |
| − | * [[集合 (プログラミング)]]
| |
| − | * [[データ構造]]
| |
| − | | |
| − | {{データ構造}}
| |
| − | {{データ型}}
| |
| − | {{DEFAULTSORT:りすと}}
| |
| − | [[Category:抽象データ型]]
| |
| − | | |
| − | [[de:Liste]]
| |
| − | [[fr:Liste]]
| |
| − | [[nl:Lijst]]
| |
| − | [[pl:Lista]]
| |
| − | [[sl:seznam]]
| |