アルゴリズム図鑑というアプリに触発されて、改めてデータ構造とアルゴリズムについて復習してみたくなりました。
まずはよく使う５種類のデータ構造（配列、リスト、キュー、スタック、ハッシュテーブル）について、出来るだけ分かりやすく特徴を説明します。
また、後で見返したときに意味があるものにするために、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++11からstd::arrayが使えるようになったようです。
・std::vectorは可変長配列。std::arrayは固定長配列。

Java

（補足）
・JavaのArrayListは紛らわしいですが、Listインターフェースを実装した可変長配列のこと。

C＃

（補足）
・C#のList<T>は、Listインターフェースの配列実装。
・T[]と宣言すると、内部ではArrayクラスになっている。

複数の値の連続性を次の要素への参照（ポインタ）で表すデータ構造で、連結リストとも呼ばれます。
次の要素への参照を辿ることで、先頭から順番にアクセスすることが出来ます。
先頭から順に参照を辿る必要があるため、ランダムアクセスが低速になります。
しかし、要素の挿入時に配列のように要素をずらす処理が不要になるため、データの挿入は高速になります。
配列と丁度逆の特徴となるため、保持するデータの用途によって使い分けます。

計算量(Order)

追加：O(1)
挿入：O(1)
削除：O(1)
参照：O(N)

コレクション(Collection)

C++(STL)	Java	C#
std::list	LinkedList<E>	LinkedList<T>

リファレンス(Reference)

C++

Java

C＃

キュー

特徴(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

（補足）
・既知のすべての実装クラス:
AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

C＃

（補足）
・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++

Java

（補足）
・古い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++

（補足）
・std::mapは二分木での実装。std::unordered_map(C++11)がハッシュテーブルによる実装。

配列

特徴(Feature)

計算量(Order)

コレクション(Collection)

リファレンス(Reference)

C++

Java

C＃

リスト

特徴(Feature)

計算量(Order)

コレクション(Collection)

リファレンス(Reference)

C++

Java

C＃

キュー

特徴(Feature)

計算量(Order)

コレクション(Collection)

リファレンス(Reference)

C++

Java

C＃

スタック

特徴(Feature)

計算量(Order)

コレクション(Collection)

リファレンス(Reference)

C++

Java

C＃

ハッシュテーブル

特徴(Feature)

計算量(Order)

コレクション(Collection)

リファレンス(Reference)

C++

Java

C＃

その他のコレクション