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

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

  1. ёмкость выделенной памяти (capacity)
  2. количество элементов в массиве (оsize)

При попытке добавить элемент в конец массива проверяется условие size < capacity.

Если оно истинно, то элемент просто добавляется на позицию, соответствующую началу массива плюс смещение на size.

Если ложно, происходит реаллокация: операционная система выделяет новый большой кусок памяти и в него копируются данные из старого куска, который затем освобождается.
время добавления элемента в конец массива
В среднем время добавления элемента в массив составляет O(1). Если выделенная память по массив закончится и произойдет реаллокация, то потребуется O(n) времени.
время добавления элемента в середину массива
В среднем и худшем случае время добавления элемента в массив составляет O(n), так как придется перемещать часть массива вправо.
Время работы остальных операций
В среднем и худшем случае время добавления элемента в массив составляет O(n), так как придется перемещать часть массива вправо.
Когда лучше использовать динамический массив
Динамический массив подходит в случаях, когда нужно сохранить последовательность в некотором порядке. Можно обращаться к элементам последовательности по номеру.
Добавлять и удалять элементы лучше только последние.

Ещё динамический массив можно использовать вместо хеш-таблицы в случае, если ключи представляют собой небольшие неотрицательные целые числа.