概要

情報技術の基礎として理解しておきたいデータ構造のうち、配列、スタック、キュー、リスト、ハッシュ、木構造、ヒープを整理する。

データ構造は、データをどのように持つか、どのように探すか、どのように追加・削除するかを決める考え方となる。
同じデータでも、構造の選び方によって処理のしやすさや計算量が変わる。

この記事の構成

• 配列
  配列：複数の類似データを連続的に集約したデータ型の総称。
• スタック/キュー
  スタック：後入れ先出し（LIFO：Last In First Out）のデータ構造のこと。
• 線形リスト
  線形リストの意味と要点を具体例から整理。
• ハッシュ
  ハッシュ関数：キーを一定の計算ルールでハッシュ値に変換する関数のこと。
• 木構造の分類
  木構造の分類と各項目の特徴を整理。
• ヒープ
  ヒープの意味と要点を具体例から整理。

配列

• 配列
  複数の類似データを連続的に集約したデータ型の総称。

• 静的配列
  作成時に要素数を決め、後から長さを変更しない配列。

• 動的配列
  要素の追加や削除に応じて、長さを変更できる配列。
  異なるデータ型を格納できるかどうかは、使用するプログラム言語の型システムによる。

スタック/キュー

• スタック
  後入れ先出し（LIFO：Last In First Out）のデータ構造のこと。
  スタックにデータを入れることをpush、データを出すことをpopという。

• キュー
  先入れ先出し（FIFO：First In First Out）のデータ構造のこと。
  キューにデータを入れることをenqueue、データを出すことをdequeueという。

線形リスト

※ 線形リストは、単にリストとも呼ばれる。

• 線形リスト
  順序付けされた関連データを集約したデータ構造のこと。

  各ノードは、データ値を保持するデータ部と、次または前のノードを参照するポインタ部で構成される。リスト全体を管理する構造が、先頭ノードや末尾ノードへの参照を別に保持する場合もある。

• 単方向リスト
  ポインタ部に次データへのポインタのみ保持するリスト。

• 双方向リスト
  ポインタ部に次データと前データへのポインタを保持するリスト。

• 環状リスト
  末尾ノードの次データへのポインタが、先頭ノードを指すリスト。

ハッシュ

• ハッシュ関数
  キーを一定の計算ルールでハッシュ値に変換する関数のこと。
  ハッシュテーブルでは、ハッシュ値を格納位置を決めるために使う。

  例えば、\(h(x) = x \bmod n\) では、複数の \(x\) が同じハッシュ値になる。このように異なるキーが同じハッシュ値になることを衝突という。
  暗号学的ハッシュ関数に求められる一方向性は、ハッシュテーブルの定義そのものではない。

• ハッシュテーブル（ハッシュ表）
  キー（key）と値（value）を対応付けて格納するデータ構造。
  キーのハッシュ値から格納位置を求め、その位置でキーを照合して値を探索する。

  • 例 : ハッシュ関数を \(h(x) = x \bmod n\) とし、異なるキー \(a\)、\(b\) のハッシュ値が一致する条件を考える。

    → 「ハッシュ値が一致する」ことより、次のように置ける。
    \(a = a^{\prime} \times n + m\)
    \(b = b^{\prime} \times n + m\)
    （\(a^{\prime}, b^{\prime}\) は整数、\(m\) は共通するハッシュ値）

    よって
    \(a - b = n (a^{\prime} - b^{\prime})\)

    また、\(a^{\prime}\ -\ b^{\prime}\) は、整数である。

    よって
    \(a - b\) が \(n\) の倍数であることが条件となる。

木構造の分類

• 木構造
  木構造は、グラフとして見ると連結で閉路を持たない構造となる。
  根付き木は、ルート（根）、ノード（節）、ノード間をつなぐエッジ（枝）、リーフ（葉）から構成される。

  ※ 上記は、応用数学の「5. グラフ理論」で触れた記載と同じ。
  → 応用情報技術 - 応用数学 > グラフ理論

• \(2\) 分木
  子ノードの数が \(2\) つ以下である木構造。
  実用例として、データの大小関係を木構造でたどる \(2\) 分探索木や構文・文法を表現する構文木などがある。

• 多分木
  各ノードが、任意の数の子ノードを持てる木構造。

• 完全 \(2\) 分木
  最下層以外のノードがすべて埋まり、最下層のノードが左から順に詰められた \(2\) 分木。
  実用例として、バイナリヒープがある。

• AVL木
  各ノードの左右の部分木の高さの差を \(1\) 以下に保つ、高さ平衡 \(2\) 分探索木。
  完全 \(2\) 分木とは別の概念となる。

• B木
  一つのノードに複数のキーと子を持てる、平衡した多分探索木。
  木の高さを抑えられるため、データベースやファイルシステムの索引などで使われる。

ヒープ

• ヒープ
  親子間で一定の大小関係を保つ木構造で、バイナリヒープは完全 \(2\) 分木として構成される。最小ヒープでは各親が子以下、最大ヒープでは各親が子以上となるため、根が全体の最小値または最大値となる。

  全要素から最大値または最小値を取り出す場合に適したデータ構造。

  最小値を求める場合、子要素は親要素以上となるように構成する。
  最大値を求める場合、子要素は親要素以下となるように構成する。

まとめ

• スタックは最後に入れたデータを先に取り出すLIFO、キューは先に入れたデータを先に取り出すFIFO。
• 配列は添字によるアクセスに向き、リストは挿入や削除を伴う構造変更に向く。
• ハッシュ表ではキーをハッシュ関数へ渡してハッシュ値を求め、高速な探索に利用。
• 木は閉路を持たない階層的なグラフとして、階層データの表現に使われる。
• ヒープは親子間の大小関係を保つ木構造で、優先度付きキューなどに利用される。
• データ構造のヒープとメモリ領域のヒープは、同じ名称でも意味が異なる。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス
• Python公式チュートリアル - データ構造（日本語・リスト、スタック、キュー、集合の公式解説）
• NIST Dictionary of Algorithms and Data Structures - Array（英語・配列の公的用語定義）
• NIST Dictionary of Algorithms and Data Structures - Hash table（英語・ハッシュ表の公的用語定義）
• NIST Dictionary of Algorithms and Data Structures - Tree（英語・木構造の公的用語定義）