Коллекции и структуры данных в C#

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору

Сначала — теория (раздел 3 "Данные")

Структуры данных — о разделе → реализация и псевдокод операций → Коллекции в контексте ООП.

Ниже — коллекции C#.

список.Add(x)                         // List<T> — динамический массив
значение := список[i]

словарь[key] := value                 // Dictionary — хеш, O(1) в среднем
значение := словарь[key]

очередь.Enqueue(x); x := очередь.Dequeue()   // FIFO

Разбор:

• Фрагмент начинается с список.Add(x) // List<T> — динамический массив и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: List<T> используется как типобезопасная динамическая коллекция с доступом по индексу.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

Play ITЗагрузка интерактивного демо…

Play ITЗагрузка интерактивного демо…

---

Как выбирать коллекцию на практике

Когда видишь много коллекций, легко потеряться. Проще выбирать от задачи:

• нужен "рабочий" список элементов с индексом - List<T>;
• нужны уникальные элементы - HashSet<T>;
• нужен быстрый доступ по ключу - Dictionary<TKey, TValue>;
• нужна очередь задач - Queue<T>;
• нужен стек действий (undo/redo) - Stack<T>.

Главное: не искать "лучшую коллекцию на все случаи". Такой не бывает. Бывает подходящая под конкретные операции.

---

Частые ошибки и как их избежать

• Использовать List<T> там, где важна уникальность: тут лучше HashSet<T>.
• Обращаться к dict[key] без проверки ключа: безопаснее TryGetValue.
• Брать потокобезопасные коллекции "просто так": в однопоточном коде это лишние накладные расходы.
• Рано оптимизировать без замеров: сначала понять, где реально узкое место.

---

Мини-практикум

1. Возьмите сценарий "каталог товаров".
2. Разложите данные по 3 коллекциям — список для вывода, словарь по Id, множество тегов.
3. Замерьте время на поиск товара по имени в List<T> и по Id в Dictionary<TKey, TValue>.
4. Сравните асимптотику с фактическим временем на маленьких и больших объёмах.

Связанные материалы — Ковариантность, контравариантность, инвариантность, LINQ, Итераторы и ключевое слово yield.

---

Коллекции и структуры данных в C#

Коллекции

В реальной разработке редко приходится работать с одним объектом. Чаще всего — у нас есть список пользователей, набор заказов, список настроек, очередь задач и т.д. Чтобы эффективно хранить, обрабатывать и управлять такими группами, в C# существует мощная система коллекций.

Коллекция — это структура данных, предназначенная для хранения набора элементов одного или разных типов. Она позволяет добавлять и удалять элементы, перебирать элементы, искать, сортировать, фильтровать, организовывать данные по определённому принципу (по индексу, по ключу, по приоритету и т.д.).

Код ITЗагрузка примера кода…

Разбор:

• Фрагмент начинается с class User и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: List<T> используется как типобезопасная динамическая коллекция с доступом по индексу. foreach перечисляет элементы через GetEnumerator(), MoveNext() и Current. Оператор new создаёт экземпляры объектов и коллекций, формируя рабочее состояние примера.
• Выполнение идёт поэлементно: на каждом шаге цикла берётся текущий элемент и применяется нужное действие.

Без коллекций пришлось бы писать user1, user2, user3… — и быстро запутаться. А что если количество заранее неизвестно, и понадобится делать запрос в базу данных - и там может быть как один user, так и тысяча?

Собственно, поэтому коллекции являются основой для такой работы. И они бывают разные, в зависимости от необходимости.

• Хранить много объектов - List<User>;
• Быстро находить по ID - Dictionary<int, User>;
• Избежать дубликатов - HashSet<User>;
• Обрабатывать по порядку (FIFO) - Queue<Task>;
• Обрабатывать "последний — первый" (LIFO) - Stack<UndoAction>;
• Группировать данные - ILookup<Department, Employee>.

Play ITЗагрузка интерактивного демо…

Play ITЗагрузка интерактивного демо…

Play ITЗагрузка интерактивного демо…

В .NET все коллекции строятся на основе иерархии интерфейсов. Это позволяет писать гибкий, расширяемый и тестируемый код.

Интерфейс	Назначение
IEnumerable<T>	Поддержка перебора элементов (например, с помощью foreach)
ICollection<T>	Предоставляет возможности для добавления, удаления и подсчёта элементов
IList<T>	Обеспечивает доступ к элементам по индексу (list[0]) и поддержку упорядоченного списка
IDictionary<TKey, TValue>	Хранение и управление коллекцией пар "ключ-значение"
ISet<T>	Представляет математическое множество — коллекцию без дублирующихся элементов
IReadOnlyCollection<T>	Коллекция только для чтения, с возможностью получения количества элементов
IReadOnlyList<T>	Список только для чтения, с доступом к элементам по индексу

IEnumerable<T> - лучше всего подходит для переборов. Позволяет использовать foreach, ковариантен (out T) - можно присвоить IEnumerable<string> переменной IEnumerable<object>. Реализуется всеми коллекциями.

public interface IEnumerable<out T>
{
    IEnumerator<T> GetEnumerator();
}

Разбор:

• Фрагмент начинается с public interface IEnumerable<out T> и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: IEnumerable<T> задаёт контракт перечисления и поддерживает ленивую обработку последовательности.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

Пример:

IEnumerable<string> names = new List<string> { "Alice", "Bob" };
foreach (string name in names) { ... }

Разбор:

• Фрагмент начинается с IEnumerable<string> names = new List<string> { "Alice", "Bob" }; и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: List<T> используется как типобезопасная динамическая коллекция с доступом по индексу. IEnumerable<T> задаёт контракт перечисления и поддерживает ленивую обработку последовательности. foreach перечисляет элементы через GetEnumerator(), MoveNext() и Current.
• Выполнение идёт поэлементно: на каждом шаге цикла берётся текущий элемент и применяется нужное действие.

yield return — ключевое слово для ленивого перебора:

public static IEnumerable<int> GetNumbers()
{
    yield return 1;
    yield return 2;
    yield return 3;
}

Разбор:

• Фрагмент начинается с public static IEnumerable<int> GetNumbers() и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: IEnumerable<T> задаёт контракт перечисления и поддерживает ленивую обработку последовательности. yield return выдаёт элементы по одному и сохраняет состояние итератора между шагами.
• Поток выполнения ленивый: метод продолжает выполнение только при запросе следующего элемента, а не целиком за один вызов.

IEnumerator<T> - это итератор. Он управляет текущим элементом при переборе.

public interface IEnumerator<out T> : IDisposable
{
    T Current { get; }
    bool MoveNext(); // Переходит к следующему элементу
    void Reset();    // Сбрасывает (редко используется)
}

Разбор:

• Фрагмент начинается с public interface IEnumerator<out T> : IDisposable и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Основной акцент здесь на типах и сигнатурах: компилятор заранее проверяет корректность использования конструкций.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

foreach под капотом использует GetEnumerator() и MoveNext().

ICollection<T> используется для изменяемых коллекций. Он наследует IEnumerable<T> и добавляет операции Add, Remove, Count.

public interface ICollection<T> : IEnumerable<T>
{
    int Count { get; }
    bool IsReadOnly { get; }
    void Add(T item);
    bool Remove(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
}

Разбор:

• Фрагмент начинается с public interface ICollection<T> : IEnumerable<T> и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: IEnumerable<T> задаёт контракт перечисления и поддерживает ленивую обработку последовательности.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

IList<T> используется для доступа по индексу. Позволяет list[0] = item; и реализуется List<T>, T[].

public interface IList<T> : ICollection<T>
{
    T this[int index] { get; set; } // Индексатор
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);
}

Разбор:

• Фрагмент начинается с public interface IList<T> : ICollection<T> и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: List<T> используется как типобезопасная динамическая коллекция с доступом по индексу.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

IDictionary<TKey, TValue> - это словарь. Он хранит пары "ключ - значение" и позволяет получать быстрый доступ по ключу (O(1) в среднем).

public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>>
{
    TValue this[TKey key] { get; set; }
    ICollection<TKey> Keys { get; }
    ICollection<TValue> Values { get; }
    bool ContainsKey(TKey key);
    bool TryGetValue(TKey key, out TValue value);
    void Add(TKey key, TValue value);
    bool Remove(TKey key);
}

Разбор:

• Фрагмент начинается с public interface IDictionary<TKey, TValue> — ICollection<KeyValuePair<TKey, TValue>> и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: Dictionary<TKey, TValue> хранит пары ключ-значение и ориентирован на быстрый доступ по ключу.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

ISet<T> используется как множество без дубликатов, гарантируя уникальность элементов. Реализуется HashSet<T>, SortedSet<T>.

public interface ISet<T>
{
    bool Add(T item); // Возвращает false, если уже есть
    void UnionWith(IEnumerable<T> other);
    void IntersectWith(IEnumerable<T> other);
    bool IsSubsetOf(IEnumerable<T> other);
}

Разбор:

• Фрагмент начинается с public interface ISet<T> и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: IEnumerable<T> задаёт контракт перечисления и поддерживает ленивую обработку последовательности.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

IReadOnlyCollection<T> и IReadOnlyList<T> нужны для защиты от изменений. Они используются, когда нужно только читать данные.

public interface IReadOnlyCollection<out T> : IEnumerable<T>
{
    int Count { get; }
}

public interface IReadOnlyList<out T> : IReadOnlyCollection<T>
{
    T this[int index] { get; }
}

Разбор:

• Фрагмент начинается с public interface IReadOnlyCollection<out T> : IEnumerable<T> и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: List<T> используется как типобезопасная динамическая коллекция с доступом по индексу. IEnumerable<T> задаёт контракт перечисления и поддерживает ленивую обработку последовательности.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

Есть обобщённые и необобщённые коллекции. Необобщённые нетипобезопасны, требуют приведения типов и заметно медленнее из-за распаковки/упаковки. Необобщённые находятся в System.Collections.

Необобщённые (устаревшие):

• ArrayList - Список объектов object;
• Hashtable - Словарь объектов;
• Queue – Очередь;
• Stack – Стек;
• SortedList - Отсортированный список

Обобщённые:

• List<T> - упорядоченная коллекция элементов;
• Dictionary<TKey, TValue> - словарь "ключ-значение";
• HashSet<T> - множество без дубликатов;
• LinkedList<T> - двусвязный список; быстрые вставки/удаления в середине, медленный доступ по индексу O(n);
• Queue<T> - FIFO (первый вошел – первый вышел);
• Stack<T> - LIFO (последний вошел – первый вышел); внутри — цепочка узлов или массив с ростом, операции push/pop — O(1) амортизированно;
• SortedSet<T> - отсортированное множество;
• ConcurrentBag<T> - Параллельная коллекция.

Параллельные (потокобезопасные) коллекции (из System.Collections.Concurrent):

• ConcurrentQueue<T>
• ConcurrentStack<T>
• ConcurrentDictionary<TKey, TValue>

Потокобезопасные (параллельные) коллекции — это специальные структуры данных, разработанные для безопасной работы из нескольких потоков одновременно. Обычные коллекции, такие как List<T>, Dictionary<TKey, TValue>, не являются потокобезопасными. Если к ним обращаются несколько потоков (особенно с записью), возможны повреждения структуры данных, исключения, гонки данных. Чтобы этого избежать, можно использовать блокировки (lock), но это медленно, сложно в отладке и может привести к взаимоблокировкам (deadlock).

Потокобезопасная коллекция позволяет получать одновременный доступ из нескольких потоков, гарантирует целостность данных, обеспечивает атомарность операций и не требует ручных блокировок в большинстве случаев. Они используют низкоуровневые примитивы (например, Interlocked, SpinWait) для эффективной синхронизации.

Если у вас один поток - используйте обычные коллекции, они быстрее. Также не стоит использовать параллельные коллекции, когда нужен порядок и сортировка, ведь они не гарантируют порядок.

---

Операции по типам коллекций

List<T> и T[] (упорядоченный доступ по индексу):

Действие	List<T>	T[]
Добавить в конец	Add(value)	— (фиксированный размер или новый массив)
Вставить по индексу	Insert(index, value)	—
Прочитать	list[index] или ElementAt(i)	arr[index]
Заменить	list[index] = value	arr[index] = value
Удалить по индексу	RemoveAt(index)	—
Удалить по значению	Remove(value)	—

Dictionary<TKey, TValue> (словарь):

Действие	Метод
Добавить или заменить	Add(key, value) или dict[key] = value
Прочитать	dict[key] или TryGetValue(key, out var v)
Удалить	Remove(key)
Проверить ключ	ContainsKey(key)

HashSet<T> (множество):

Действие	Метод
Добавить	Add(value) — false, если элемент уже был
Удалить	Remove(value)
Проверить	Contains(value)

Queue<T> (FIFO):

Действие	Метод
Добавить в хвост	Enqueue(value)
Извлечь с головы	Dequeue()
Просмотр головы	Peek()

Stack<T> (LIFO):

Действие	Метод
Положить наверх	Push(value)
Снять сверху	Pop()
Просмотр	Peek()

PriorityQueue<T> (.NET 6+): Enqueue, Dequeue — элемент с наивысшим приоритетом извлекается первым.

Очереди и стеки не поддерживают доступ по индексу — только с одного или двух концов.

Пример List<T>:

var items = new List<string> { "a", "b" };
items.Add("c");              // в конец
items.Insert(1, "x");        // в середину
string s = items[0];         // чтение
items[0] = "A";              // замена
items.RemoveAt(2);           // удаление по индексу

Разбор:

• Фрагмент начинается с var items = new List<string> { "a", "b" }; и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: List<T> используется как типобезопасная динамическая коллекция с доступом по индексу. Оператор new создаёт экземпляры объектов и коллекций, формируя рабочее состояние примера.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

---

Кортежи в C# (Tuple и ValueTuple)

Кортежи удобно использовать рядом с коллекциями, когда нужно быстро сгруппировать 2-3 значения без отдельного класса.

В современном C# обычно используют ValueTuple и синтаксис (a, b, c):

var user = (Name: "John", Age: 25);
Console.WriteLine(user.Name); // John
Console.WriteLine(user.Age);  // 25

Разбор:

• Фрагмент начинается с var user = (Name: "John", Age: 25); и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Основной акцент здесь на типах и сигнатурах: компилятор заранее проверяет корректность использования конструкций.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

Имена полей (Name, Age) повышают читаемость и убирают магические Item1, Item2.

---

Возврат нескольких значений из метода

Именованный кортеж часто заменяет out-параметры в простых сценариях:

public static (string Name, bool IsValid) Validate(string input)
{
    var trimmed = input?.Trim() ?? "";
    var isValid = !string.IsNullOrWhiteSpace(trimmed);
    return (trimmed, isValid);
}

var result = Validate("  John  ");
Console.WriteLine(result.Name);    // John
Console.WriteLine(result.IsValid); // True

Разбор:

• Фрагмент начинается с public static (string Name, bool IsValid) Validate(string input) и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Основной акцент здесь на типах и сигнатурах: компилятор заранее проверяет корректность использования конструкций.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

---

Деконструкция

Если сам кортеж дальше не нужен, его можно разложить по переменным:

var (name, isValid) = Validate("  John  ");
Console.WriteLine(name);
Console.WriteLine(isValid);

Разбор:

• Фрагмент начинается с var (name, isValid) = Validate(" John "); и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Основной акцент здесь на типах и сигнатурах: компилятор заранее проверяет корректность использования конструкций.
• Инструкции выполняются последовательно: объявление сущностей, вызов операций и получение конечного результата.

---

Кортежи + коллекции

Кортежи хорошо работают в List<T>, LINQ и временных проекциях:

var users = new List<(int Id, string Name)>
{
    (1, "Alice"),
    (2, "Bob")
};

var shortNames = users
    .Where(u => u.Name.Length <= 4)
    .Select(u => (u.Id, Upper: u.Name.ToUpper()))
    .ToList();

Разбор:

• Фрагмент начинается с var users = new List<(int Id, string Name)> и демонстрирует практический паттерн, который используется в реальном C#-коде.
• Ключевые элементы: List<T> используется как типобезопасная динамическая коллекция с доступом по индексу. Where(...) фильтрует элементы по условию. Select(...) выполняет проекцию и формирует новый результат для каждого элемента.
• LINQ-цепочка выполняется последовательно как конвейер преобразований — фильтрация, проекция, сортировка и материализация.

---

Когда лучше не использовать кортеж

Кортеж подходит для локальной логики и коротких возвращаемых значений. Лучше выбрать class или record, если структура:

• передается между слоями приложения;
• живет в публичном API;
• сериализуется в JSON или хранится в БД;
• используется во многих местах и должна нести доменную семантику.

---

Сложность операций (типовой ответ на собеседовании)

Структура	Поиск	Вставка	Удаление
T[] / List<T> (по индексу)	O(1)	O(1) в конец*, O(n) в середину	O(n)
LinkedList<T>	O(n)	O(1) при известном узле	O(1) при известном узле
Dictionary<K,V>	O(1) среднее	O(1) среднее	O(1) среднее
HashSet<T>	O(1) среднее	O(1) среднее	O(1) среднее
Stack<T> / Queue<T>	—	O(1) push/enqueue	O(1) pop/dequeue

* амортизированно для List<T> при росте внутреннего массива.

Dictionary и HashSet используют хэш-таблицу: коллизии (одинаковый хэш у разных ключей) разрешаются цепочками или открытой адресацией. При плохом распределении хэшей производительность деградирует к O(n). Для пользовательских ключей переопределяйте GetHashCode/Equals или используйте IEqualityComparer<T>.

List<T> и T[]: массив фиксированного размера (или создаётся новый при Resize); список — обёртка с динамическим буфером и удобным API (Add, RemoveAt).

IEnumerable<T> — только перебор; IList<T> — индекс и изменение списка; IQueryable<T> — дерево выражений для трансляции запроса (EF, SQL) — см. LINQ.

---