Динамическое изменение размера списков в различных языках программирования работает по-разному. 13

В некоторых языках (например, JavaScript, Lua) расширение массива происходит автоматически, когда делается попытка записи в несуществующую ячейку. 1

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

Команда увеличения размера массива, если новый размер не превышает ёмкости, просто изменяет счётчик длины массива до нужного размера. 1 С самим массивом никаких изменений при этом не происходит. 1 Команда увеличения размера, в которой новый размер превышает ёмкость, приводит к перемещению массива в памяти: 1

1. Выделяется новый фрагмент ОЗУ, размер которого превышает размер массива. 1
2. Содержимое массива копируется во вновь выделенную память. 1
3. Размер и ёмкость массива актуализируются. 1
4. В служебной структуре, хранящей параметры массива, значение указателя на данные меняется на новое. 1
5. Запускается команда освобождения ранее выделенного под массив фрагмента ОЗУ. 1

В языке C++ динамический массив используется в структуре vector. 4 Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в два раза при компиляции GNU C++ и в 1,5 раза при компиляции Microsoft Visual C++. 4 При удалении элементов уменьшение размера массива никогда не происходит. 4

В Java структура ArrayList основана на динамическом массиве. 4 При превышении максимального на данный момент размера происходит увеличение в 1,5 раза. 4