コンピュータサイエンスでは、データ構造とは、値や情報を整理・格納し、必要な操作（検索・挿入・削除など）を効率よく実行できるようにした方法や仕組みのことを指します。簡単に言えば、データ構造は「データを効率的に整理する方法」です。抽象データ型（ADT）はデータとその操作を論理的に定義したものであり、データ構造はそのADTを実際のメモリ上でどのように実装するかという具体的な設計・実装です。たとえば、抽象的なリストという概念を実現する方法として配列を使うか、リンクリストを使うかで性能や操作方法が変わります。リンクリストでは各ノードが次や前を指す「ポインタ」や「参照」を持ち、前後の移動やノード追加・削除が効率的に行えます。多くの場合、データ構造は特定の操作に最適化されており、問題に応じて最適なデータ構造を選ぶことがプログラミングの重要な要素です。



データ構造の分類（概要）

  • 線形構造: 配列、リンクリスト、スタック、キューなど。データ要素が順序を持って並ぶ。
  • 非線形構造: ツリー、グラフなど。要素間の関係が階層的または複雑なネットワークを成す。
  • 静的 vs 動的: 配列のようにサイズが固定されるもの（静的）と、リンクリストや動的配列のようにサイズが変化するもの（動的）。
  • 永続性・不変性: 変更が元の構造を破壊しない（関数型プログラミングでの不変データ構造）ものもある。

代表的なデータ構造と基本操作

  • 配列（Array）: インデックスによるランダムアクセスがO(1)。挿入・削除は位置によってO(n)。連続メモリ確保によりキャッシュ効率が良い。
  • リンクリスト（Linked List）: ノードの挿入・削除はポインタ操作でO(1)（位置が分かっている場合）。ランダムアクセスはO(n)。単方向・双方向・循環などの変種がある。
  • スタック（Stack）: LIFO（後入先出）。push/popがO(1)。関数呼び出しの戻り先管理や深さ優先探索に利用。
  • キュー（Queue）: FIFO（先入先出）。enqueue/dequeueがO(1)。幅優先探索やタスクスケジューリングに利用。
  • ハッシュ表（Hash Table / Map）: 平均で検索・挿入・削除がO(1)。衝突処理（チェイニングやオープンアドレス）が鍵。キーから高速に値を取り出す用途に最適。
  • 木（Tree）: 二分探索木（BST）、平衡木（AVL、赤黒木）、ヒープなど。BSTは平均で探索がO(log n)（平衡が保たれれば）。ヒープは優先度付きキューの実装で挿入・取り出しがO(log n)。
  • グラフ（Graph）: ノード（頂点）とエッジ（辺）で表現。表現は隣接リスト（稀なグラフに有利）や隣接行列（密なグラフに有利）。探索アルゴリズムにより幅優先探索（BFS）、深さ優先探索（DFS）、最短経路（Dijkstra、Bellman-Ford）、最小全域木（Kruskal、Prim）などがある。

実装とアルゴリズムの関係

アルゴリズムはデータ構造上で動作する手順です。ある問題を解くために、どのデータ構造を使うかでアルゴリズムの効率が大きく変わります。例：

  • 二分探索は配列（またはランダムアクセス可能でソート済みの構造）でのみO(log n)を達成できる。
  • Dijkstraの最短経路は優先度付きキュー（ヒープ）を使うことで効率化できる。
  • ハッシュ表を使えば集合の包含チェックが高速になる（平均O(1)）。

設計時には時間計算量（時間複雑度）と空間計算量（メモリ使用量）、キャッシュ局所性、並列性や実装の容易さ、最悪ケースの振る舞い（例：ハッシュの衝突、BSTの偏り）を考慮します。

データ構造を選ぶ際の指針

  • 主要な操作（頻繁に行う検索・挿入・削除・順序保持など）を洗い出す。
  • それらの操作の平均・最悪時間を比較する（例：頻繁に先頭挿入するなら配列よりリンクリスト）。
  • メモリ制約やキャッシュ効率を考慮する（配列はメモリ連続で高速）。
  • スレッドセーフや並行処理が必要か、永続性が必要かも判断基準になる。

実践的な応用例

  • データベースのインデックス: B木やB+木を使用してディスクアクセスを最小化。
  • 検索エンジン: インバーテッドインデックス（ハッシュやツリーの変種）で高速検索。
  • ネットワークルーティング: グラフと最短経路アルゴリズムを組み合わせる。
  • リアルタイムシステム: 優先度付きキュー（ヒープ）でタスクスケジューリング。

まとめ

データ構造はプログラムの性能と設計品質を左右する基盤です。抽象データ型としての要件を満たしつつ、実際の利用状況に合わせて配列、リンクリスト、ハッシュ表、木、グラフなど適切な構造を選び、対応するアルゴリズムを組み合わせることが重要です。問題の特性（操作頻度・データ量・メモリ制約・並列性など）を見極めて最適なデータ構造を選んでください。