Динамический массив в C: пишем с нуля

Вы используете push() в JavaScript, append() в Python, add() в Java. Они кажутся мгновенными. Никогда не заканчивается место. Вы никогда о них не задумываетесь.

Это проблема — не потому что абстракции плохи, а потому что вы используете инструмент, не зная его цены. Каждый из этих методов основан на идеях, которые вы можете понять полностью. Эта статья покажет вам, как в C, где машина ничего от вас не скрывает.

К концу вы создадите рабочий динамический массив и, что важнее, ментальную модель, которая сделает std::vector, срезы Go и Vec из Rust очевидными.

Основная идея: два уровня памяти

Прежде чем писать код, поймите ключевую концепцию, которая делает динамический массив возможным.

Обычный массив — это фиксированный блок памяти. Вы объявляете int numbers[8], и компилятор выделяет ровно 32 байта на стеке. Если нужен девятый элемент — вы в тупике.

Динамический массив обходит это, располагаясь в куче — области памяти, которую программа может запрашивать и освобождать во время выполнения, любого размера, в любое время. Куча не освобождается автоматически при возврате из функции. Вы управляете ею. Это управление делает возможным изменение размера, но также и возможные ошибки памяти.

Динамический массив — это две сущности одновременно: блок целых чисел где-то в куче и небольшая управляющая структура, которая помнит, где этот блок находится, насколько он велик и сколько элементов в нём сейчас. Всё, что мы построим — это просто правильный учёт этих двух вещей.

Что нужно знать заранее

Память: стек и куча

Когда вы объявляете локальную переменную, она попадает на стек. Стек быстр и автоматичен — переменные появляются при вызове функции и исчезают при возврате.

void foo() {
    int x = 10;  // живёт на стеке
}
// x здесь уже нет

Куча работает иначе. Память там сохраняется, пока вы явно не освободите её. Вы запрашиваете у ОС блок, используете его и освобождаете, когда закончите. Это позволяет создавать структуры данных, которые переживают функцию, создавшую их.

Указатели

Указатель — это переменная, которая хранит адрес памяти, а не значение.

int score = 99;
int *ptr = &score;  // ptr хранит адрес score, а не 99

&score означает «дай мне адрес score». *ptr означает «перейди по этому адресу и прочитай, что там». Это обратные операции.

Почему это важно? Потому что, когда вы выделяете память в куче, вы получаете обратно адрес — указатель — на начало этой памяти. Другого способа ссылаться на динамическую память нет. Указатели — не причуда языка; это единственный инструмент для работы с динамическим выделением.

int *numbers = malloc(sizeof(int) * 8);
// numbers хранит адрес 32-байтового блока в куче
// numbers[0], numbers[1], ... numbers[7] — все допустимы

malloc возвращает указатель на выделенный блок. sizeof(int) даёт размер одного целого в байтах (обычно 4). Умножьте на 8 — получите 32 байта, место для 8 целых.

Структуры

В C нет классов. Для группировки связанных данных используется struct.

struct IntArray {
    int *data;      // указатель на целые числа в куче
    int length;     // сколько элементов сейчас хранится
    int capacity;   // сколько места выделено
};

typedef позволяет опускать ключевое слово struct при каждом использовании:

typedef struct {
    int *data;
    int length;
    int capacity;
} IntArray;

Теперь IntArray arr; допустимо вместо struct IntArray arr;. Мелочь, но упрощает код.

Оператор -> обращается к полю структуры через указатель:

array->length  // то же, что (*array).length

Вы будете постоянно использовать ->, потому что наши функции всегда получают указатель на структуру, а не саму структуру. Передача структуры по значению копировала бы все три поля каждый раз — расточительно, и изменения не были бы видны вызывающему.

Заголовочные файлы

#include <stdio.h>   // printf, scanf
#include <stdlib.h>  // malloc, realloc, free, exit
#include <stdbool.h> // bool, true, false

stdlib.h — критически важен. Все функции работы с памятью находятся там. Без него malloc и free не объявлены. stdbool.h существует, потому что в C изначально не было булева типа. Он даёт bool, true и false вместо int, 1 и 0.

Структура

Теперь, когда строительные блоки ясны, структура становится очевидной:

#define DEFAULT_CAPACITY 8

typedef struct {
    int *data;      // адрес нашего блока целых чисел в куче
    int length;     // текущее количество элементов (логический размер)
    int capacity;   // сколько элементов мы можем вместить (физический размер)
} IntArray;

length и capacity — не одно и то же. Это различие — сердце работы динамического массива.

capacity = 8  (в памяти существует 8 слотов)
length   = 3  (используются только 3)

[ 10 | 20 | 30 | __ | __ | __ | __ | __ ]
  [0]  [1]  [2]

Когда length == capacity, массив полон и должен расшириться перед следующим add.

#define DEFAULT_CAPACITY 8 — константа времени компиляции. Препроцессор заменяет каждое вхождение DEFAULT_CAPACITY на 8 до того, как компилятор увидит код. Это не переменная — у неё нет адреса и она не использует память во время выполнения.

Создание массива

IntArray* createArray(int capacity) {
    // Защита от бессмысленных входных данных
    if (capacity <= 0)
        capacity = DEFAULT_CAPACITY;

    // Выделяем управляющую структуру в куче
    // Здесь место для: одного указателя, двух int
    IntArray *array = malloc(sizeof(IntArray));
    if (array == NULL) {
        printf("Ошибка выделения памяти
");
        exit(EXIT_FAILURE);
    }

    // Выделяем блок целых чисел отдельно
    // Структура хранит только указатель на этот блок
    array->data = malloc(sizeof(int) * capacity);
    if (array->data == NULL) {
        printf("Ошибка выделения памяти
");
        free(array);  // не забываем освободить структуру
        exit(EXIT_FAILURE);
    }

    array->length = 0;
    array->capacity = capacity;

    return array;
}

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

Тип возвращаемого значения — IntArray* — указатель. Мы возвращаем не саму структуру, а её адрес. Это дескриптор, который вызывающий будет использовать для всех последующих операций.

Уничтожение массива

void destroyArray(IntArray *array) {
    free(array->data);  // сначала освобождаем блок целых чисел
    free(array);        // затем освобождаем структуру
}

Порядок важен. Сначала освободите блок данных, затем структуру. Если освободить структуру первой, array->data станет висячей ссылкой — вы будете обращаться к памяти через указатель на уже освобождённый объект.

Каждый malloc должен иметь ровно один соответствующий free. Это дисциплина, которой требует C. Современные языки имеют сборщики мусора, чтобы обеспечивать это автоматически. В C это ваша ответственность.

Получение и установка элементов

int get(IntArray *array, int index) {
    if (index < 0 || index >= array->length) {
        printf("Индекс вне границ
");
        exit(EXIT_FAILURE);
    }
    return array->data[index];
}

void set(IntArray *array, int index, int value) {
    if (index < 0 || index >= array->length) {
        printf("Индекс вне границ
");
        exit(EXIT_FAILURE);
    }
    array->data[index] = value;
}

Проверка границ не опциональна. Без неё array->data[index] при index >= length читает память, принадлежащую чему-то другому — возможно, другой переменной, возможно, ОС. C вас не остановит. Поведение не определено, что на практике означает тихое повреждение данных или трудноотслеживаемый сбой.

Обе операции выполняются за O(1), потому что array->data[index] напрямую вычисляется в адрес памяти: адрес = базовый_адрес + (индекс × sizeof(int)). Никакого поиска. Одна арифметическая операция.

Добавление элементов: сердце динамического массива

Это функция, к которой сводится всё остальное.

void add(IntArray *array, int value) {
    // Массив полон?
    if (array->length == array->capacity) {
        // Удваиваем ёмкость — почему, объясним ниже
        array->capacity *= 2;

        // Просим ОС изменить размер нашего блока целых чисел
        int *newData = realloc(array->data, sizeof(int) * array->capacity);

        // ВАЖНО: сохраняем во временный указатель, не в array->data
        // Если realloc не удастся, он вернёт NULL — если бы мы присвоили
        // сразу в array->data, то потеряли бы исходный указатель
        // и получили бы утечку памяти без возможности восстановления
        if (newData == NULL) {
            printf("Ошибка перераспределения памяти
");
            exit(EXIT_FAILURE);
        }

        // Обновляем только после успеха
        array->data = newData;
    }

    // Сохраняем значение и увеличиваем length в одном шаге
    array->data[array->length++] = value;
}

realloc — более умный брат malloc. Он принимает существующий указатель и новый размер. Если он может расширить блок на месте — делает это. Если нет — выделяет новый блок, копирует старые данные, освобождает старый блок и возвращает новый адрес. Существующие данные сохраняются в любом случае.

Почему удваивать ёмкость, а не увеличивать на 1? Если бы вы увеличивали на 1 каждый раз, когда массив заполняется, то каждое добавление вызывало бы realloc и копирование всех существующих элементов. Добавление n элементов стоило бы O(n²) суммарно.

Удвоение означает, что перераспределения происходят при размерах 4, 8, 16, 32, 64... Каждое перераспределение копирует все элементы, но количество копий на один элемент стремится к 2 по мере роста n. За много вставок средняя стоимость одного add составляет O(1). Это называется амортизированное константное время — дорого иногда, дёшево в среднем.

Удаление элементов

Удаление по индексу

void removeAt(IntArray *array, int index) {
    if (index < 0 || index >= array->length) {
        printf("Индекс вне границ
");
        exit(EXIT_FAILURE);
    }

    // Сдвигаем каждый элемент после удаляемого на одну позицию влево
    for (int i = index; i < array->length - 1; i++) {
        array->data[i] = array->data[i + 1];
    }

    // Последняя позиция всё ещё хранит старое значение, но мы
    // не стираем его — просто перестаём считать его частью массива
    array->length--;
}

Цикл идёт до array->length - 1, а не до array->length. На последней итерации i равно length - 2, и мы читаем array->data[length - 1]. Если бы цикл шёл до length, последняя итерация читала бы array->data[length], что находится за пределами выделенного блока.

Это O(n) в худшем случае — удаление с индекса 0 сдвигает все элементы.

Удаление по значению

bool removeValue(IntArray *array, int value) {
    for (int i = 0; i < array->length; i++) {
        if (array->data[i] == value) {
            removeAt(array, i);
            return true;  // удаляем только первое совпадение
        }
    }
    return false;  // значение не найдено
}

Линейный поиск, делегируем фактическое удаление removeAt. Возвращает false, если значение не найдено, чтобы вызывающий мог обнаружить промах.

Реверс массива

void reverse(IntArray *array) {
    int left = 0;
    int right = array->length - 1;

    while (left < right) {
        // Меняем местами элементы на позициях left и right
        int temp = array->data[left];
        array->data[left] = array->data[right];
        array->data[right] = temp;

        // Двигаем оба указателя к центру
        left++;
        right--;
    }
}

Техника двух указателей. Начинаем с противоположных концов, меняем местами, движемся к центру, останавливаемся, когда они встретятся. Время O(n), дополнительная память O(1) — не нужен второй массив. Условие left < right гарантирует, что для массива с нечётным количеством элементов средний элемент останется на месте.

Практический вывод

Теперь вы знаете, как работает динамический массив изнутри. Возьмите этот код и соберите его в своём редакторе. Поэкспериментируйте: добавьте 1000 элементов, замерьте количество вызовов realloc. Затем попробуйте изменить коэффициент роста с 2 на 1.5 — увидите, как меняется производительность. Напишите функцию shrinkToFit, которая уменьшает ёмкость до текущей длины. Это лучшее упражнение для закрепления материала.