Как выполнять вставку и удаление элемента в массиве?

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

Вставка

При наличии свободной ячейки элементы от последнего занятого до позиции k сдвигают вправо. Проход начинается с конца: a[i + 1] получает a[i]. После сдвига новое значение записывается в a[k], а логическая длина увеличивается на единицу.

Почему нельзя идти вперёд

Если копировать справа налево? Для вставки именно справа налево безопасно; прямой проход сначала запишет a[k + 1] значением a[k], затем возьмёт уже изменённую ячейку и размножит один элемент. Маленький массив из трёх разных чисел наглядно показывает повреждение.

Удаление

После удаления позиции k каждый следующий элемент сдвигают влево: a[i] получает a[i + 1]. Здесь проход, наоборот, идёт вперёд, потому что источник расположен правее назначения и ещё не затронут. Логическая длина уменьшается; значение в бывшей последней ячейке больше не относится к массиву.

Границы и ёмкость

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

Доказательство сдвига

Сформулируйте, какая часть хвоста уже перемещена и какие исходные значения ещё целы. Протрассируйте вставку в начало, конец и пустой массив, затем удаление единственного элемента. Такое доказательство объясняет не только результат, но и обязательное направление прохода.

Направление сдвига защищает ещё не перенесённые данные

При вставке элементы [index, size) сдвигают вправо от конца к началу. Если идти вперёд, первое присваивание затрёт значение, которое ещё требуется перенести. При удалении движение идёт слева направо, потому что источник расположен правее назначения.

def insert_at(buffer: list[int], size: int, index: int, value: int) -> int:
    if not 0 <= index <= size or size >= len(buffer):
        raise IndexError("no position or capacity")
    for position in range(size, index, -1):
        buffer[position] = buffer[position - 1]
    buffer[index] = value
    return size + 1

storage = [10, 20, 30, 0, 0]
size = insert_at(storage, 3, 1, 15)
assert storage[:size] == [10, 15, 20, 30]

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

Практика: симметричное удаление

Напишите delete_at, возвращающую удалённое значение и новый логический размер. После сдвига очистите ставшую свободной ячейку условным маркером. Проверьте удаление первого, среднего и последнего элементов, а также неверный индекс. Сформулируйте инвариант обоих циклов через уже перенесённый диапазон. Затем сравните со связным списком: при каких условиях список действительно удаляет за O(1), а когда поиск позиции всё равно стоит O(n)?