Performance summary of C's various collection operations

This article mainly records the performance of the various collection operations of C#. The following tags describe the time of the tags, and the following table compares the time of the various operations of the various collections.

Marking instructions:
1.O(1) means that the operation takes the same amount of time no matter how many items are in the collection; for example,ArraryLIst's Add() method is O(1), and it takes the same amount of time to add a new element to the end of the list no matter how many elements are in the collection.
2. O(n) means that for each element in the set, the amount of time needed to be increased is the same, if the set needs to be re-scored
With memory,ArrayList's Add() method on O(n), changes the capacity, needs to copy the list, the copy time increases with the increase of the element and the linear increase.
3. O(log n) indicates that the time required for the operation increases and increases with the increase of elements in the set, but the increase of time per element is not
It's linear. It's a logarithmic curve. When you insert into a set,SortedDictionary < Tkey,Tvalue > is
SortedList O (log n) < Tkey,Tvalue > O(n), SortedDictionary < Tkey,Tvalue >
It's much faster because it's much more efficient to insert elements into the tree than the list.

The following table shows the operation times of various collections:
Note: if there are multiple large O values in the cell, the collection needs to be resized, which will take 1 definite time
If the cell content is no, this operation is not supported.
A collection of Add Insert Remove Item Sort Find List < T > If the set has to be resized it's either O(1) or O(n) O(n) O(n) O(1) O(n log n) worst case O(n^2) O(n) Stack < T > (stack) Push(), if the stack has to be resized, O(1) or O(n) no Pop(),O(1) no no no Queue < T > (march) Enqueue(), if the stack has to be resized, O(1) or O(n) no Dequeu(),O(1) no no no HastSet < T > (unordered list) If the stack has to be resized, O(1) or O(n)

Add()

O (1) or O (n)

O(1) no no no LinkedList < T > (list) AddLast(),O(1) AddAfter(),O(1) O(1) no no O(n) Dictionary < Tkey,TValue > O (1) or O (n) no O(1) O(1) no no SortedDictionary < Tkey,Tvalue > O(log n) no O(log n) O(log n) no no SortedList < Tkey,Tvalue >

The unordered data is O(n), and if resize is required, it goes to the end of the list

O(log n)

no O(n) Read and write is O(log n), O(log n) if the key is in the list, O(n) if the key is not in the list. no no
Conclusion:
The size of the array is fixed, but can use the list as a collection of dynamic growth, lined up first in first out of the way to access the elements, after stack into the first access to elements, linked list to quickly insert and delete elements, search slowly, but through the keys and values can use a dictionary, it's search and insert operation is faster, set (Hashset < T > ) is the only term for disorder.
Code changes the world and records knowledge.