Массив в памяти и динамический массив

Массив хранит элементы одного размера в памяти подряд. Эти два простых свойства определяют и его силу, и слабость: доступ по индексу мгновенный, а вставка в середину дорогая. Динамический массив добавляет механизм роста, чтобы append оставался дешёвым.

Непрерывная память и индексация за O(1)

Если массив начинается с адреса 1000, а каждый элемент занимает 8 байт, то a[5] лежит по адресу 1000 + 5 * 8 = 1040. Формула не зависит от n, поэтому a[0] и a[10**6] читаются одинаково быстро. list в Python хранит не сами элементы, а ссылки на них, а ссылки одного размера, поэтому правило работает так же.

Вставка и удаление в середине: O(n)

Так как элементы лежат без промежутков, чтобы вставить в позицию i, нужно сдвинуть вправо каждый элемент справа. При удалении наоборот, влево. Число сдвигов равно n - i: вставка в начало — худший случай (n), в конец — лучший (0).

def insert_at(a, i, x):
    a.append(None)                   # make room at the end
    moves = 0
    for j in range(len(a) - 1, i, -1):
        a[j] = a[j - 1]              # shift one step right
        moves += 1
    a[i] = x
    return moves