Введение

Список – структура данных, в которую можно добавлять и удалять элементы.

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

Языковая поддержка

C++ std::vector и Rust std::vec::Vec являются реализациями динамических массивов, как и классы ArrayList, поставляемые с API Java и .NET Framework. Общий класс List<>, поставляемый с версией 2.0 .NET Framework, также реализован на основе динамических массивов. OrderedCollection в Smalltalk – это динамический массив с динамическим начальным и конечным индексом, что обеспечивает удаление первого элемента за O(1). Реализация типа данных списка в Python представляет собой динамический массив с законом роста: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76. Delphi и D реализуют динамические массивы непосредственно в ядре языка. В Ada пакет Ada.Containers.Vectors предоставляет реализацию динамического массива для заданного подтипа. Многие скриптовые языки, такие как Perl и Ruby, предлагают динамические массивы как встроенный примитивный тип данных. Ряд кроссплатформенных фреймворков предоставляют реализации динамических массивов для C, включая CFArray и CFMutableArray в Core Foundation, а также GArray и GPtrArray в GLib. Common Lisp обеспечивает базовую поддержку векторов изменяемого размера, позволяя настроить встроенный тип массива как изменяемый и использовать указатель заполнения для определения места вставки.