データ構造の選び方 - アーキ教室

ベテランのSI屋さんが考えたことを書き残した雑記です。
SI屋さんにしか通じない単語を説明なしに使うので素人は要注意です。
いろいろな意見を欲しているので、つっこみは大歓迎です。
他の記事はSI屋さんの雑記からどうぞ。

概要

プログラミングにおけるデータ構造の選び方は、性能や保守性に大きな影響を与えるにもかかわらず、なんとなく選んでいる初学者が多いように思います。
本記事は代表的なデータ構造の特徴を説明し、適切な選択を行うための指針を提供することを目的としています。

一般的なデータ構造の特徴と選び方

一般的なデータ構造の特徴や選択基準を一覧で整理します。
これらの特徴は、言語やライブラリによって異なる場合がありますので、一般的なケースとして捉えてください。

特徴一覧

名称	要素数の変更	要素の重複	順序	性能
配列	不可（固定長）	可能	あり	高速
リスト	可能（可変長）	可能	あり	アクセスは低速 挿入や削除は高速
スタック	実装に依存	可能	あり	LIFOは高速
キュー	実装に依存	可能	あり	FIFOは高速
セット	可能	不可（一意）	なし	高速
マップ（Key/Value）	可能	キーは不可（一意） 値は可能	なし	高速
木（階層構造）	一般的に可能	一般的に可能	階層的	中速

選び方一覧

一般的なデータ構造の選び方は以下の通りです。

名称	選択基準
配列	要素数が固定、高速な読み取りが必要
リスト	要素数が可変、要素の追加／削除が多い
スタック	後入れ先出し (LIFO:Last In First Oout) に適したデータを扱う
キュー	先入れ先出し (FIFO:First In First Out) に適したデータを扱う
セット	一意な要素の集合を扱う、高速な検索が必要な場合
マップ（Key/Value）	一意なキーと紐づく値のペアを扱う、高速な検索が必要な場合
木（階層構造）	階層的なデータを扱う

実現したいことに対して一般的なデータ構造が存在しない場合もあります。たとえば、一意性と順序の両方を保証したい場合などです。このような場合は、使用している言語やライブラリで専用のデータ構造が提供されていないか調べたり、複数のデータ構造を組み合わせて使うことで実現したりします。具体的には、リストとセットを併用したり、JavaであればLinkedHashSetを、Pythonであればcollections.OrderedDictを使用したりします。

データ構造の詳細説明

以下では、一般的なデータ構造の詳細な説明を行います。
それぞれのデータ構造の特徴や使用例を深く理解することで、より適切な選択ができるようになるでしょう。

配列

配列の主な特徴は、要素を連続したメモリ領域に格納することです。
現代的な言語では配列という呼び名でリストを指すことも多いのですが、ここでは伝統的な配列の特徴を説明します。

• 使い方
  • インデックスを指定して要素にアクセスする
  • 要素の総数の変更はできず作り直しとなる
• 要素
  • 順序を持っている
  • 重複する値を持つことができる
• 性能
  • ランダムアクセスはO(1)で非常に高速
  • 要素の位置変更は低速
  • 省メモリ
• 使用が適さないケース
  • 要素の追加や削除を頻繁に行う
• 一般的な技術仕様
  • 連続したメモリ領域に格納される

リスト

リストの主な特徴は、順序性を持った要素を制限なく追加／削除できることです。

• 使い方
  • 要素の順序が保証され決まった順番でアクセスできる
• 要素
  • 順序を持っている
  • 重複する値を持つことができる
• 性能
  • ランダムアクセスはO(n)で低速
  • 要素の追加や削除はO(1)で高速
• ユースケース
  • ToDoリスト
  • 音楽のプレイリスト
  • 履歴
• 使用が適さないケース
  • 要素の中から特定の要素を検索する
• 一般的な技術仕様
  • 各要素は次の要素への参照（ポインタ）を持つことで論理的な順序を保つ

スタック

スタックは、要素の順序を保持しながら、LIFO（Last In, First Out）方式でデータを管理するデータ構造です。

• 使い方
  • 積み重ねのイメージで要素の追加や取り出しを行う
• 要素
  • 順序を持っている
  • 重複する値を持つことができる
• 性能
  • 要素を追加するプッシュ操作はO(1)で高速
  • 要素を取り出すポップ操作はO(1)で高速
• ユースケース
  • 関数の呼び出し履歴
  • アンドゥ機能
• 使用が適さないケース
  • LIFO操作以外
• 一般的な技術仕様
  • 配列やリストを拡張して実装されることが多い

キュー

キューは、要素の順序を保持しながら、FIFO（First In, First Out）方式でデータを管理するデータ構造です。

• 使い方
  • 一方通行のイメージで要素の追加や取り出しを行う
• 要素
  • 順序を持っている
  • 重複する値を持つことができる
• 性能
  • 要素を追加するエンキュー操作はO(1)で高速
  • 要素を取り出すデキュー操作はO(1)で高速
• ユースケース
  • 注文
• 使用が適さないケース
  • FIFO操作以外
• 一般的な技術仕様
  • 配列やリストを拡張して実装されることが多い

セット

セットは、一意な要素の集合を管理するデータ構造です。

• 使い方
  • 重複しない要素を追加する
• 要素
  • 順序を持たない
  • 重複する値を持たない
• 性能
  • 要素の追加／変更／削除は平均してO(1)と高速
• ユースケース
  • 一意なIDの管理
  • 重複を許さないコレクション
• 使用が適さないケース
  • 順序が必要な場合
  • 重複を許容する場合
• 一般的な技術仕様
  • ハッシュテーブルを用いて実装されることが多い

マップ

マップは、キーと値のペアを管理するデータ構造です。

• 使い方
  • 重複しないキーに対してキーと値のペアを追加する
  • キーを指定してペアを取り出す
• 要素
  • 順序を持たない
  • キーは重複してはならない
  • 値は重複しても良い
• 性能
  • キーと値のペアの追加／変更／削除は平均してO(1)と高速
• ユースケース
  • 電話帳など一意のキーに紐づく値を管理する場合（電話番号と名前）
  • 設定情報の管理
• 使用が適さないケース
  • 順序が必要な場合
  • キーの重複を許容する場合
• 一般的な技術仕様
  • ハッシュテーブルを用いて実装されることが多い
• マップは別名が多く以下のようなデータ構造で呼ばれることもあります
  • ハッシュ
  • ハッシュテーブル
  • 辞書（Dictionary）
  • 連想配列（Associative Array）

グラフ理論の観点による整理

ここから先は私の自己満足のための内容なので、データ構造理解の参考にはなりません。
が、本当に書きたかったのは、この部分だったりします。現時点では粗削りなので、少しずつ改善していこうと思います。

グラフ特性による整理

今まで紹介したデータ構造は、グラフ理論の観点から見ると、すべて「制約のついたグラフ」として表現できます。
グラフとは、ノード（要素）とエッジ（関係）で構成されるデータ構造です。

パターン	関係性	順序	一意性	閉路	層の有無
集合	なし	-	なし	-	不問
セット	なし	-	あり	-	不問
線形	1対1	あり	不問	なし	不問
木構造	1対多	あり：階層	不問	なし	なし
森構造	1対多	あり：階層	不問	なし	あり
無層ネットワーク	多対多	不問	不問	不問	なし
多層ネットワーク	多対多	不問	不問	不問	あり

各パターンに対応するデータ構造

パターン	該当するデータ構造
集合	マルチセット、バッグ
セット	セット
線形	配列、リスト、スタック、キュー
木構造	ツリー
森構造	複数のツリー
無層ネットワーク	オブジェクト群、RDBのテーブル群
多層ネットワーク	マップ、ハッシュ、タグ