プログラムの処理効率アップに意外と重要！データ構造の初歩

効率的なプログラムを作るには、アルゴリズム（処理手順）と同じくらいデータ構造が重要になります。

この記事では配列をはじめとした、初歩的なデータ構造について詳しく解説します。

ちょっとした違いを知るだけで、プログラミングに差が出てきます。ぜひ最後までご覧ください。

データ構造と配列

データを取り出しやすくするために決まった形で配置する方法を、データ構造と呼びます。

さっそく解説していきますね。

配列は、複数のデータ（変数）を格納するためのデータ構造です。

配列のルールは、格納するデータを同じデータ型（整数型、文字列型など）に統一することです。

配列を利用するときには、あらかじめ格納するデータの数を指定します。配列にデータを格納するには、配列の全体がおさまる連続したメモリー領域の確保が必要なためです。

配列に格納された個々のデータを要素と呼び、先頭から順番に通し番号（添字、英語ではindex）がついています。

たとえば"array"という配列の先頭にあるデータを呼び出したいとき、array[0]と記述します。

この呼び出し方は、どのような言語でもほぼ同じです。添字の番号は0からはじまることを覚えておいてください。

配列は一番シンプルなデータ構造です。どのようなデータ構造がよいか迷ったとき、まず配列を使って実装できないか検討しましょう。

同じデータ型で、あらかじめ数が決まっているデータ（例：一週間あたりの日数）なら、配列で実装できます。

添字をテキストに置き換えた、連想配列という配列もあります。通常の配列と違い、連想配列では添字に任意の文字列を指定可能です。

連想配列の添字はキーとも呼ばれます。

連想配列はキーが文字列型になっているため、対応するデータをプログラム内から直接指定して呼び出しやすいデータ構造です。そのため連想配列は、キーワードで検索したいデータを格納するのに向いています。

キューとスタックは、一時的に複数のデータを格納するためのデータ構造です。このような記憶領域をバッファと呼びます。

プログラミングでバッファを実装するとき、基本的には配列を使います。

キューとスタックの違いは、配列にデータを格納する順番と、配列からデータを取り出す順番です。

キューは、データを順番に処理するためのデータ構造です。

データを格納する処理の順番は先入れ先出し（First In First Out：FIFO形式）で、日本語に訳すと"待ち行列"という意味になります。

その名のとおり、キャンセル待ちの座席などを処理するのに向いています。

プログラミングで実装するときは、配列の末尾にデータを追加し、配列の先頭からデータを取り出すイメージです。

スタックは、逆から順番にデータを取り出したいときに使うデータ構造です。

最後に入れたデータを先に取り出すため、LIFO形式（Last In First Out）とも呼ばれます。

アプリケーションの"元に戻す"（Undo）や、Webブラウザの履歴など、直近のデータにさかのぼる処理に適しています。

スタックを実装するときは、配列の末尾からデータを追加・取り出しをおこなうイメージです。

これまで解説したもの以外にも、さまざまなデータ構造があります。

データ構造は基本的に、配列とポインタを使って実装が可能です。

ポインタは次のデータがどこにあるかを示す特殊なデータで、配列の要素データなど変数と組み合わせて使います。

[主なデータ構造の概要]

データ構造	概要
リスト	配列の要素どうしを、ポインタで数珠つなぎに接続したデータ構造。配列と似ているが、格納したいデータの個数をあらかじめ決められないときに使う。
ハッシュテーブル	連想配列の添字（テキスト）を数値（ハッシュ値）に変換し、さらに格納方法を工夫してより速く検索できるよう改良したデータ構造。
ヒープ	1つのデータ要素＋2つのポインタでつながるツリー状の階層を持つ（木構造、二分木）。データを格納する過程で、大きさを比べ順序をつけたい（ソートしたい）場合に使うデータ構造。
二分探索木	ヒープと同様ツリー状の階層を持つ構造で、あるデータをもとに次のデータを探索し、少ない手順でより速く取り出したいときに使うデータ構造。