Начнём с самой базовой структуры данных — той, которую вы наверняка уже использовали, но, возможно, никогда не задумывались, как она устроена изнутри.

Помните задачу из разведки? У вас есть массив оценок студента: 5, 3, 4, 5, 2. Нужно добавить ещё одну оценку в конец. Казалось бы — что тут сложного? Но если вы работаете с обычным массивом int[], код получается таким:

int[] grades = { 5, 3, 4, 5, 2 };

// Хотим добавить оценку 4 в конец — но массив уже заполнен!
int[] newGrades = new int[grades.Length + 1];

for (int i = 0; i < grades.Length; i++)
{
    newGrades[i] = grades[i];
}

newGrades[newGrades.Length - 1] = 4;
grades = newGrades;

Шесть строк ради одной оценки. Создаём новый массив побольше, копируем все старые элементы, вставляем новый. А если оценок не 5, а 500? Каждое добавление — полное копирование массива. Это медленно, громоздко и скучно. А что если нужно добавить 100 оценок подряд? Сто раз создаём новый массив и копируем всё содержимое — сначала 5 элементов, потом 6, потом 7... В итоге 5 + 6 + 7 + ... + 104 = больше 5000 операций копирования. Для сотни вставок. Именно эту проблему решают динамические массивы — List<T> в C#. Но прежде чем к ним перейти, разберёмся, как вообще устроен массив изнутри.

Представьте спортивную раздевалку. Ряд пронумерованных шкафчиков: 0, 1, 2, 3, 4. Все одного размера, стоят вплотную друг к другу. Вы знаете номер шкафчика — подходите и открываете его за секунду. Не нужно проверять все подряд: третий шкафчик — это третий шкафчик, он всегда на одном месте. Не нужно спрашивать у охранника, не нужно обходить все предыдущие. Знаете номер — знаете, где искать.

Но есть ограничение: шкафчиков ровно столько, сколько установили при строительстве. Хотите ещё один? Придётся сносить весь ряд и строить заново — длиннее.

Массив в памяти компьютера работает точно так же.

Три ключевых свойства в этом определении. Фиксированное количество — размер задаётся один раз при создании и больше не меняется. Одного типа — нельзя смешать целые числа и строки в одном массиве (в C# точно нельзя). Непрерывный блок памяти — элементы лежат один за другим, без промежутков, без пропусков.

Именно непрерывность даёт массиву его суперспособность. Компьютер знает адрес первого элемента и размер каждого. Чтобы найти элемент с индексом i, он делает простую арифметику:

адрес_элемента = начальный_адрес + i * размер_элемента

Никакого перебора, никакого поиска — одно умножение и одно сложение. Именно поэтому доступ к элементу по индексу занимает O(1) — константное время, независимо от размера массива. Неважно, 10 элементов или 10 миллионов — третий элемент находится мгновенно. Это как найти дом по адресу на карте: вы не обходите все дома на улице, а сразу идёте к нужному номеру.

На схеме видно: каждый int занимает 4 байта, ячейки идут подряд. Чтобы найти grades[3], компьютер берёт адрес начала 0x100, прибавляет 3 * 4 = 12 и попадает ровно в 0x10C. Никуда ходить не надо — чистая математика. В C# статический массив создаётся через оператор new с указанием размера. Вот два способа:

// Способ 1: создаём пустой массив, потом заполняем
int[] scores = new int[5];
scores[0] = 95;
scores[1] = 82;
scores[2] = 74;
scores[3] = 91;
scores[4] = 88;

// Способ 2: сразу с инициализацией
int[] scores = { 95, 82, 74, 91, 88 };

В первом случае массив создаётся на 5 ячеек, каждая по умолчанию равна 0 (для int). Потом мы вручную заполняем каждую. Второй способ — короче и удобнее, когда значения известны заранее. Компилятор сам определяет размер массива по количеству элементов в фигурных скобках.

Работать с элементами просто — обращаемся по индексу в квадратных скобках:

int[] scores = { 95, 82, 74, 91, 88 };

Console.WriteLine(scores[0]);       // 95 — первый элемент
Console.WriteLine(scores[4]);       // 88 — последний
Console.WriteLine(scores.Length);   // 5 — количество элементов

// Изменение элемента
scores[2] = 100;
Console.WriteLine(scores[2]);       // 100

Свойство Length возвращает количество элементов. Обратите внимание: индексы начинаются с 0, поэтому в массиве из 5 элементов последний — scores[4], а не scores[5]. Это не причуда C# — так устроено во всех языках, унаследовавших индексацию от C. Причина как раз в формуле адреса: первый элемент смещён на 0 позиций от начала, второй — на 1, и так далее.

А что будет, если попросить scores[5]?

Console.WriteLine(scores[5]);  // IndexOutOfRangeException!

Бум! Программа падает с ошибкой IndexOutOfRangeException. C# строго проверяет границы массива — выйти за пределы не даст. И это хорошо: лучше упасть сразу и увидеть ошибку, чем прочитать мусор из чужой памяти и потом часами искать, откуда в программе взялось число 847291638 (привет, C и C++, где такое запросто).

Теперь про сложность операций. Доступ по индексу — O(1), это мы уже разобрали. А что с остальным?

Поиск элемента. Если нужно выяснить, есть ли в массиве оценка 74, придётся пройтись по всем элементам. Массив не отсортирован, данные никак не упорядочены — нет способа угадать, где лежит нужное значение:

int[] scores = { 95, 82, 74, 91, 88 };

bool found = false;
for (int i = 0; i < scores.Length; i++)
{
    if (scores[i] == 74)
    {
        found = true;
        break;  // Нашли — можно не продолжать
    }
}
// В лучшем случае — первый элемент, в худшем — последний

В лучшем случае нужный элемент окажется первым — повезло. В худшем — последним или его вообще нет, и мы проверим все n элементов. Средний случай — n/2 проверок. Всё это O(n).

Вставка в середину — тоже O(n). Допустим, нужно вставить оценку 77 на позицию 2. Все элементы правее должны сдвинуться на одну позицию вправо, чтобы освободить место. А если массив заполнен — сначала нужно создать новый побольше, скопировать элементы, и уже потом сдвигать.

Удаление — зеркальная ситуация. Удалили элемент из середины — образовалась «дыра». Все элементы правее нужно сдвинуть влево, чтобы её закрыть. Снова O(n).

Итого для статического массива:

// Сложность операций статического массива
// Доступ по индексу:   O(1)  — мгновенно
// Изменение элемента:  O(1)  — мгновенно (знаем адрес)
// Поиск элемента:      O(n)  — линейный перебор
// Вставка:             O(n)  — сдвиг + возможно копирование
// Удаление:            O(n)  — сдвиг элементов

Видите картину? Доступ — шикарный, всё остальное — медленное. Для задач, где размер коллекции заранее известен и не меняется, это идеально. Дни недели — их ровно 7, и это не изменится. Месяцы — 12. RGB-каналы пикселя — 3. Но если данные приходят постепенно (оценки студентов, заказы в магазине, логи сервера, сообщения в чате), фиксированный массив становится обузой. Каждое добавление — создание нового массива и полное копирование. И вот тут появляется идея, простая и элегантная: а что если выделять массив с запасом?

Допустим, нам нужно хранить 3 элемента. Вместо массива на 3 ячейки выделяем на 4. Добавляем четвёртый — массив заполнился. Что делаем? Создаём новый массив вдвое больше (на 8 ячеек), копируем старые элементы и продолжаем работать. Следующее расширение будет на 16, потом на 32, и так далее. Каждый раз удваиваем.

Да, одно конкретное добавление, которое вызывает расширение, стоит O(n) — нужно скопировать все элементы в новый массив. Но вот в чём фокус: расширение происходит всё реже и реже. После удвоения до 8 ячеек — следующие 4 добавления пройдут мгновенно. После удвоения до 16 — следующие 8 добавлений бесплатны. После удвоения до 1024 — целых 512 добавлений без копирования.

Если посчитать среднюю стоимость добавления на длинной дистанции, получается амортизированное O(1) — как будто каждая вставка стоит одинаково мало.

Представьте, что вы кладёте монетки в копилку. 99 раз просто бросаете монетку — мгновенно. На сотый раз копилка полная — вы пересыпаете всё в банку побольше. Долго? Да. Но если разделить общее время на 100 операций, каждая «стоила» почти ничего. Амортизация — это усреднение: редкие дорогие операции «размазываются» по множеству дешёвых.

В C# динамический массив — это List<T>, где T — тип элементов. Вот как решается задача из разведки:

List<int> grades = new List<int> { 5, 3, 4, 5, 2 };

grades.Add(4);  // Готово. Одна строка.

Console.WriteLine(grades.Count);  // 6
Console.WriteLine(grades[5]);     // 4

Сравните с шестью строками копирования из начала урока. List<T> сам заботится о расширении — вы просто вызываете Add и не думаете о размерах. Внутри List<T> лежит обычный массив, но список управляет им за вас: следит за заполненностью, расширяет когда нужно, копирует данные.

Вот основные операции List<T> на примере списка игроков:

List<string> playerNames = new List<string>();

// Добавление в конец — амортизированное O(1)
playerNames.Add("Алиса");
playerNames.Add("Борис");
playerNames.Add("Вера");

// Доступ по индексу — O(1), как у обычного массива
Console.WriteLine(playerNames[1]);  // Борис

// Количество элементов
Console.WriteLine(playerNames.Count);  // 3

// Вставка по индексу — O(n), элементы правее сдвигаются
playerNames.Insert(1, "Глеб");
// Теперь: Алиса, Глеб, Борис, Вера

// Удаление — O(n), элементы сдвигаются
playerNames.Remove("Борис");
// Теперь: Алиса, Глеб, Вера

// Проверка наличия — O(n)
bool hasVera = playerNames.Contains("Вера");  // true

Обратите внимание на важное отличие: у массива — свойство Length, у списка — Count. Не путайте, это частый источник ошибок у новичков.

А ещё у List<T> есть свойство Capacity — сколько ячеек выделено «под капотом» внутреннего массива. Count — сколько элементов реально хранится. Count всегда меньше или равен Capacity. Посмотрим, как они меняются:

List<int> numbers = new List<int>();
Console.WriteLine($"Count: {numbers.Count}, Capacity: {numbers.Capacity}");
// Count: 0, Capacity: 0

numbers.Add(1);
Console.WriteLine($"Count: {numbers.Count}, Capacity: {numbers.Capacity}");
// Count: 1, Capacity: 4  (начальная ёмкость)

numbers.Add(2);
numbers.Add(3);
numbers.Add(4);
Console.WriteLine($"Count: {numbers.Count}, Capacity: {numbers.Capacity}");
// Count: 4, Capacity: 4  (заполнено под завязку)

numbers.Add(5);  // Пятый элемент — расширение!
Console.WriteLine($"Count: {numbers.Count}, Capacity: {numbers.Capacity}");
// Count: 5, Capacity: 8  (ёмкость удвоилась)

Видите? Первое добавление сразу выделило массив на 4 ячейки. Четыре элемента помещаются свободно. Но пятый уже не влезает — List<T> создаёт новый массив на 8 ячеек, копирует туда первые четыре и добавляет пятый. Следующее расширение будет на 16, потом 32, и так далее. Всё прозрачно — вы этого не видите в обычном коде, но понимать полезно, особенно когда работаете с большими объёмами данных.

Кстати, если вы заранее знаете примерное количество элементов, можно подсказать списку начальную ёмкость и избежать лишних расширений:

// Ожидаем около 1000 заказов — сразу выделяем место
List<double> orderPrices = new List<double>(1000);

Это не ограничивает список — он всё равно расширится, если элементов окажется больше. Но первые 1000 добавлений пройдут без единого копирования. Окей, когда что использовать? Сведём все сложности в одну таблицу:

* Для int[] добавление — это создание нового массива и полное копирование, отсюда O(n).

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

А что с памятью? List<T> расходует её чуть больше, чем массив: внутренний массив выделяется с запасом, и часть ячеек пустует. В худшем случае — почти половина ёмкости не используется (сразу после удвоения). Но на практике этот перерасход мизерный. Миллион int — это 4 мегабайта. Даже с двойным запасом — 8 мегабайт. На фоне гигабайтов оперативной памяти современных машин — капля в море.

Массив (Array) — структура данных, которая хранит фиксированное количество элементов одного типа в непрерывном блоке памяти. Доступ по индексу — O(1), потому что адрес элемента вычисляется арифметически: начало + индекс * размер.

Статический массив (int[] в C#) — массив фиксированного размера. Задаётся при создании и не меняется. Добавление и удаление элементов требует создания нового массива и копирования данных — O(n).

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

Амортизированная сложность — средняя стоимость операции на большом количестве вызовов. Отдельное расширение стоит O(n), но оно происходит всё реже, и в среднем каждое добавление обходится в O(1).

У массива — свойство Length, у List<T> — Count (текущее количество элементов) и Capacity (выделенная ёмкость внутреннего массива).

Правило выбора: List<T> по умолчанию, int[] — только когда размер точно известен и фиксирован.