データ構造 — 配列・連結リスト・木・グラフ

データ構造とは、検索、挿入、削除、走査のようなよくある操作をしやすくするための、データの整理方法です。配列、連結リスト、木、グラフを理解したいなら、最も手早い方法は2つの問いを立てることです。データはどんな形をしているのか、そしてどの操作を軽くしたいのか、です。

データが列なら、出発点は配列であることが多いです。各要素が主に次の要素を指すなら、連結リストが合うかもしれません。データに階層があるなら、木を使います。要素どうしがさまざまな方向につながるなら、グラフを使います。

最短で役立つルールは次のとおりです。

• 配列: 添字付きの順序に最適。
• 連結リスト: 鎖状の局所的なつながりに最適。
• 木: 階層に最適。
• グラフ: ネットワークに最適。

配列・連結リスト・木・グラフは実際に何をするのか

配列は、要素を固定された順序で格納し、「$7$番目の要素」のように位置を直接指定できます。通常の連続領域による実装では、この直接アクセスは $O(1)$ です。

連結リストは、各ノードが別のノードを指す形で要素を格納します。ノードからノードへたどることはできますが、$n$ 番目の要素に到達するには通常それ以前のノードを順にたどる必要があるため、位置によるアクセスは一般に $O(n)$ です。

木は、データを階層的な段に分けて格納します。各ノードは子を持てるので、フォルダの中にフォルダがあるような入れ子構造を自然に表せます。探索や更新のコストは、木の種類や平衡が保たれているかどうかに依存します。

グラフは、ノードと辺を格納します。木と違って、1つのノードは任意の形で多くの他ノードとつながれ、閉路も許されます。そのため、グラフは道路網、SNS、依存関係マップを表す自然なモデルになります。

すばやい比較: それぞれのデータ構造が向く場面

Structure	Best mental model	Usually good at	Common limitation
Array	番号付きの要素の列	添字による直接アクセス	途中への挿入や削除では要素の移動が必要になりがち
Linked list	ノードの鎖	既知のノード付近での挿入や削除	ランダムアクセスが遅い
Tree	分岐する階層	段階構造や親子関係の表現	挙動が木の種類に大きく左右される
Graph	接続のネットワーク	到達可能性、経路、関係性	アルゴリズムが複雑になりやすい

具体例: 1つのキャンパスアプリで構造を選ぶ

時間割画面、講義カタログ、徒歩ルート地図を持つキャンパスアプリを作るとします。データ構造を選ぶ最も簡単な方法は、各機能をそのデータの形に対応させることです。

時間割画面の平日タブは、自然に配列になります。

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

重要なのは、位置による直接アクセスです。「$3$番目のタブを表示して」は自然な要求であり、順序にも意味があります。

講義カタログは、自然に木になります。

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

各段階が次の段階を含んでいます。これは階層なので、木が最もすっきりしたモデルです。

建物どうしを結ぶ通路は、自然にグラフになります。1つの建物は複数の建物とつながれ、経路はループすることもあります。図書館から実験室までの最短ルートを求めたいなら、それは木の問題ではなくグラフの問題です。

連結リストが合うのは、同じアプリの中でももっと限定的な部分です。たとえば、主な操作が1歩ずつ前後に移動することであるなら、最近訪れた画面の列です。この場合、各画面に必要なのは $20$ 番目の画面への高速アクセスではなく、近くの画面へのリンクです。

ここでの教訓は、「最適」は仕事次第だということです。1つの製品の中で複数のデータ構造が使われるのは、データの各部分で関係の形が異なるからです。

すばやく見分ける方法

多くの学生は、まずこれらを用語として覚えます。すると抽象的に感じられますが、実際の問いはもっと単純です。

考えるべきは、「どの操作を軽くしたいか」です。

「位置 $i$ に飛ぶ」を軽くしたいなら、配列が強いです。「次のつながりをたどる」を軽くしたいなら、連結構造が役立ちます。「階層を下にたどる」をしたいなら、木が合います。「2つのものがつながっているかを調べる」をしたいなら、グラフが合います。

データ構造を学ぶときのよくある間違い

1つの構造が常に最速だと思い込む

万能の勝者はありません。「速い」かどうかは、何を最も頻繁に行うかと、実装に依存します。

木は自動的に効率がよいと考える

非常に効率よく探索できる木もありますが、それは木の種類や平衡のような構造条件に依存します。形の悪い木は、平衡木よりずっと性能が悪くなることがあります。

挿入が安そうだからという理由だけで連結リストを選ぶ

挿入は、正しいノードがすでに分かっていれば安くできます。しかし、そのノードを見つけるのには時間がかかることがあります。

本当はグラフなのに木を使う

ある要素が複数の親を持てたり、横断リンクや閉路があったりするなら、無理に木に押し込むと本来の構造が見えにくくなり、後の操作が扱いにくくなります。

抽象的な構造とプログラミング言語の機能を混同する

プログラミング言語にある「array」「list」「map」「tree」には、メモリ使用量や速度に影響する実装上の選択が含まれていることがあります。抽象的な考え方と具体的なコンテナは関係していますが、同じものではありません。

配列・連結リスト・木・グラフはいつ使われるか

配列は、順序付きコレクション、表、バッファ、その他位置が重要な場面で使われます。

連結リストは、ランダムアクセスよりも局所的なポインタ更新が重要な特殊な実装で現れます。

木は、ファイルシステム、文書構造、式木、多くの検索インデックスのような階層データに使われます。

グラフは、経路、依存関係解析、ネットワークモデリング、推薦リンク、そして一般的な接続問題に使われます。

正しいデータ構造の選び方

まず、次の2つを自分に問いかけてください。

1. データはどんな関係を持っているか。列か、階層か、それともネットワークか。
2. 最も重要な操作は何か。添字アクセスか、局所更新か、階層走査か、それとも経路探索か。

この2つの答えがあれば、たいてい候補はすぐに絞れます。

それでも迷うなら、紙の上に小さな例を書いてみてください。コードを書く前に、図のほうが構造をはっきり示してくれることがよくあります。

自分でも試してみよう

プレイリスト、フォルダ構成、路線図のような身近な例を3つ選んでみましょう。それぞれが主に列なのか、階層なのか、ネットワークなのかを見極め、主要な操作を楽にする構造を選びます。別の例でも練習したいなら、GPAI Solver で似た分類問題を生成できます。