データ構造【data structure】

概要

複数のデータの配置や関係性、データの参照や出し入れなどの操作のルールを定義したもので、様々な種類がある。それぞれに特徴や適した処理があるため、同じ処理の記述でも、目的に対して適切なデータ構造を選択できるかどうかでプログラムの複雑さや処理性能に大きな差がつくことがある。

データ構造の種類

最も基本的なデータ構造には、要素を一列に並べた「配列」（array）、要素を格納した順に取り出すことができる「キュー」（queue）、格納したのとは逆順に取り出すことができる「スタック」（stack）などがある。

格納された要素への参照データを含むデータ構造もあり、任意の標識と要素を一対一に関連付けて格納する「連想配列」（辞書、ハッシュ、マップとも呼ばれる）、要素が前後の要素への参照を持つ「連結リスト」（linked list）、要素が任意個の他の要素への参照を持つ「グラフ」（graph）、一つの頂点から樹状に枝分かれしたグラフである「木構造」（ツリー構造）などがある。

これらには細部の仕様が異なるバリエーションがある。例えば、連結リストには前の要素が後の要素への参照を持つだけの「片方向リスト」（単方向リスト）、これに加えて後の要素が前の要素への参照も持つ「双方向リスト」、要素が環状に連なっている「循環リスト」などいくつかの種類がある。

言語上の扱い

プログラミング言語では、基本的なデータ構造のいくつかが言語仕様や標準ライブラリなどにあらかじめ組み込まれて提供されていることが多い。用意されていない場合でも、既存のデータ構造や複合データ型、クラスなどの仕様を利用して開発者がデータ構造の定義や挙動の実装を行うことがある。

実際のプログラム上では基本的なデータ構造を単体で用いることも多いが、あるデータ構造の要素として別のデータ構造を格納するなど、アルゴリズムに合わせて組み合わせて用いる場合もある。