データ構造と用途について

概要

配列・ハッシュ・ツリーなど、様々なデータ構造があります。
用途によって向き不向きがあるので、まとめておきます。

データ構造

配列(Array)

データが単純に一列に並んだ構造です。
algo-logic.info

環状バッファ(Ring Buffer)

最後と最初をつなげた配列です。
ufcpp.net

ギャップバッファ(Gap Buffer)

編集した箇所にギャップ（すき間）を作るように要素を移動する配列です。
takty.stxst.com

連結リスト(Linked List)

要素から前や次の要素へのリンクがある構造です。
www.codereading.com

二分探索木(Binary Search Tree)

要素が２つのリンクを持ち、左側が自分より小さく、右側が自分より大きくなるように維持した構造です。平衡を保つ機構として、ＡＶＬ木・赤黒木が優秀です。
ufcpp.net

二分ヒープ(Binary Heap)

要素が２つのリンクを持ち、両方が自分より小さい値になるように維持した構造です。
www.codereading.com

ハッシュテーブル(Hash Table)

要素を要約した数値（ハッシュ）を計算し、その数値に応じた場所に要素を入れる構造です。
qiita.com

用途と向き不向き

値を一つずつ最後まで列挙する

◎　どれでも良いですが、配列・リングバッファ・ギャップバッファが特に速いです。

末尾に追加

◎　配列・リングバッファ・ギャップバッファが速いですが、どれでも良いです。

先頭に挿入

△　配列の先頭に挿入すると、全ての要素を後ろに１つずつずらすことになり、時間が掛かります。
→　代わりに、環状バッファを検討してください。

同じ個所に何度も挿入

△　配列・環状バッファの途中に挿入すると、以降の要素を後ろに１つずつずらすことになり、時間が掛かります。
→　代わりにギャップバッファを検討してください。

格納された値で検索

◎　ハッシュテーブルが速いです。
◎　二分探索木も良いです。
△　配列・リングバッファ・ギャップバッファは、先頭から調べていくことになるので時間が掛かります。
→　並べ替えてソート済の配列にしてしまえば、検索は二分探索木と同じ速さになります。

格納された値の最大値（または最小値）を調べる

◎　ヒープでは、木の根が必ず最大値（または最小値）になるため、最速で処理が可能です。
◎　二分探索木も良いです。
△　配列・リングバッファ・ギャップバッファは、先頭から調べていくことになるので、時間がかかります。
→　並べ替えてソート済みの配列にすれば、最大値も最小値も最速で取得できます。（並べ替えるのに時間が掛かりますが……）

まとめ

用途に合わせてデータ構造を選べば、速度は爆上がりです。