データ構造

コンピュータサイエンスにおいて、データ構造とは、データへの効率的なアクセスのために通常選択されるデータの編成および保存形式である。 ^{[1] [2] [3]}より正確には、データ構造とは、データ値、それらの関係、およびデータに適用できる関数または操作の集合であり、 ^{[4]つまり、}データに関する代数構造である。

データ構造は抽象データ型（ADT）の基礎として機能します。ADTはデータ型の論理形式を定義します。データ構造はデータ型の物理形式を実装します。^[5]

さまざまな種類のデータ構造はさまざまなアプリケーションに適しており、特定のタスクに高度に特化しているものもあります。たとえば、リレーショナルデータベースでは、データの取得にBツリーインデックスがよく使用されますが、^[6]コンパイラ 実装では通常、識別子の検索にハッシュテーブルが使用されます。^[7]

データ構造は、大規模データベースやインターネットインデックスサービスなどの用途で大量のデータを効率的に管理する手段を提供します。通常、効率的なデータ構造は効率的なアルゴリズムを設計するための鍵となります。一部の正式な設計方法とプログラミング言語では、ソフトウェア設計における主要な構成要素として、アルゴリズムではなくデータ構造を重視しています。データ構造は、メインメモリとセカンダリメモリの両方に格納された情報の格納と検索を整理するために使用できます。^[8]

データ構造は、さまざまなプログラミング言語やテクニックを使用して実装できますが、それらはすべて、データを効率的に整理して保存するという共通の目標を共有しています。^[9]データ構造は一般に、ポインターによって指定されたメモリ内の任意の場所からデータを取得して保存するコンピューターの機能に基づいています。ポインターとは、メモリアドレスを表すビット文字 列で、それ自体をメモリに格納してプログラムで操作することができます。したがって、配列とレコードのデータ構造は、算術演算を使用してデータ項目のアドレスを計算することに基づいていますが、リンクされたデータ構造は、構造自体にデータ項目のアドレスを格納することに基づいています。このデータ構造化のアプローチは、アルゴリズムの効率とスケーラビリティに大きな影響を与えます。たとえば、配列内の連続したメモリ割り当てにより、迅速なアクセスと変更操作が容易になり、順次データ処理シナリオでのパフォーマンスが最適化されます。^[10]

データ構造の実装には通常、その構造のインスタンスを作成し、操作する一連の手順を記述する必要があります。データ構造の効率は、これらの操作とは切り離して分析することはできません。この観察から、抽象データ型という理論的概念が生まれました。抽象データ型とは、そのデータ構造に対して実行される操作と、それらの操作の数学的特性（空間コストと時間コストを含む）によって間接的に定義されるデータ構造です。^[11]

データ構造にはさまざまな種類があり、一般的にはより単純なプリミティブデータ型に基づいて構築されます。よく知られている例としては、次のものがあります。^[12]

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

トライ(接頭辞ツリー)は、文字列を効率的に取得するために使用される特殊なタイプのツリーです。トライでは、各ノードは文字列の文字を表し、ノード間のエッジはノードを接続する文字を表します。この構造は、オートコンプリート、スペルチェック、辞書の作成などのタスクに特に役立ちます。トライを使用すると、文字列の接頭辞に基づいて、迅速な検索と操作を行うことができます。

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

ほとんどのプログラミング言語には、データ構造の実装をさまざまなプログラムで再利用できるようにする何らかのライブラリメカニズムが備わっています。最近の言語には通常、最も一般的なデータ構造を実装する標準ライブラリが付属しています。例としては、 C++ 標準テンプレート ライブラリ、Java Collections Framework、Microsoft .NET Frameworkなどがあります。

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

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

• ピーター・ブラス著『Advanced Data Structures』、ケンブリッジ大学出版局、2008年、ISBN 978-0521880374 
• ドナルド・クヌース『コンピュータプログラミングの芸術』第 1 巻。Addison -Wesley、第 3 版、1997 年、ISBN 978-0201896831 
• Dinesh Mehta およびSartaj Sahni著、『データ構造とアプリケーションハンドブック』、Chapman and Hall / CRC Press、2004 年、ISBN 1584884355 
• ニクラウス・ヴィルト著『アルゴリズムとデータ構造』、プレンティス・ホール、1985年、ISBN 978-0130220059 

• アルフレッド・エイホ、ジョン・ホップクロフト、ジェフリー・ウルマン、『データ構造とアルゴリズム』、アディソン・ウェズレー、1983年、ISBN 0-201-00023-7 
• GH GonnetおよびR. Baeza-Yates、アルゴリズムとデータ構造ハンドブック - Pascal および C、第 2 版、Addison-Wesley、1991 年、ISBN 0-201-41607-7 
• エリス・ホロウィッツとサルタジ・サーニ著『Pascal におけるデータ構造の基礎』Computer Science Press、1984 年、ISBN 0-914894-94-3 

• アルゴリズムとデータ構造の辞書からの説明
• データ構造コース
• .NET の観点から見たデータ構造の検討
• シャッファー、C. データ構造とアルゴリズム分析