データ構造

コンピュータサイエンスにおいて、データ構造とは、通常、効率的なデータアクセスを目的として選択される、データを整理して格納する方法です。^{[ 1 ] [ 2 ] [ 3 ]}より正確には、データ構造とは、データの編成と格納形式の仕様、およびこのデータを操作する関数や操作を含む、データ型の物理的な実装です。データ構造は、抽象データ型（ADT）と密接に関連しています。^{[ 4 ]}データ構造は、メモリ内のデータの表現と操作の実行方法を記述しますが、ADTは、データ型の論理形式または代数構造（どのような操作が許可され、どのような結果を生成するか）を記述しますが、それらの操作がどのように実装されるかは記述しません。 ^{[ 4 ]}一部の著者は「抽象データ型」という用語を使用せず、単にデータ構造の論理形式と物理形式に言及します。^{[ 5 ]}

効率的なデータ構造は、大規模なデータセットを管理するために不可欠であり、アルゴリズム設計の基礎となります。リレーショナルデータベースでは、データ検索に一般的にB ツリーインデックスが使用され、 ^{[ 6 ]}コンパイラの実装では通常ハッシュ テーブルを使用して識別子を検索します。^{[ 7 ]}ファイルシステムや検索エンジンでは、特殊なデータ構造が広く使用されています。^{[ 8 ] [ 9 ]} Rob Pike は、アルゴリズムは自明であることが多いため、データ構造の選択はアルゴリズムの選択よりも効率に大きな影響を与えることがほとんどであると述べています。^{[ 10 ]}データ構造は、主記憶装置 ( RAM ) と二次記憶装置 (ディスクなど)の両方でデータを整理するために使用されます。 ^{[ 11 ]}

データ構造を実装するには、その構造のインスタンスを作成および操作するサブルーチン（挿入、削除、走査、検索など）のセットを作成する必要があります。データ構造は、さまざまなプログラミング言語と手法を使用して実装できます。データ構造は、特定の実装とは独立して動作と操作を記述するADTとは対照的に、単一の具体的な実装に直接対応します。同じADTに対して複数の具体的なデータ構造が存在する場合があります。たとえば、リストADTの場合は、リンクリストまたはサイズ変更可能な配列です。^{[ 12 ]}そのため、データ構造の効率は具体的な実装に密接に関連しており、ベンチマークと理論シミュレーションによって評価する必要があります。^{[ 13 ]}

データ構造は一般的に、メモリ アドレス(ポインタ(ビット列)で指定されるか、より抽象的には参照によって指定される)を介してデータを格納およびアクセスするコンピュータの機能に依存しており、そのアドレス自体をメモリに格納してプログラムで操作することができます。たとえば、配列やレコードは要素を連続したメモリ位置に格納するため、厳密なレイアウトが必要ですが、算術演算によってアドレスを計算することで高速なインデックスアクセスが可能になります。対照的に、リンクされたデータ構造(リンク リストやツリーなど) は、関連する要素のアドレスを構造内に格納するため、柔軟なメモリ使用と動的なサイズ変更が可能になります。これらの異なるデータ構造化方法にはそれぞれ異なるトレードオフがあり、異なるタスクに適しています。たとえば、配列における連続したメモリ割り当ては、高速なアクセスと変更操作を容易にし、シーケンシャルなデータ処理シナリオでのパフォーマンスを最適化します。^{[ 14 ]}

データ構造には多くの種類があり、一般的にはより単純な基本データ型に基づいて構築されています。よく知られている例としては、^{[ 15 ]などがあります。}

• 配列とは、特定の順序で並べられた複数の要素の集合であり、通常はすべて同じ型です（言語によっては、個々の要素がすべて同じ型に強制される場合もあれば、ほぼ任意の型にできる場合もあります）。要素へのアクセスは、必要な要素を指定する整数インデックスを使用して行います。一般的な実装では、配列の要素用に連続したメモリ領域を割り当てますが（必ずしもそうである必要はありません）、配列は固定長またはサイズ変更可能です。
• 連結リスト（単にリストとも呼ばれる）は、ノードと呼ばれる任意の型のデータ要素の線形集合であり、各ノードは値を持ち、連結リスト内の次のノードを指し示します。配列に対する連結リストの主な利点は、リストの残りの部分を再配置することなく、常に効率的に値を挿入および削除できることです。ただし、特定の要素へのランダムアクセスなど、その他の操作は、配列よりもリストの方が遅くなります。
• レコード（タプルまたは構造体とも呼ばれる）は集約データ構造です。レコードは、通常は固定数と固定順序で、名前でインデックス付けされた他の値を含む値です。レコードの要素は通常、フィールドまたはメンバーと呼ばれます。オブジェクト指向プログラミングのコンテキストでは、レコードはオブジェクトと区別するために、プレーンな古いデータ構造として知られています。^{[ 16 ]}
• ハッシュテーブル（ハッシュマップとも呼ばれる）は、キーに基づいて値を高速に取得できるデータ構造です。ハッシュ関数を用いてキーを配列内のインデックスにマッピングすることで、平均的なケースでは定数時間でのアクセスが可能になります。ハッシュテーブルは、辞書、キャッシュ、データベースのインデックス作成などで一般的に使用されています。しかし、ハッシュ衝突が発生する可能性があり、パフォーマンスに影響を与えることがあります。衝突に対処するために、チェイニングやオープンアドレッシングといった手法が用いられます。
• グラフは、ノードがエッジで接続された集合であり、エンティティ間の関係を表します。グラフは、ソーシャルネットワーク、コンピュータネットワーク、交通ネットワークなど、さまざまなものをモデル化するために使用できます。グラフは、頂点（ノード）とエッジ（ノード間の接続）で構成されます。グラフは有向グラフまたは無向グラフであり、サイクルを持つ場合と非巡回グラフの場合があります。グラフ探索アルゴリズムには、幅優先探索と深さ優先探索があります。
• スタックとキューは、配列またはリンクリストを使用して実装できる抽象データ型です。スタックには、プッシュ（スタックの最上位に要素を追加する）とポップ（スタックの最上位の要素を削除する）という2つの主要な操作があり、これらは後入れ先出し（LIFO）の原則に従います。キューには、エンキュー（キューの末尾に要素を追加する）とデキュー（キューの先頭から要素を削除する）という2つの主要な操作があり、これらは先入れ先出し（FIFO）の原則に従います。
• ツリーは要素の階層構造を表します。ツリーはエッジで接続されたノードで構成され、1つのノードがルートとなり、他のすべてのノードがサブツリーを形成します。ツリーはさまざまなアルゴリズムやデータストレージのシナリオで広く使用されています。バイナリツリー（特にヒープ）、AVLツリー、Bツリーは、代表的なツリーの種類です。これらは、データの効率的かつ最適な検索、ソート、および階層的表現を可能にします。
• トライ木（接頭辞木）は、文字列を効率的に検索するために使用される特殊な木構造です。トライ木では、各ノードが文字列の文字を表し、ノード間のエッジはそれらを接続する文字を表します。この構造は、オートコンプリート、スペルチェック、辞書作成などのタスクに特に役立ちます。トライ木を使用すると、文字列の接頭辞に基づいて高速な検索や操作を行うことができます。

ほとんどのアセンブリ言語と、 BCPL (Basic Combined Programming Language)などの一部の低レベル言語には、データ構造の組み込みサポートがありません。一方、多くの高レベルプログラミング言語と、 MASMなどの一部の高レベルアセンブリ言語には、レコードや配列などの特定のデータ構造に対する特別な構文やその他の組み込みサポートがあります。たとえば、C (BCPL の直接の子孫) とPascal言語は、ベクトル (1 次元配列) と多次元配列に加えて、それぞれ構造体とレコードをサポートしています。 ^{[ 17 ] [ 18 ]}

ほとんどのプログラミング言語には、データ構造の実装を異なるプログラム間で再利用できるようにするライブラリ機構が備わっています。現代の言語には通常、最も一般的なデータ構造を実装した標準ライブラリが付属しています。例としては、C++標準テンプレートライブラリ、Javaコレクションフレームワーク、Microsoft .NETフレームワークなどがあります。

現代のプログラミング言語は一般的にモジュール型プログラミング、つまりライブラリモジュールのインターフェースとその実装の分離をサポートしています。一部の言語は、クライアントが実装の詳細を隠蔽できる不透明なデータ型を提供しています。C ++、Java、Smalltalkなどのオブジェクト指向プログラミング言語は、通常この目的でクラスを使用します。

多くの既知のデータ構造には、複数の計算スレッドがデータ構造の単一の具体的なインスタンスに同時にアクセスできるようにする並行バージョンがあります。 ^{[ 19 ]}

• ピーター・ブラス著、『高度なデータ構造』、ケンブリッジ大学出版局、2008年、ISBN 978-0521880374
• ドナルド・クヌース著『コンピュータプログラミングの技法』第1巻、アディソン・ウェスリー社、第3版、1997年、ISBN 978-0201896831
• ディネシュ・メータ、サルタジ・サーニ著、『データ構造と応用ハンドブック』、チャップマン・アンド・ホール／CRCプレス、2004年、ISBN 1584884355
• ニクラウス・ヴィルト著、『アルゴリズムとデータ構造』、プレンティス・ホール、1985年、ISBN 978-0130220059

• パット・モリン著『オープンデータ構造』
• GH GonnetおよびR. Baeza-Yates、『Handbook of Algorithms and Data Structures - in Pascal and C』、第 2 版、Addison-Wesley、1991 年、ISBN 0-201-41607-7
• エリス・ホロウィッツ、サルタジ・サーニ著『パスカルにおけるデータ構造の基礎』、コンピュータサイエンスプレス、1984年、ISBN 0-914894-94-3

• アルゴリズムとデータ構造の辞典からの説明
• データ構造コース
• .NETの観点から見たデータ構造の考察
• シャファー、C.データ構造とアルゴリズム解析