Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

.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"));
takutoy
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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした