C#(.NET)コレクションの使い方と計算量

.NETのGenericコレクションの使い方サンプル（計算量付き）
[C#(.NET)コレクションの使い分けヒント](http://qiita.com/takutoy/items/cb1e94c36296108e5fd7)　の続き

## List&lt;T&gt;
内部データ構造は配列。

```csharp
var list = new List<string>();

// 追加 : O(1)
list.Add("item");

// 取得 : O(1)
var item = list[0];

// 検索 : O(n)
int index = list.IndexOf("item");
bool contains = list.Contains("item");
var finditem = list.Find(_ => _.StartsWith("it"));

// ソート : O(n log n)
list.Sort();

// 列挙 : O(1) ※GetEnumerator()のみ。foreachを含めたらO(n)
foreach (var element in list)
{
    Console.WriteLine(element);
}

// 削除 : O(n)
bool removed = list.Remove("itemmmm");
list.RemoveAt(0);
```

## LinkedList&lt;T&gt;
内部データ構造は連結リスト。

```csharp
var llist = new LinkedList<string>();

// 追加 : O(1)
LinkedListNode<string> addedNode = llist.AddLast("value");
LinkedListNode<string> addedNode2 = llist.AddAfter(addedNode, "value2");

// 検索 : O(n)
bool contains = llist.Contains("value");

// 検索と取得 : O(n)
LinkedListNode<string> findNode = llist.Find("value");
var value = findNode.Value;

// 列挙 : O(1)
foreach (var element in llist)
{
    Console.WriteLine(element);
}

// 削除(要素指定) : O(n)
bool removed = llist.Remove("value");

// 削除(ノード指定) : O(1)
llist.Remove(addedNode2);
llist.RemoveFirst();
```

## Queue&lt;T&gt;
内部データ構造は循環配列。

```csharp
var queue = new Queue<string>();

// エンキュー : O(1)
queue.Enqueue("item");

// 検索 : O(n)
bool contains = queue.Contains("item");

// ピーク : O(1)
var item = queue.Peek();

// デキュー : O(1)
var item2 = queue.Dequeue();
```

## Stack&lt;T&gt;
内部データ構造は配列。

```csharp
var stack = new Stack<string>();

// プッシュ : O(1)
stack.Push("item");

// 検索 : O(n)
bool contains = stack.Contains("item");

// ピーク : O(1)
var item = stack.Peek();

// ポップ : O(1)
var item2 = stack.Pop();
```

## Dictionary&lt;TKey, TValue&gt;
内部データ構造はハッシュテーブル。

```csharp
var dict = new Dictionary<string, string>();

// 追加 : O(1)
dict.Add("key", "value");

// 検索 : O(1)
bool containsKey = dict.ContainsKey("key");

// 取得 : O(1)
var value = dict["key"];

// 削除 : O(1)
bool removed = dict.Remove("key");
```

※備考
O(1)になるには下記の条件が必要。そうでない場合はO(n)に近づく。

- CountがCapacityより十分少ない
- TKey（またはIEqualityComparer&lt;TKey&gt;）のGetHashCode()が偏りのないハッシュを返す


## SortedDictionary&lt;TKey, TValue&gt;
内部データ構造は二分探索木。

```csharp
var sdict = new SortedDictionary<string, string>();

// 追加：O(log n)
sdict.Add("key2", "value2");
sdict.Add("key", "value");

// 検索：O(log n)
bool contains = sdict.ContainsKey("key");

// 取得：O(log n)
var value = sdict["key"];

// 列挙：O(log n)
foreach (var element in sdict)
{
    Console.WriteLine($"Key={element.Key}, Value={element.Value}");
}

// 削除：O(log n)
bool removed = sdict.Remove("key");
```
    
## SortedList&lt;TKey, TValue&gt;
内部データ構造は（ソートされた）配列。

```csharp
var slist = new SortedList<string, string>();

// 追加：O(n)
slist.Add("key", "value");
slist.Add("key2", "value");

// 検索：O(log n)
bool containsKey = slist.ContainsKey("key");
int indexKey = slist.IndexOfKey("key");

// 取得：O(log n)
var value = slist["key"];

// 取得(インデックス使用)：O(1)
var keybyindex = slist.Keys[0];
var valuebyindex = slist.Values[0];

// 列挙：O(1)
foreach (var element in slist)
{
	Console.WriteLine($"Key={element.Key}, Value={element.Value}");
}

// 削除：O(n)
bool removed = slist.Remove("key");
slist.RemoveAt(0);
```

## HashSet&lt;T&gt;
内部データ構造はハッシュテーブル。

```csharp
var set = new HashSet<string>();

// 追加：O(1)
bool added = set.Add("item");

// 検索：O(1)
bool contains = set.Contains("item");

// 集合演算：O(n) ~ O(n+m)
set.UnionWith(new[] { "otheritem" });
set.IntersectWith(new[] { "item" });

// 列挙：O(1)
foreach (var element in set)
{
	Console.WriteLine(element);
}

// 削除：O(1)
bool removed = set.Remove("item");

// 削除(条件指定)：O(n)
int removedCount = set.RemoveWhere(_ => _.StartsWith("it"));
```

※備考
O(1)になるには下記の条件が必要。そうでない場合はO(n)に近づく。

- CountがCapacityより十分少ない
- TKey（またはIEqualityComparer&lt;TKey&gt;）のGetHashCode()が偏りのないハッシュを返す

## SortedSet&lt;T&gt;
内部データ構造は二分探索木。

```csharp
var sset = new SortedSet<string>();

// 追加：O(log n)
bool added = sset.Add("item");
sset.Add("item2");
sset.Add("item4");
sset.Add("item3");

// 検索：O(log n)
bool contains = sset.Contains("item");

// 集合演算：O(n) ~ O(n+m)
sset.UnionWith(new[] { "otheritem" });

// 列挙：O(log n)
foreach (var element in sset)
{
    Console.WriteLine(element);
}

// 削除：O(log n)
bool removed = sset.Remove("item");

// 削除（条件指定）：O(n)
int removedCount = sset.RemoveWhere(_ => _.StartsWith("it"));
```