Динамический массив

Динамический массив (в Python это list) хранит данные в непрерывном буфере, который при заполнении заменяется на больший (обычно с коэффициентом роста ~2). За счёт удвоения добавление в конец стоит амортизированно O(1).

Сложность: доступ по индексу — O(1); append — амортизированно O(1); вставка/удаление в начало или середину — O(n). Память: O(n) плюс запас под рост.

a = []
for i in range(5):
    a.append(i)   # амортизированно O(1)
a.insert(0, -1)   # O(n): сдвиг всех элементов
print(a)          # [-1, 0, 1, 2, 3, 4]