Динамический массив: интерактивная анимация (Dynamic Array)

#include <stdio.h>
#include <stdlib.h>

// Структура, описывающая динамический массив
typedef struct {
    int* data;      // Указатель на начало блока памяти в куче
    int size;       // Текущее количество полезных элементов
    int capacity;   // Текущая вместимость (сколько ячеек выделено)
} DynamicArray;

// Инициализация пустого массива с начальной емкостью
void init(DynamicArray* arr, int initial_capacity) {
    arr->capacity = initial_capacity;
    arr->size = 0;
    // Выделяем непрерывный блок памяти под capacity элементов
    arr->data = (int*) malloc(arr->capacity * sizeof(int));
}

// Добавление элемента в конец (Push) - Амортизированная O(1)
void push(DynamicArray* arr, int value) {
    // 1. Проверяем, есть ли свободное место
    if (arr->size == arr->capacity) {
        // Места нет. Удваиваем емкость (стратегия роста x2)
        arr->capacity *= 2;

        // realloc делает три вещи:
        // 1) Пытается расширить текущий блок памяти
        // 2) Если не выходит - выделяет новый блок большего размера
        // 3) Копирует старые данные в новый блок и удаляет старый!
        arr->data = (int*) realloc(arr->data, arr->capacity * sizeof(int));
    }

    // 2. Добавляем элемент и сдвигаем границу полезных данных
    arr->data[arr->size] = value;
    arr->size++;
}

// Очистка памяти после использования (обязательно в C!)
void destroy(DynamicArray* arr) {
    free(arr->data);
    arr->data = NULL;
    arr->size = 0;
    arr->capacity = 0;
}

# В Python стандартный тип `list` под капотом реализован именно
# как динамический массив указателей (в CPython).
# Он сам управляет емкостью и перевыделением (рост примерно в 1.125 раз).

# Создаем пустой динамический массив
arr = []

# Добавление в конец (Append / Push) - Амортизированная O(1)
# Большую часть времени это работает мгновенно.
# Иногда Python останавливается, выделяет новый кусок памяти и копирует все элементы.
arr.append(42)
arr.append(15)

# Вставка в середину (Insert) - Строгая O(n)
# Python придется сдвинуть на один шаг вправо все элементы, начиная с нулевого,
# чтобы освободить ячейку под число 99. Чем ближе к началу вставка, тем больше сдвиг.
arr.insert(0, 99)

# Чтение и запись по индексу - Строгая O(1)
# Адрес нужной ячейки вычисляется мгновенно математически:
# Адрес_ячейки = Базовый_адрес + Индекс * Размер_элемента
val = arr[1]
arr[1] = 100

# Удаление из конца (Pop) - O(1)
# Обычно Python не уменьшает емкость массива при удалении
# сразу, чтобы избежать лишних аллокаций.
last = arr.pop()

// В JavaScript стандартный объект Array работает как динамический массив
// (хотя движки вроде V8 могут оптимизировать его по-разному в зависимости от типов).
let arr = [];

// Добавление элементов в конец (Push) - Амортизированная O(1)
// Движок JS (например, V8 в Chrome/Node) сам следит за длиной (length)
// и реальной емкостью (capacity) внутреннего C++ массива.
arr.push(42);
arr.push(15);

// Вставка элемента в начало (Unshift) - O(n)
// Метод unshift сдвигает все существующие элементы на один индекс вправо.
// Для большого массива это очень медленная операция!
arr.unshift(99);

// Удаление элемента из конца (Pop) - O(1)
// Просто отдает последний элемент и уменьшает length на 1.
let last = arr.pop();

// Доступ по индексу работает за O(1)
// Движок знает точное смещение в памяти, так как элементы (обычно) лежат непрерывно.
const firstElement = arr[0];