List<T> // Динамический массив
LinkedList<T> // Двусвязный список
Queue<T> // Очередь (FIFO)
Stack<T> // Стек (LIFO)
Dictionary<TKey, TValue> // Хэш-таблица
SortedDictionary<TKey, TValue> // На основе бинарного дерева
Hashtable // Устаревший non-generic аналог Dictionary
HashSet<T> // Неупорядоченное множество уникальных элементов
SortedSet<T> // Упорядоченное множество
ObservableCollection<T> // Для WPF/Silverlight (уведомляет об изменениях)
ConcurrentBag<T> // Потокобезопасная коллекция
BlockingCollection<T> // Для Producer-Consumer сценариев
var list = new List<int> {1, 2, 3};
list.Add(4); // O(1) амортизированное
list.Insert(0, 0); // O(n)
int val = list[2]; // O(1)
Применение: Основная "рабочая лошадка" для хранения элементов, когда нужен доступ по индексу.
var linkedList = new LinkedList<string>();
linkedList.AddLast("first"); // O(1)
linkedList.AddFirst("zero"); // O(1)
Применение: Когда важны частые вставки/удаления в середине коллекции (O(1) при наличии ссылки на узел).
var dict = new Dictionary<string, int>();
dict["one"] = 1; // O(1)
dict.ContainsKey("two"); // O(1)
Применение: Быстрый поиск по ключу, ассоциативные массивы.
var set = new HashSet<int>();
set.Add(1); // O(1)
set.UnionWith(new[] {2, 3}); // Объединение множеств
Применение: Проверка уникальности, математические операции над множествами.
var queue = new Queue<string>();
queue.Enqueue("first"); // O(1)
string item = queue.Dequeue(); // O(1)
Применение: Обработка задач в порядке поступления (FIFO).
var stack = new Stack<double>();
stack.Push(3.14); // O(1)
double val = stack.Pop(); // O(1)
Применение: Алгоритмы с LIFO логикой (например, отмена действий).
ConcurrentDictionary<TKey, TValue> // Потокобезопасный словарь
ConcurrentQueue<T> // Потокобезопасная очередь
ConcurrentStack<T> // Потокобезопасный стек
ConcurrentBag<T> // Неупорядоченная коллекция
ArrayList // Устаревший аналог List<T>
Hashtable // Устаревший аналог Dictionary<TKey, TValue>
Queue // Устаревший аналог Queue<T>
| Коллекция | Добавление | Поиск | Удаление | Доступ по индексу |
|---|---|---|---|---|
| List<T> | O(1)* | O(n) | O(n) | O(1) |
| LinkedList<T> | O(1) | O(n) | O(1)** | O(n) |
| Dictionary<K,V> | O(1) | O(1) | O(1) | - |
| HashSet<T> | O(1) | O(1) | O(1) | - |
| Queue<T> | O(1) | - | O(1) | - |
| Stack<T> | O(1) | - | O(1) | - |
*Амортизированная сложность для List
В C# доступен богатый выбор коллекций, каждая из которых оптимизирована для конкретных сценариев использования. Понимание их внутреннего устройства и характеристик производительности позволяет выбирать оптимальную структуру данных для каждой задачи, что значительно влияет на эффективность кода.