データ構造とは何か

データ構造入門

データ構造とは

データ構造とは、「コンピューターがデータを効率的に扱うための方法や構造のこと」です。これには様々な種類があり、それぞれに特徴があります。

アルゴリズムの話をする際に必ずと言っても良いほど出てくるのがデータ構造です。この2つは切っても切れない関係にあります。

アルゴリズムを定めるときに、データをどのような状態で保持しておくかを定めて置く必要があるのですが、その際にデータ構造が使われます。また、コンピュータ内部での実際のデータの保管方法もデータ構造によって決められています。

また、どのようなデータ構造を使うかによって、アルゴリズムの効率が変化するので、プログラムを書く際は気をつける必要があります。

基本的なデータ構造

配列(Array)

メモリの連続する領域にデータを格納します。データにアクセスする際は、先頭から位置を表すインデックス(index)を用いてアクセスします。

詳細: 配列(Array)

連結リスト(Linked List)

連結リストはリンクリスト・リンクトリストとも呼ばれることがあります。ノードと呼ばれる要素が複数つながってできており、配列とは違ってメモリの連続しない領域にデータを格納することができます。

1つのノードには、1つのデータと次のノードへのアドレスが格納されています。このノードを先頭から一つ一つたどって行くことで、データにアクセスすることができます。

詳細: 連結リスト(Linked List)

スタック(Stack)

スタックにはデータを1つ格納する操作(push)と1つ取り出す操作(pop)があります。

最後に格納したデータが最初に出てくるようなデータ構造をしていて、このような順序をLIFO(Last In First Out) もしくは FILO(First In Last Out)と言います。

詳細: スタック(Stack)

キュー(Queue)

キューは待ち行列とも呼ばれ、これもデータを1つ格納する操作(enqueue)と1つ取り出す操作(dequeue)があります。

最初に格納したデータが最初に出てくるようなデータ構造をしていて、このような順序をFirst In First Out (FIFO)と言います。

詳細: キュー(Queue)

セット(Set)

setは、数学でいうところの「集合」を表すデータ構造です。複数の要素を保持するデータ構造ですが、要素が重複することを許しません。

詳細:セット(Set)

グラフ(Graph)

グラフは、頂点と頂点同士を結ぶ辺によって構成されるデータ構造です。様々なところで使用されるデータ構造ですが、主に有限で離散的なものを考察する際に使用されます。

詳細:グラフ(Graph)

辞書(Dictionary)

辞書は、連想配列(associative array)・ハッシュ(hash)・マップ(map)とも呼ばれます。配列はインデックスを用いて要素にアクセスしましたが、辞書は鍵(key)を用いて要素にアクセスすることができます。

プログラミング言語にも依りますが、keyには数値や文字列などを使用することができます。

詳細: 辞書(Dictionary)

データ構造入門

Posted by cs-learner