Какие знаешь структуры данных в программировании?

Основные структуры данных в программировании

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

Линейные структуры данных

Массивы (Array)

Статическая структура фиксированного размера с прямым доступом по индексу:

int[] numbers = new int[5] { 1, 2, 3, 4, 5 };
Console.WriteLine(numbers[2]); // O(1) - константное время доступа

Списки (List<T>)

Динамические массивы с автоматическим увеличением емкости:

List<string> names = new List<string> { "Alice", "Bob" };
names.Add("Charlie"); // Амортизированная O(1)
names.Insert(1, "David"); // O(n) - требует сдвига элементов

Стек (Stack<T>)

LIFO (Last-In-First-Out) структура:

Stack<int> stack = new Stack<int>();
stack.Push(10); // Добавление на вершину
int top = stack.Pop(); // Удаление с вершины - O(1)

Очередь (Queue<T>)

FIFO (First-In-First-Out) структура:

Queue<string> queue = new Queue<string>();
queue.Enqueue("First"); // Добавление в конец
string first = queue.Dequeue(); // Удаление из начала - O(1)

Связные списки (LinkedList<T>)

Цепочка узлов, где каждый содержит данные и ссылки:

LinkedList<int> list = new LinkedList<int>();
list.AddLast(5); // Добавление в конец - O(1)
list.AddFirst(3); // Добавление в начало - O(1)

Ассоциативные структуры (словари)

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

Хеш-таблица для пар ключ-значение:

Dictionary<string, int> ages = new Dictionary<string, int>();
ages["Alice"] = 25; // Добавление - O(1) в среднем случае
int age = ages["Alice"]; // Поиск - O(1) в среднем случае

Отсортированный словарь (SortedDictionary<TKey, TValue>)

Балансированное бинарное дерево поиска (красно-черное дерево):

SortedDictionary<string, decimal> prices = new SortedDictionary<string, decimal>();
prices["Apple"] = 1.99m; // Добавление - O(log n)
prices["Banana"] = 0.99m; // Элементы хранятся отсортированными по ключу

Хеш-множество (HashSet<T>)

Коллекция уникальных элементов на основе хеш-таблицы:

HashSet<int> uniqueNumbers = new HashSet<int> { 1, 2, 3, 3, 4 };
Console.WriteLine(uniqueNumbers.Count); // 4 (дубликаты игнорируются)

Иерархические структуры

Деревья (Trees)

Рекурсивная структура с узлами и потомками. В .NET нет встроенной реализации, но часто создаются кастомные:

public class TreeNode<T>
{
    public T Data { get; set; }
    public List<TreeNode<T>> Children { get; } = new List<TreeNode<T>>();
}

// Бинарное дерево поиска (BST)
public class BinaryTreeNode<T> where T : IComparable<T>
{
    public T Value { get; set; }
    public BinaryTreeNode<T> Left { get; set; }
    public BinaryTreeNode<T> Right { get; set; }
}

Куча/Очередь с приоритетом (PriorityQueue<T>)

В .NET 6+ появилась встроенная реализация:

PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Task1", 3); // Приоритет 3 (низкий)
priorityQueue.Enqueue("Task2", 1); // Приоритет 1 (высокий)
string nextTask = priorityQueue.Dequeue(); // "Task2" - O(log n)

Графы (Graphs)

Структура из вершин и ребер, обычно реализуется кастомно:

public class Graph<T>
{
    private Dictionary<T, List<T>> adjacencyList = new Dictionary<T, List<T>>();
    
    public void AddVertex(T vertex) => adjacencyList[vertex] = new List<T>();
    public void AddEdge(T from, T to) => adjacencyList[from].Add(to);
}

Выбор структуры данных: ключевые критерии

• Время доступа: Массивы/O(1) vs Списки/O(n) для произвольного доступа
• Время вставки/удаления: Связные списки/O(1) vs Массивы/O(n)
• Память: Массивы более компактны, связные списки требуют доп. памяти на ссылки
• Упорядоченность: List сохраняет порядок, HashSet - нет
• Уникальность: HashSet гарантирует уникальность, List - нет
• Частые операции поиска: Dictionary/O(1) vs List/O(n)

Специализированные структуры в C#

• Immutable коллекции (System.Collections.Immutable): неизменяемые коллекции для многопоточности
• Concurrent коллекции (System.Collections.Concurrent): потокобезопасные реализации
• Memory<T>/Span<T>: для высокопроизводительной работы с памятью
• Record structs (C# 10): неизменяемые структуры данных по умолчанию

Правильный выбор структуры данных критически важен для производительности приложений. Например, для частых поисков по ключу Dictionary предпочтительнее List, а для LIFO/FIFO сценариев — Stack и Queue соответственно. В реальных проектах часто комбинируют несколько структур для достижения оптимальной эффективности.