39
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

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

.NETのGenericコレクションの使い方サンプル(計算量付き)
C#(.NET)コレクションの使い分けヒント の続き

List<T>

内部データ構造は配列。

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<T>

内部データ構造は連結リスト。

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<T>

内部データ構造は循環配列。

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<T>

内部データ構造は配列。

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<TKey, TValue>

内部データ構造はハッシュテーブル。

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<TKey>)のGetHashCode()が偏りのないハッシュを返す

SortedDictionary<TKey, TValue>

内部データ構造は二分探索木。

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<TKey, TValue>

内部データ構造は(ソートされた)配列。

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<T>

内部データ構造はハッシュテーブル。

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<TKey>)のGetHashCode()が偏りのないハッシュを返す

SortedSet<T>

内部データ構造は二分探索木。

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"));
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
39
Help us understand the problem. What are the problem?