データ構造

基本的なデータ構造

アレイ

最もシンプルなデータ構造は、線形配列です。一次元配列とも呼ばれます。配列は、同じ型（整数、フロート、文字列など）の複数の値を保持します。配列内の要素へのアクセスは非常に高速です。配列のサイズは通常固定です。配列のサイズが最初に定義された後は、より大きな配列を新たに作成し、すべての値を新しい配列にコピーしない限り、配列のサイズを増やすことができない場合があります。コンピュータサイエンスでは、配列データ構造または単に配列は、少なくとも1つの配列インデックスまたはキーによって識別される要素（値または変数）の集まりからなるデータ構造である。配列は、各要素の位置を、そのインデックスタプルから数式で計算できるように格納されている。

例えば、0～9のインデックスを持つ10個の整数変数の配列は、メモリアドレス2000、2004、2008、2036に10個のワードとして格納され、インデックスiの要素は、2000＋4×iのアドレスを持つようになります。

数学の概念である行列は2次元のグリッドとして表現できるため、2次元の配列を行列と呼ぶこともあります。数学的にはベクターではなくタプルが正しいのですが、コンピュータでは配列を指すのに「ベクター」という言葉が使われることがあります。配列はテーブル、特にルックアップテーブルの実装によく使われ、テーブルという言葉は配列の同義語として使われることもあります。

配列は、最も古く、最も重要なデータ構造の一つであり、ほとんどのプログラムで使用されています。また、リストや文字列など、他の多くのデータ構造の実装にも使用されています。配列は、コンピュータのアドレッシング・ロジックを効果的に利用しています。最近のコンピュータや多くの外部記憶装置では、メモリはワードの1次元配列で、そのアドレスがインデックスとなっている。プロセッサ、特にベクトルプロセッサは、しばしば配列操作に最適化されています。

配列が便利なのは、要素のインデックスを実行時に計算できるからです。特に、この機能により、1つの反復文で配列の任意の数の要素を処理することができます。そのため、配列データ構造の要素は同じサイズであることが求められ、同じデータ表現を使用する必要があります。有効なインデックスタプルのセットと要素のアドレス（したがって、要素のアドレス指定式）は、配列が使用されている間は、常にではありませんが、通常は固定されています。

配列とは、多くの高級プログラミング言語で提供されているデータ型の一種で、実行時に計算される1つまたは複数のインデックスによって選択可能な値または変数の集合体からなる。配列型は、多くの場合、配列構造で実装されるが、言語によっては、ハッシュテーブル、リンクリスト、探索木などのデータ構造で実装される場合もある。

リンクリスト

リンクされたデータ構造とは、参照によってリンクされた情報/データのセットのことである。データはしばしばノードと呼ばれます。また、参照はリンクやポインターと呼ばれることが多い。今後、これらの概念には、ノードとポインターという言葉を使用します。

リンクされたデータ構造では、ポインタは参照解除されるか、または同等かどうか比較されるだけです。そのため、リンクされたデータ構造は、ポインタの加算や減算が必要な配列とは異なります。

リンクリスト、サーチツリー、エクスプレッションツリーは、いずれもリンクされたデータ構造です。また、トポロジカルソートやセットユニオンファインドなどのアルゴリズムでも重要な役割を果たします。

スタック

スタックは基本的なデータ構造で、論理的には実際の物理的なスタックやパイルで表現される線形構造と考えることができ、アイテムの挿入や削除はスタックのトップと呼ばれる一方の端で行われる構造です。この基本的な考え方は、データセットをお皿や本の山に見立てて、そこから物を取り除くためには一番上の物を取り除かなければならないと考えることで説明することができます。この構造は、プログラミングのあらゆる場面で使われています。

スタックの基本的な実装は「後入れ先出し」構造とも呼ばれますが、スタックの実装にはさまざまなバリエーションがあります。

スタックで実行できる操作は基本的に3つあります。それらは

• スタックへのアイテムの挿入（"push"）。
• スタックからのアイテムの削除（「ポッピング」）について
• スタックの一番上のアイテムの内容を表示する（"peeking"）。

キュー

待ち行列とは、抽象的なデータ型または線形データ構造であり、一方の端（「テール」）から最初の要素が挿入され、他方の端（「ヘッド」）から既存の要素の削除が行われるものである。待ち行列は、「先入れ先出し」の構造です。「先入れ先出し」とは、最初に列に入れられた要素が最初に出てきて、最後に列に入れられた要素が最後に出てくることを意味します。待ち行列の例としては、待っている人の列があります。最初に並んだ人が最初に、最後に並んだ人が最後になります。

キューに要素を追加することを「エンキュー」といい、キューから要素を削除することを「デキュー」といいます。

グラフ

グラフは、数学のグラフやハイパーグラフの概念を実現するための抽象的なデータ型です。

グラフデータ構造は、ノードまたは頂点と呼ばれる特定のエンティティの、エッジまたはアークと呼ばれる順序付けられたペアの有限の（そしておそらく変更可能な）セットから構成されます。ノードは、グラフ構造の一部である場合もあれば、整数のインデックスや参照で表される外部エンティティである場合もある。また、グラフデータ構造では、各辺に記号的なラベルや数値属性などの辺の値を関連付けることができる。

樹木

ツリーは、最も強力な先進的データ構造の一つです。人工知能（AI）やデザインなど、高度なテーマでよく登場します。意外なことに、ツリーはもっと基本的な用途、つまり効率的なインデックスの作成にも重要な役割を果たします。

ツリーを使用する際には、高い確率でインデックスが使用されます。最も単純なインデックスは、キーフィールドのソートされたリストです。ツリーは通常、定義された構造を持っています。バイナリツリーの場合、バイナリ検索を使用すると、すべての項目を見なくても任意の項目を見つけることができます。

ツリーデータタイプはグラフの一種であり、グラフをトラバースするために作られた多くのアルゴリズムがツリーでも機能しますが、アルゴリズムはよく似ており、専用のスタートノード（他のノードがリンクしていないノード）を持つ必要があります。

単純な順序付きリストの問題点は、新しいアイテムを追加し始めたときに、リストのソートを維持しなければならないことです。これは合理的に効率的に行うことができますが、いくつかの変更が必要です。一方、木の「枝」をロックすると、他の枝は他のユーザが編集できるようになります（影響を受けないからです）。

ハッシュテーブル

ハッシュテーブルとは、各インデックスがハッシュ値に基づいてリンクリストを指し示す配列のことである。ハッシュ値とは、ハッシュ関数によって決定される値のことです。ハッシュ関数は、格納されているデータに基づいて一意の値を決定します。これにより、コンピュータは常にどこを見ればよいかがわかるため、データに一定時間でアクセスすることができる。

各ノードは別のノードを指しています。