アルゴリズム図鑑というアプリに触発されて、改めてデータ構造とアルゴリズムについて復習してみたくなりました。
まずはよく使う５種類のデータ構造（配列、リスト、キュー、スタック、ハッシュテーブル）について、出来るだけ分かりやすく特徴を説明します。
また、後で見返したときに意味があるものにするために、C++、Java、C#の各コレクションの実装について、関連サイトのリファレンスを残しました。
配列
特徴(Feature)
- ランダムアクセスが得意
- 挿入、削除が苦手
複数の値をメモリ上の連続した領域に並べて配置するデータ構造です。
メモリ上の連続した領域に配置することにより、添字からメモリアドレスを計算出来るため（配列の先頭アドレス + (添字 * サイズ)）、任意の要素へのランダムアクセスが高速になります。
任意の場所に要素を挿入する場合、挿入したデータ以降の要素を後ろに1つずつずらす処理が行われるため、データの挿入は低速です。
計算量(Order)
- 追加：O(1) ※最後尾への追加
- 挿入：O(N)
- 削除：O(N)
- 参照：O(1)
コレクション(Collection)
| C++(STL) | Java | C# |
|---|---|---|
| std::vector | ArrayList<E> | List<T> |
リファレンス(Reference)
C++
- [C++] STLの型の使い分け - Qiita
- C++ 動的配列クラス std::vector 入門
- Programming Place Plus C++編【標準ライブラリ】 第５章 vector
- 【C++】配列とVectorとArrayで比較 - タイトルって難しい。
- array - cpprefjp C++日本語リファレンス
（補足）
・C++11からstd::arrayが使えるようになったようです。
・std::vectorは可変長配列。std::arrayは固定長配列。
Java
- ArrayList (Java Platform SE 7)
- ArrayListクラス - コレクション(ArrayList) - Java入門
- CopyOnWriteArrayList (Java Platform SE 6)
- ArrayBlockingQueue (Java Platform SE 6)
（補足）
・JavaのArrayListは紛らわしいですが、Listインターフェースを実装した可変長配列のこと。
C＃
- List(T) クラス (System.Collections.Generic)
- C# 動的配列 List 入門
- List<T>クラス | C# プログラミング解説
- SynchronizedCollection(T) クラス (System.Collections.Generic)
- スレッドセーフなコレクション | 計測制御ソフト受託開発 インフォテック ブログ
- Array クラス (System)
- 配列 (C# プログラミング ガイド) | Microsoft Docs
- 配列 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C
（補足）
・C#のList<T>は、Listインターフェースの配列実装。
・T[]と宣言すると、内部ではArrayクラスになっている。
リスト
特徴(Feature)
- 挿入、削除が得意
- ランダムアクセスが苦手
複数の値の連続性を次の要素への参照（ポインタ）で表すデータ構造で、連結リストとも呼ばれます。
次の要素への参照を辿ることで、先頭から順番にアクセスすることが出来ます。
先頭から順に参照を辿る必要があるため、ランダムアクセスが低速になります。
しかし、要素の挿入時に配列のように要素をずらす処理が不要になるため、データの挿入は高速になります。
配列と丁度逆の特徴となるため、保持するデータの用途によって使い分けます。
計算量(Order)
- 追加：O(1)
- 挿入：O(1)
- 削除：O(1)
- 参照：O(N)
コレクション(Collection)
| C++(STL) | Java | C# |
|---|---|---|
| std::list | LinkedList<E> | LinkedList<T> |
リファレンス(Reference)
C++
- list - cpprefjp C++日本語リファレンス
- C++ 双方向リストクラス std::list 入門
- std::list - cppreference.com
- Programming Place Plus C++編【標準ライブラリ】 第６章 list
Java
- LinkedList (Java Platform SE 8)
- コレクション(LinkedList) - Java入門
- LinkedListクラス - Javaちょこっとリファレンス
- Javaのリストにマルチスレッドでアクセスする３種類の方法のおさらい - Qiita
C＃
- LinkedList(T) クラス (System.Collections.Generic)
- 双方向連結リスト - アルゴリズムとデータ構造 | ++C++; // 未確認飛行 C
- ジェネリックコレクション その4 LinkedList - 総武ソフトウェア推進所
- List と LinkedList の性能差 - えこ日記
キュー
特徴(Feature)
- 先入れ先出し方式のデータ操作が可能
コレクションの最後尾にのみ要素を追加することができ、先頭からのみ要素を取り出すことが出来る、先入れ先出し式のデータ構造を表します。
FIFO (first-in first-out)方式と言われ、待ち行列とも呼ばれます。
要素を追加することをEnqueue、取り出すことをDequeueと言います。
基本的に取り出された要素はキューから削除されます。
計算量(Order)
- 追加：O(1)
- 挿入：×
- 削除：O(1)
- 参照：O(1) ※先頭の要素のみアクセス可
コレクション(Collection)
| C++(STL) | Java | C# |
|---|---|---|
| std::queue | Queue<E> | Queue<T> |
リファレンス(Reference)
C++
（補足）
・単にqueue<T>と書いた場合、queue<T, deque<T>>と書いたのと同じ意味になり、デフォルト実装のdeque<T>になる。
Java
- Queue (Java Platform SE 8)
- キュー | アルゴリズムとデータ構造 | Aizu Online Judge
- [Java] スタック・キューのメモ - Qiita
- ArrayDeque | Javaコード入門
- 今まで知らなかった 5 つの事項: java.util.concurrent 第 1 回
（補足）
・既知のすべての実装クラス:
AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue
C＃
- Queue(T) クラス (System.Collections.Generic)
- ConcurrentQueue(T) クラス (System.Collections.Concurrent)
- Queue型 - C#プチリファレンス
- ジェネリックコレクション その6 Queue - 総武ソフトウェア推進所
（補足）
・ConcurrentQueue(T)は、.NET Framework 4.0 以降で使用可能。
・コレクションが空またはいっぱいになったときにブロックする必要がある場合は、BlockingCollection<T> クラスが使えそう。
・古いバージョンの.NET Frameworkでは、Synchronizedメソッドでスレッドセーフなラッパーを使用していたようだ。
スタック
特徴(Feature)
- 後入れ先出し方式のデータ操作が可能
コレクションの最後尾にのみ要素を追加することができ、最後尾からのみ要素を取り出すことが出来る、後入れ先出し式のデータ構造を表します。
LIFO (last-in first-out)方式と言われます。
筒状の入れ物にデータを入れたり、本を積んでいくようなイメージを持つと理解しやすいと思います。
要素を追加することをPush、取り出すことをPopと言います。
基本的に取り出された要素はスタックから削除されます。
計算量(Order)
- 追加：O(1)
- 挿入：×
- 削除：O(1)
- 参照：O(1) ※最後尾の要素のみアクセス可
コレクション(Collection)
| C++(STL) | Java | C# |
|---|---|---|
| std::stack | Deque<E> | Stack<T> |
リファレンス(Reference)
C++
- stack - cpprefjp C++日本語リファレンス
- Programming Place Plus C++編【標準ライブラリ】 第１０章 stack
- C++コンテナ std::stack - Qiita
- stack - C++ Reference
Java
- Deque (Java Platform SE 8)
- BlockingDeque (Java Platform SE 8)
- <Java>Dequeインターフェースの使い方 - 東大ニート
- ArrayDeque | Javaコード入門
- DequeとStackと - CLOVER
- Java SE 6 のコレクション・フレームワークのメソッド (5) : BlockingQueue, BlockingDeque - 倭マン's BLOG
（補足）
・古いjava.util.Stackよりは、java.util.Dequeを使う方が良さそう。
・既知のすべての実装クラス:
ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList
C＃
ハッシュテーブル
特徴(Feature)
- 要素の検索が超高速
キーと値のペアを複数保持しており、キーに対応する値を高速に取得するためのデータ構造です。
言語によって連想配列や辞書とも呼ばれます。
ハッシュ関数を使ってキーからハッシュ値を求め、格納アドレスを決定するためランダムアクセスが高速なのが最大の特徴です。
計算量オーダーだけみると万能に見えるし、実際弱点が少ないデータ構造な気はしますけど、foreachなどで全データを順番に参照するような用途には向いてないです。（メモリ効率も走査効率も悪い）
全データを走査するような用途の場合は、配列やリストを使います。
特定の要素のみを高速で取得したい場合にハッシュテーブルを採用します。
計算量(Order)
- 追加：O(1)
- 挿入：×
- 削除：O(1)
- 参照：O(1)
コレクション(Collection)
| C++(STL) | Java | C# |
|---|---|---|
| std::unordered_map | HashMap<K,V> | Dictionary(TKey, TValue) |
リファレンス(Reference)
C++
- map - cpprefjp C++日本語リファレンス
- C++ 連想配列クラス std::map 入門
- std::map - cppreference.com
- unordered_map - cpprefjp C++日本語リファレンス
- C++ ハッシュ連想配列クラス unordered_map 入門
- C++11 unordered map(mapとは少し違うよー） - のんびりしているエンジニアの日記
（補足）
・std::mapは二分木での実装。std::unordered_map(C++11)がハッシュテーブルによる実装。
Java
- HashMap (Java Platform SE 8)
- LinkedHashMap (Java Platform SE 8)
- コレクション(HashMap) - Java入門
- LinkedHashMap | Java | 株式会社CONFRAGE
- ConcurrentHashMap (Java Platform SE 6)
- ConcurrentHashMapという選択 - 技術開発日記
C＃
- Dictionary(TKey, TValue) クラス (System.Collections.Generic)
- Dictionary型 - C#プチリファレンス
- C# Dictionary<T> の使い方(まとめ)
- .NET TIPS：ハッシュテーブル（連想配列）を使うには？（Dictionaryクラス編）［2.0のみ、C#、VB］ - ＠IT
- ConcurrentDictionary(TKey, TValue) クラス (System.Collections.Concurrent)
- 方法: ConcurrentDictionary の項目を追加および削除する
- ConcurrentDictionaryは、.NET 4.0の新しいスレッドセーフなHashtable
その他のコレクション
名前の紹介だけ。
- 循環バッファ
- 2分探索木
- 優先度付き待ち行列、ヒープ
- セット