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