改訂新版 世界大百科事典 「データ構造」の意味・わかりやすい解説
データ構造 (データこうぞう)
data structure
コンピューターを用いて問題を解決するためには，問題をモデル化し，そのモデルを操作することによって解を導くという手順が必要である。現在のコンピューターではこれをデータ構造とその操作手続きの組として現している。データ内に存在する構造関係を理解することと，その構造をコンピューター内に表現し処理するための技術について理解することは，情報処理の基本的な課題である。
上記過程においてデータ構造は，上流においてはモデル化という意味的な面にかかわるとともに，下流においてはこれをコンピューターという一定の機構のもとで物理的に実現するための技法を含む幅広い概念である。またこれがデータ構造の正しい理解を困難にしている。
上記のように問題解決のプロセスにおいて現れる情報の表現形式は，図1-aに示した順序で具体化されていく。これに対応してデータ構造の議論にも意味的な面と形式的な面がある。意味的な面は問題のモデルから論理構造にかかる部分の議論であり，モデルをデータ間の規格化された関係の表現形式によっていかに表すかを問題とする。形式面はデータ間の論理関係から物理的な構造表現にかかる部分の議論である。このうち，形式面での議論は枠組みが定まっているため技術的にほぼ固まっているが，意味的な面はソフトウェア技術の進歩とともにコンピューターでの情報の取扱いが変化しているため流動的な状況にある。これまでのソフトウェア技術のもとでは，人が問題をモデル化し，意味を解釈した結果をコンピューター言語によって手続き化するという手順をとっていた。図1の表現でいえば第2段階からがコンピューター化される部分であったため，モデル化を含めた意味部分が表面に現れることが少なかった。このため，従来のデータ構造の議論は主として形式面に偏っていた。以下ではデータ構造に関し，この両方の面を考察する。
データ構造の形式面
データ構造の形式面を次のように定義する。〈データ構造はコンピューターのメモリー内で相互に関係づけられたデータの集合である〉。ここで〈関係〉の内容は意味に関するので形式面の範囲外の問題であり，どのような方法でこの関係が表現されるかが形式的な議論の対象とされる。この表現形態によってデータ構造を分類することができる。また表現形態によってその機械的な処理すなわち構造の創成，変更，アクセス，消去などやメモリー管理の方法や難易，効率等が異なる。
論理的データ構造
メモリー内での関係の物理的な表現とは，あるデータから他のデータへ，あるいはデータ集合の中で指定したデータにアクセスするためのアドレス情報を得ることである。その方式として（1）メモリー・アドレスの線形性を用いるもの，（2）ポインターを用いるもの，（3）やや特殊であるがハッシングによるもの，がある（図2）。（1）はデータの論理構造自身が線形的な構造を持つ場合に限られる。順序情報の関数としてアドレスが求められるのでアクセスははやいが，挿入や削除は多くのデータの移動を伴うので効率が悪い。（2）のポインター形式は，データ間の関係はアドレスの順序と切り離されているので挿入・削除の影響は局所的であり，多重関係も表現できる。一般にポインターを用いる場合，自由記憶領域の管理（動的記憶割当てを含む）や使用済み領域の管理（カーベジ・コレクション）が必要となる場合が多い。（3）のハッシングは，ハッシュ関数と呼ばれる特定の関数をデータ内容（の一部）に適用して得られる関数値をこのデータのアドレスとするもので，アクセスははやいが，一般に連鎖的な構造化の手段にはなっていない。現実のデータ構造の表現にはこれらが組み合わされて用いられる。図3に例を二つ示す。
物理的データ構造
論理的なデータ構造は物理的実現よりもデータ間の関係自体に重点を置いた表現である。これには配列，リスト構造，木構造，グラフなどがある。配列は一次元もしくは多次元のデータの順序化された並びであり，インデックス集合からの変換機構をもつ構造である。リストも所与の型（要素型）の0個以上のデータ（リスト要素）の列である（図2-b）。n＞0のとき，リストはa1，a2，……，anである。a1を第1要素，anは最終要素と呼ぶ。リストは各要素がリスト内の位置に応じた順序を持つ。線形配列はリストで順序とアドレスが結合したものといえる。リストは成長も縮小も可能だし，要素の挿入・削除の容易な柔軟性に富んだ構造であり，多様な目的に使われる。ポインター形式で実現されたリストを連結リストと呼び，多重のリストの構造の多重連結リスト（図4），順逆両方向を有する双方向連結リストなど多様な構造が可能である。
木構造は図5のようなノード（節）と呼ばれる要素の集まりである。そのうちの最上位のノードをルートと呼ぶ。これは再帰的に定義される。（1）〈単一ノードは木構造である。このノードはルートでもある〉。（2）〈nがノードで，T1，T2，……，Tkがn1，n2，……，nkをルートとする木構造のとき，nをn1，……，nkの親として新しい木構造を定義することができる。nはルート，T1，……，Tnを部分木と呼ぶ。n1，……，nkはnの子ノードである〉。木構造ですべてのノードの子ノードの数が2であるものを2進木という。
グラフはノードとアーク（ノード間の結合路）からなる図6の構造であり，広範な応用に用いられる。
データ構造の意味的面
データ構造の意味的な面は，モデル化と，その論理的データ構造による表現の議論である。問題のモデルは静的なデータ構造とその操作の組で表される。このモデルの段階から論理的なデータ構造のレベルまでの道が遠いことがソフトウェア開発を困難にしていることから，近年，データ構造とその操作を組にした抽象データ型の概念が生まれ，この間に置かれるようになった（図1-b）。一方，このようなプログラム言語分野でのアプローチとは別に，データベースの分野では限られた範囲で表現形式と操作手順を固定し，それでモデルを表現する。これをさらに普遍的なものにするものが人工知能分野の知識表現の考え方である。このようにデータ構造の上流部分はソフトウェアの中枢にかかわる概念として発展している。
執筆者：大須賀 節雄
出典 株式会社平凡社「改訂新版 世界大百科事典」改訂新版 世界大百科事典について 情報