データ構造
データこうぞう
データの並べ方・つなぎ方の型。操作の速さを決める、アルゴリズムと対をなす基礎概念。
概要
データ構造とは、プログラムの中でデータをどう並べ、どうつなぐかの「型」のことです。本棚にたとえるなら、同じ蔵書でも「著者名順にぎっしり並べる」「ジャンルごとの棚に分ける」「よく読む本だけ手元に積む」で、探しやすさも追加のしやすさも変わります。データ構造は、まさにこの「しまい方」を選ぶ概念です。
なぜしまい方が重要かというと、どのデータ構造を選ぶかによって、それぞれの操作 — 探す・先頭に足す・途中に挟む・順に眺める — の速さが劇的に変わるからです。万能のしまい方は存在せず、どの構造もある操作が速い代わりに別の操作が遅いというトレードオフを抱えています。だからこそ、「このプログラムはどの操作を一番よくやるのか」を見極めて構造を選ぶことが設計の第一歩になります。アルゴリズムがデータを処理する「手順」だとすれば、データ構造はその手順が働きかける「舞台」であり、両者は常に対で考えるべきものです。
なぜ生まれたか
コンピュータのメモリは、本来ただの「番地の付いた一列のマス目」でしかありません。黎明期のプログラマは、この平坦なメモリの上にデータをどう配置するかをすべて手作業で決めていました。しかし扱う問題が複雑になると、「一覧」「対応表」「階層」といった論理的なまとまりを、毎回むき出しの番地計算で表現するのは限界を迎えます。同じ工夫が何度も再発明され、しかも配置の選び方ひとつで性能が桁違いに変わることが経験的に知られていきました。
そこで、繰り返し現れる配置のパターンに名前を付け、それぞれの性質 — どの操作が速く、どの操作が遅いか — を体系的に整理したものがデータ構造という分野です。配列、連結リスト、スタック、キュー、木、ハッシュテーブル。1970年代には Wirth が「アルゴリズム + データ構造 = プログラム」という書名でこの対の関係を言い当て、以来この語彙はプログラミング教育の背骨になっています。
詳細
代表4種を「得意な操作」で比べる
無数にあるデータ構造も、まず4つを押さえれば見通しが立ちます。それぞれの形と得意技を図で比べてみます。
配列は、データをメモリ上に隙間なく一列に並べる構造です。「3番目の要素」への到達は番地の足し算1回で済むため一瞬ですが、途中に1件挟むには後ろの要素をすべてずらす必要があります。連結リストは逆に、各要素が「次の要素の場所」を指すことで鎖のようにつながる構造です。途中への挿入・削除はつなぎ替えるだけで済みますが、「3番目」に行くには先頭から鎖をたどるしかありません。同じ「一覧」でも、読み取り中心なら配列、並びの編集中心ならリストと、得意分野が正反対なのが分かります。
ハッシュテーブルは、キーをハッシュ化して格納場所を直接計算する構造で、「名前から電話番号を引く」ような対応表の検索が件数によらずほぼ一定時間で済みます。多くの言語の辞書・マップ・オブジェクトの正体はこれです。代償として、要素は計算された場所に散らばるため、五十音順に取り出すような「順序」の操作は苦手です。木は要素が親子関係で枝分かれする構造で、階層をそのまま表せるうえ、「並び順を保ったまま速く探す」ことができます。二分探索木では左に小さい値・右に大きい値を置くことで、アルゴリズムの二分探索と同じ「半分ずつ捨てる」探し方が挿入や削除と両立します。
同じ操作を3つの構造に同時にさせてみると、この得意・不得意の差が「手数」としてそのまま目に見えます。
配列
手数: —
連結リスト
手数: —
ハッシュテーブル
手数: —
操作を選ぶと、3つの構造が同じ仕事をどうこなすかを1手ずつ見られます。手数の差に注目してください。
構造を決めれば手順は決まる
Linux を作った Linus Torvalds は「悪いプログラマはコードを心配し、良いプログラマはデータ構造を心配する」と語っています。これは経験則ではなく構造的な話で、データ構造を決めた瞬間に、そこで速く実行できる操作の集合 — つまり採れるアルゴリズム — がほぼ決まってしまうからです。「後から挿入した順に取り出したい」ならキュー、「直近のものから戻りたい」ならスタック、と要件を操作の言葉に翻訳できれば、構造の選択は自然に定まり、コードはその構造に沿って素直に書けます。逆に構造の選択を誤ると、どれだけ手順を工夫しても遅さは覆せません。それぞれの操作コストを定量的に比べる物差しが計算量とO記法です。
実務のいたるところにある
データ構造は教科書の中の話ではなく、普段使う道具の中身そのものです。JSON はオブジェクトと配列が入れ子になった木構造であり、HTML を解析した結果の DOM も要素が親子関係を持つ木です。データベースのインデックスの実体は B-tree という「1ノードに多数の子を持たせてディスク読み取り回数を減らした木」で、貼るだけで検索が桁違いに速くなるのは木構造の性質そのものです。Git のコミット履歴は有向グラフ、メッセージキューはその名の通りキュー、関数呼び出しの管理はスタックとヒープのスタックが担っています。
実務での落とし穴は、言語が用意する便利な構造を「なんとなく」使うことです。配列に対して「含まれているか」を大量に問い合わせてループが遅くなる、順序が必要なのにハッシュテーブルを選んで後から並べ替え続ける、といった性能問題の多くは、操作と構造のミスマッチが原因です。コードを書き始める前に「このデータに一番よくする操作は何か」を一度問う習慣が、この語彙のいちばん実践的な使い方です。