Алгоритмы и структуры данных на C#: полное руководство для разработчика

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

Введение в алгоритмы и структуры данных на C#

Алгоритмы и структуры данных — это фундамент, на котором строится любое качественное программное обеспечение. В экосистеме .NET и языка C# понимание этих концепций позволяет не только писать более эффективный код, но и грамотно выбирать инструменты из богатой стандартной библиотеки (BCL — Base Class Library). От выбора структуры данных зависит скорость работы приложения, потребление памяти и, в конечном итоге, пользовательский опыт.

В этой статье мы разберём ключевые структуры данных и алгоритмы, которые должен знать каждый C#-разработчик. Мы рассмотрим их реализацию, особенности производительности (Big O нотация) и практические примеры кода. Статья подойдёт как начинающим, так и опытным программистам, желающим систематизировать знания.

Основные структуры данных в C#

Массивы и списки (Array vs List)

Массив (Array) — это фиксированная структура данных, хранящая элементы одного типа в непрерывной области памяти. Доступ по индексу происходит за O(1), но вставка и удаление элементов (кроме конца) требуют O(n) из-за сдвига.

int[] numbers = new int[5] { 10, 20, 30, 40, 50 };
Console.WriteLine(numbers[2]); // 30

List<T> — это динамический массив. Он автоматически увеличивает свою ёмкость при добавлении элементов. Внутри используется массив, поэтому скорость доступа по индексу также O(1). Однако вставка в середину или начало — O(n).

List<string> names = new List<string>() { "Анна", "Борис" };
names.Add("Виктор");
names.Insert(1, "Глеб"); // O(n)
Console.WriteLine(names[0]); // Анна

Стек и очередь (Stack и Queue)

Stack<T> (стек) работает по принципу LIFO (Last In, First Out). Используется для алгоритмов обхода, разбора выражений, управления вызовами.

Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
int top = stack.Pop(); // 3

Queue<T> (очередь) работает по принципу FIFO (First In, First Out). Применяется в системах обработки задач, буферизации данных.

Queue<string> queue = new Queue<string>();
queue.Enqueue("Задача 1");
queue.Enqueue("Задача 2");
string next = queue.Dequeue(); // "Задача 1"

Обе структуры реализованы на основе массива (циклический буфер) и обеспечивают операции вставки и удаления за O(1) в среднем.

Словарь (Dictionary)

Dictionary<TKey, TValue> — это хеш-таблица. Она обеспечивает поиск, вставку и удаление элементов по ключу за O(1) в среднем (при хорошей хеш-функции). Это одна из самых часто используемых структур данных в C#.

Dictionary<string, int> ages = new Dictionary<string, int>();
ages["Алиса"] = 30;
ages["Боб"] = 25;

if (ages.ContainsKey("Алиса"))
{
    Console.WriteLine(ages["Алиса"]); // 30
}

Важно: Ключи в Dictionary должны быть уникальными и реализовывать интерфейс IEquatable<T> или иметь корректно переопределённые GetHashCode() и Equals().

Связный список (LinkedList)

LinkedList<T> — это двусвязный список. В отличие от List, вставка и удаление в середину списка выполняется за O(1) (если у вас есть ссылка на узел). Однако доступ по индексу — O(n). Используется реже, но незаменим для очередей с двусторонним доступом и LRU-кешей.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.AddFirst(0);

LinkedListNode<int> node = list.Find(1);
list.AddAfter(node, 10); // O(1)

Алгоритмы сортировки и поиска на C#

Быстрая сортировка (QuickSort)

QuickSort — один из самых эффективных алгоритмов сортировки общего назначения. Средняя временная сложность — O(n log n), худшая — O(n²). В .NET встроенная сортировка (Array.Sort) использует интроспективную сортировку (гибрид QuickSort, HeapSort и InsertionSort).

public static void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivotIndex = Partition(arr, left, right);
        QuickSort(arr, left, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, right);
    }
}

private static int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]); // swap
        }
    }
    (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
    return i + 1;
}

Бинарный поиск (Binary Search)

Бинарный поиск работает только на отсортированных массивах. Временная сложность — O(log n). В .NET есть встроенный метод Array.BinarySearch.

int[] sortedNumbers = { 1, 3, 5, 7, 9, 11 };
int target = 7;
int index = Array.BinarySearch(sortedNumbers, target);

if (index >= 0)
    Console.WriteLine($"Элемент найден на индексе {index}");
else
    Console.WriteLine("Элемент не найден");