Choosing the Right Collection Class in .Net. Algorithm complexity.

Базовый набор коллекций в .Net представлен в пространстве имён System.Collections, но они давно устарели, они не типизированы и в большинстве работают медленнее их аналогов. По этой причине сразу перейду к коллекциям из пространства имён System.Collections.Generic.

System.Collections.Generic.

Базовые типизированные коллекции: 

List<T>, LinkedList<T>, HashSet<T>, SortedSet<T>, Stack<T>, Queue<T>.

List<T> является основным контейнером для хранения данных. По сути, это массив элементов. Поскольку элементы хранятся непрерывно в виде массива, мы можете получить доступ к элементам в List<T> по индексу очень быстро. Однако удалить или вставить элемент в начале или середине коллекции требуют затрат времени, поскольку происходит сдвиг части элементы вверх или вниз. Тем не менее, добавление и удаление в конце List<T> является быстрой операцией.

LinkedList<T> является двусвязным списком. Это значит что вставка или удаление элементов происходит быстро. 

HashSet<T> и SortedSet<T>. Оба реализуют интерфейс ISet<T>. Класс HashSet<T> содержит неупорядоченный список уникальных элементов, в свою очередь в SortedSet<T> элементы упорядочены. Используются очень редко. Позволяют более оптимально реализовать операции над множествами — пересечение, объединение и вычитание. Резервируют значительно больше памяти, чем нужно для хранения их элементов, поэтому их имеет смысл использовать только для множеств среднего размера.

Stack<T>, Queue<T>, реализация стека и очереди.

Ассоциативные коллекции:

Dictionary<TKey,TVale> - сама часто используемая ассоциативная коллекция. Классическая хеш-таблица. Хорошо справляется с поиском/удалением/вставкой элементов.

SortedDictionary<TKey,TValue> и SortedList<TKey,TValue> похожи на Dictionary<TKey,TVale> и реализуют интерфейс IDictionary, но они сохраняют свои элементы в порядке сортировки по ключу. Классы SortedDictionary<TKey,TValue> и SortedList<TKey,TValue> имеют схожую функциональность. Но поскольку SortedList<TKey,TValue> реализован в виде списка, основанного на массиве, a SortedDictionary<TKey,TValue> реализован как словарь, эти классы обладают разными характеристиками:

SortedList<TKey,TValue> использует меньше памяти, чем SortedDictionary<TKey,TValue>, но

SortedDictionary<TKey,TValue> быстрее вставляет и удаляет элементы.

System.Collections.Concurrent.

System.Collections.Concurrent содержит потокоустойчивые коллекции:

ConcurrentDictionary Потокобезопасная версия Dictionary.

ConcurrentBag: Потокобезопасная коллекция неупорядоченный объектов.

ConcurrentQueue: Потокобезопасная версия Queue.

ConcurrentStack: Потокобезопасная версия Stack.

Более подробную информацию можно почитать в этой статье, из нею приведу сводную таблицу по коллекциям:

Collection	Ordering	Contiguous Storage?	Direct Access?	Lookup Efficiency	Manipulate Efficiency	Notes
Dictionary	Unordered	Yes	Via Key	Key: O(1)	O(1)	Best for high performance lookups.
SortedDictionary	Sorted	No	Via Key	Key: O(log n)	O(log n)	Compromise of Dictionary speed and ordering, uses binarysearch tree.
SortedList	Sorted	Yes	Via Key	Key: O(log n)	O(n)	Very similar toSortedDictionary, except tree is implemented in an array, so has faster lookup on preloaded data, but slower loads.
List	User has precise control over element ordering	Yes	Via Index	Index: O(1) Value: O(n)	O(n)	Best for smaller lists where direct access required and no sorting.
LinkedList	User has precise control over element ordering	No	No	Value: O(n)	O(1)	Best for lists where inserting/deleting in middle is common and no direct access required.
HashSet	Unordered	Yes	Via Key	Key: O(1)	O(1)	Unique unordered collection, like a Dictionary except key and value are same object.
SortedSet	Sorted	No	Via Key	Key: O(log n)	O(log n)	Unique sorted collection, like SortedDictionary except key and value are same object.
Stack	LIFO	Yes	Only Top	Top: O(1)	O(1)*	Essentially same as List<T> except only process as LIFO
Queue	FIFO	Yes	Only Front	Front: O(1)	O(1)	Essentially same as List<T> except only process as FIFO