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

EN: dynamic array

Массив с изменяемым размером, удваивающий выделенную ёмкость при заполнении и копирующий элементы в новый блок. Произвольный доступ — O(1); добавление в конец — O(1) амортизированно, потому что редкий resize O(n) компенсируется предшествующими дешёвыми добавлениями. Используется как базовая структура для Python list, Java ArrayList и C++ std::vector.