データ構造
データ構造
データ構造（data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。
多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。
この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。
データ構造の3つの概念
データ構造は、プログラムの中でデータの集合を系統立てて管理するための形式で、一般的に単にデータの集合を表すだけでなく、以下の3つの概念から成り立つ。
データの集合
対象となるデータの本体で、例えば、配列や構造体などの基本データ構造でデータの集合を保持する。
規則
データの集合を一定のルールに従って正しく操作・管理・保持するための決まり事である。どういった順番でデータを取り出すかなどの取り決めである。
配列
配列とは
配列とは、複数の要素（値）の集合を格納・管理するのに用いられるデータ構造が配列である。数学のベクトルおよび行列に近い概念であり、実際にベクトルおよび行列をプログラム上で表現する場合に配列が使われることが多い。同様に複数要素の集合を管理するデータ構造（コレクションあるいはコンテナ）には連結リストやハッシュテーブルなどがあるが、通常はメモリアドレス上での連続性の違いなどから配列とは区別される。1次元の配列は特に線形配列 (linear array) とも呼ばれる。
配列の長所は、簡単に使用できる、メモリ使用量に無駄がなく、空間的な効率が良い、添字（インデックス）による直接アクセスが可能という点で、短所は、要素の追加や削除が非効率、探索の効率が高くない(ただしソート済みであることが保証できるのなら、二分探索法を使う等して効率を高められる。)という点である。
実用的には、配列の要素数が宣言時（あるいはコンパイル時）に静的に決まってしまうよりも、実行時に要素数を動的に指定して配列を確保できたほうが便利なことがある。例えば、縦横任意サイズの画像ファイルから全画素情報を読み出す場合や、コンピュータで利用可能な空きメモリ量に合わせて扱うデータ個数上限を変化させたい場合などである。
配列の動的確保
多くのプログラミング言語では、配列のサイズをプログラム実行時に指定して配列を生成する（動的に確保する）手段が用意されている。例えばC言語ではmalloc関数やcalloc関数を利用する。確保に成功するとメモリブロック（配列先頭要素）へのポインタが返却され、このポインタ経由で配列を操作する。
計算オーダー
「配列」という語は、抽象データ型というよりも、添え字をオフセットとしてメモリのアドレスにマップすることで、Ο(1) でアクセスできる具象あるいは実装を特に指す場合がある（その意味では、次節の連想配列などは「配列」ではない、ということになる）。
要素に「隙間」が無いようにするには、線形リストと異なり、挿入・削除にO(n)時間かかる。探索は一般的には線型探索になるためΟ(n)だが、データがソート済みであれば二分探索を使うことでΟ(log n)に軽減することもできる（抽象データ型としては、sorted array などの名前で別のデータ構造と考える場合もある。
様々な配列
連想配列
添え字は一般に通例0か1始まりの (非負) 整数である。一方、文字列など他のデータ型を添え字のように使用できる配列を連想配列という。一般に動的配列のように、任意に拡大されるものが多いが、固定サイズのものもありえなくはない。また、完全ハッシュ（ハッシュ関数#完全ハッシュ関数）の利用も考えられる。
動的配列
要素数によって自動的にサイズが拡張する配列を、動的配列 (dynamic array) あるいは可変長配列 (variable-length array) と呼ぶ。メモリが許す限り、要素の末尾追加や途中挿入がいくらでもできる。ライブラリで提供されるものと、言語に組み込まれているもの（PerlやDなど）がある。またPerlなど、言語によっては、最初に配列を生成する際に指定されたサイズからはみ出してアクセス（範囲外アクセス）しても、自動的に拡大されるような配列を持っているものもある。逆に決まった要素数しか格納できない配列を、静的配列 (static array) あるいは固定長配列 (fixed length array) と呼ぶ。
動的配列の拡大などの場合には、最悪の場合、メモリ上の別の場所が確保されて、そこに全体をコピーする、というような時間のかかる操作が起きる可能性があるものもある（そのシステムの設計次第で、配列の内部にあるものが他からポインタで指されていて、それを更新できないなど、そういうことができない場合もある）。最悪ではなく償却計算量でNにならなければ良い、という考え方もある。
時間計算量
時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。ランダウの記号を使ってO(n2)やO(nlogn)という形で表記することが多い。償却計算量とは、同じ処理をN回行った時に、1回あたりどれくらいの計算量になるかというものである。
多次元配列
1次元だけではなく2次元・3次元などの多次元配列 (multidimensional array) を備える言語もある。 マトリックスやグリッドのような矩形構造を持ったデータ構造であることから、矩形配列 (rectangular array) と呼ばれることもある。
スタックとキュー
スタックとは
スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出しの構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。
抽象データ型
抽象データ型（ちゅうしょうデータがた、英: abstract data type、ADT）とは、データ構造とそれを直接操作する手続きをまとめてデータ型の定義とすることでデータ抽象を実現する手法またはそのひとまとまりとして定義されたデータ型を言う。通常のデータ型であれば変数宣言で変数に束縛されるものは値であるが、抽象データ型の世界において値に相当するものはデータ構造とその操作のまとまりである。
抽象データ型を用いない場合、データ構造またはデータの操作手続きのアルゴリズムの変更を行うとソースコード中にその変更部分が散在してしまい規模によっては修正困難となるが、データとその操作がひとまとめに記載されることになる抽象データ型においては、型の定義における実装部分を変更するだけで修正が完了する。
抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ(push)とポップ(pop)を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。
