リスト (抽象データ型)

From Wikipedia, the free encyclopedia

リストの例 - 3つの整数値からなる線形リスト

抽象データ型としてのリスト (英: list) は、順序つきのデータコンテナとして定義される。

リストはたいてい配列や連結リストを使って実装される。これは配列や連結リストと似た特性を持っているからである。また連結リストのことを単にリストと呼ぶこともある。順序を持つ点を強調してシーケンス (列; 英: sequence) と呼び、連結リストと区別することもある。

型のないミュータブルなリストはコンストラクタと4つの操作によって特徴付けられる:

  • 空のリストを作るコンストラクタ
  • リストが空かどうかを確かめる操作
  • リストの先頭に要素を追加する操作（Lispのcons）
  • リストの先頭要素 ("head") を求める操作（Lispのcar）
  • リストの先頭を除く部分リスト ("tail") を求める操作（Lispのcdr）

特性

リストは以下のプロパティを持つ。

  • リストのサイズ - リスト内にいくつの要素があるかを示す。
  • リストの等価性
    • 数学的には、リストの等価性は単純にオブジェクトの同一性として定義されることがある。つまり、2つのリストが等しいとは、2つが同じオブジェクトであるということでありかつその場合に限る。
    • 現代のプログラミング言語では、リストの等価性は通常、要素同士の構造の等価性として定義される。リストが型付けされているのなら、その型も影響するかもしれない。
  • リストの型付け - リストの要素はリストの型と互換の型を持たなければならない。リストが配列を用いて実装されているときは型付けされているのが普通である。
  • リスト中のすべての要素はインデックスを持つ。最初の要素はインデックス0（または他の定義された整数値）を持つ。続く要素は前の要素より1大きいインデックスを持つ。最後の要素は (頭のインデックス) + (リストのサイズ) - 1 というインデックスを持つ。
    • 特定のインデックスを指定して要素を得ることができる。
    • インデックスが増加する順でリストの中身をなめることができる。
    • 特定のインデックスにある要素の値を、他の要素に影響することなく、変更することができる。
    • 特定のインデックスに要素を追加することができる。後ろの要素のインデックスは1ずつ増える。
    • 特定のインデックスの要素を取り除くことができる。後ろの要素のインデックスは1ずつ減る。

リストはソートされていることもいないこともある。ソートによって要素の探索や追加を高速化できる（二分探索など）。

実装

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

関連項目

Related Articles

Wikiwand AI