Массивы представляют собой упорядоченные коллекции элементов одного типа, хранящиеся в смежных (последовательных) ячейках памяти.
Основные характеристики:
- Индексация: Доступ к элементам осуществляется по индексу, начинающемуся с 0. Индекс указывает смещение от начала массива.
- Размер: Размер массива (количество элементов) фиксирован при его создании в статически типизированных языках или может динамически изменяться в языках с динамической типизацией (например, в Swift
Array).
- Тип данных: Все элементы массива должны иметь один и тот же тип данных.
- Смежность: Хранение элементов в смежных ячейках памяти обеспечивает быстрый доступ к любому элементу по его индексу.
Операции:
- Доступ по индексу: O(1) - константное время.
- Добавление/удаление в конце: O(1) в среднем для динамических массивов (Swift
Array).
- Добавление/удаление в начале или середине: O(n) - линейное время, так как может потребоваться сдвиг элементов.
Пример в Swift:
swift
Внутреннее устройство (для динамических массивов типа Swift Array):
Динамические массивы обычно реализуются поверх статически выделенного буфера памяти. При достижении емкости буфера выделяется новый, больший буфер, а старые элементы копируются (реаллокация). Это обеспечивает амортизированную O(1) для добавления в конец.