データ構造【data structure】

概要

データ構造（data structure）とは、データの集まりをコンピュータプログラムで扱いやすいように、一定の形式で格納したもの。特定の問題を解く手順(アルゴリズム)には、それぞれに適したデータ構造がある。

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

データ構造の種類

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

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

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