個々のコレクションクラスについて詳しく見ていく前に、.NET Frameworkで用意されているコレクションのいくつかと特徴をざっと見ていきます。 .NET Frameworkでは、以下の名前空間にコレクションクラスと関連するインターフェイスが配置されています。

System.Collections名前空間
基本的な非ジェネリックなコレクションクラスと関連するインターフェイス
System.Collections.Generic名前空間
ジェネリックコレクションクラスと関連するインターフェイス
System.Collections.Concurrent名前空間
マルチスレッドでの操作を目的としたスレッドセーフなジェネリックコレクションクラスと関連するインターフェイス
System.Collections.ObjectModel名前空間
独自にジェネリックコレクションクラスを実装するための基本クラス
System.Collections.Specialized名前空間
特定用途に用いられるタイプセーフな非ジェネリックコレクションクラス

§1 コレクションクラスの種類とインターフェイス

System.Collections以下の名前空間に配置されているコレクションクラスの種類を大まかに分けると次の4つに分類できます。

コレクション
単純な要素の集まり
ICollection<T>ICollectionを実装するクラス
リスト
コレクションの機能に加え、要素の入れ替えやインデックスによるアクセスができるコレクション
IList<T>IListを実装するクラス
ディクショナリ
キーによる要素へのアクセスが出来るコレクション
IDictionary<TKey, TValue>IDictionaryを実装するクラス
セット(集合)
集合の概念を表すコレクション
ISet<T>(.NET Framework 4以降)を実装するクラス

上記のインターフェイスはすべてIEnumerable<T>およびIEnumerableを継承しているため、結果としてすべてSystem.CollectionsやSystem.Collections.Generic等の名前空間にあるコレクションクラスは列挙操作が可能になっています。



§2 コレクションクラスの特徴

個々のコレクションクラスが実装するインターフェイスを見ることで、そのコレクションクラスの大まかな特徴が分かります。 以下の表はコレクションクラスの特徴と実装するインターフェイスを抜粋して表にまとめたものです(個々のクラスの解説にもリンクしています)。 あわせて、要素の取得・設定の操作と、挿入・削除の操作のオーダーをランダウの記号を用いて併記しています。 表中のnはコレクション内の要素数を表します。

§2.1 コレクション、リストのクラスと特徴

配列(Array)はSystem.Collections名前空間には含まれないクラスですが、比較のため表中に含めています。

コレクション、リストのクラスと特徴
クラス データ構造 インデックスによるアクセス 要素の取得・設定 要素の挿入・削除 実装するインターフェイス
Array リスト (固定長) できる O(1) - IList<T>, ICollection<T>, IList, ICollection
ArrayList リスト (可変長) できる O(1) O(n)*1 IList, ICollection
List<T> リスト (可変長) できる O(1) O(n)*1 IList<T>, IList, ICollection<T>, ICollection
Collection<T> リスト (可変長) できる O(1) O(n)*1 IList<T>, IList, ICollection<T>, ICollection
LinkedList<T> 双方向連結リスト できない O(1)*2 O(1) ICollection<T>, ICollection
Queue キュー できない O(1)*3 O(n)*1 ICollection
Queue<T> キュー できない O(1)*3 O(n)*1 ICollection
(ICollection<T>は実装していない)
Stack スタック できない O(1)*3 O(n)*1 ICollection
Stack<T> スタック できない O(1)*3 O(n)*1 ICollection
(ICollection<T>は実装していない)
*1
容量の拡張が不要で、かつ末尾への追加となる場合はO(1)となる。
*2
取得・設定しようとするノードの位置が既知の場合。 ノードの検索はO(n)となる。
*3
Peek, Dequeue, Popなどの操作による取得の場合。 設定は出来ない。

§2.2 ディクショナリのクラスと特徴

ディクショナリのクラスと特徴
クラス インデックスによるアクセス 要素のソート 要素のキー 要素の取得・設定 要素の挿入・削除 実装するインターフェイス
Hashtable できない されない 独立した値 O(1) O(1)*2 IDictionary, ICollection
Dictionary<TKey, TValue> できない されない 独立した値 ほぼO(1) ほぼO(1)*2 IDictionary<TKey, TValue>, IDictionary, ICollection<KeyValuePair<TKey, TValue>>, ICollection
SortedList できる される 独立した値 O(log n)*1 O(n)*3 IDictionary, ICollection
SortedList<TKey, TValue> できる される 独立した値 O(log n)*1 O(n)*3 IDictionary<TKey, TValue>, IDictionary, ICollection<KeyValuePair<TKey, TValue>>, ICollection
SortedDictionary<TKey, TValue> できない される 独立した値 O(log n) O(log n) IDictionary<TKey, TValue>, IDictionary, ICollection<KeyValuePair<TKey, TValue>>, ICollection
KeyedCollection<TKey, TItem> できる されない 要素自身から取得 O(1) O(n)*4 IList<TItem>, IList, ICollection<TItem>, ICollection
OrderedDictionary できる されない 独立した値 ? ? IOrderedDictionary, IDictionary, ICollection
*1
存在しないキーの要素を設定する場合はO(n)となる。
*2
挿入により容量が拡張される場合はO(n)となる。
*3
末尾への追加となる場合はO(log n)となる。
*4
末尾への追加となる場合はO(1)となる。

§2.3 セットのクラスと特徴

セットのクラスと特徴
クラス インデックスによるアクセス 要素のソート 要素の挿入・削除 実装するインターフェイス
HashSet<T> できない されない O(1)*1 ISet<T>, ICollection<T>
SortedSet<T> できない される O(1)*1 ISet<T>, ICollection<T>, ICollection
*1
挿入により容量が拡張される場合はO(n)となる。