Как устроены массивы в программировании?

Массивы представляют собой упорядоченные коллекции элементов одного типа, хранящиеся в смежных (последовательных) ячейках памяти.

Основные характеристики:

• Индексация: Доступ к элементам осуществляется по индексу, начинающемуся с 0. Индекс указывает смещение от начала массива.
• Размер: Размер массива (количество элементов) фиксирован при его создании в статически типизированных языках или может динамически изменяться в языках с динамической типизацией (например, в Swift Array).
• Тип данных: Все элементы массива должны иметь один и тот же тип данных.
• Смежность: Хранение элементов в смежных ячейках памяти обеспечивает быстрый доступ к любому элементу по его индексу.

Операции:

• Доступ по индексу: O(1) - константное время.
• Добавление/удаление в конце: O(1) в среднем для динамических массивов (Swift Array).
• Добавление/удаление в начале или середине: O(n) - линейное время, так как может потребоваться сдвиг элементов.

Пример в Swift:

// Создание массива строк
var names: [String] = ["Alice", "Bob", "Charlie"]

// Доступ к элементу по индексу
let first_name = names[0] // "Alice"

// Добавление элемента
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Удаление элемента
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Итерация по массиву
for name in names {
    print(name)
}

Внутреннее устройство (для динамических массивов типа Swift Array):

Динамические массивы обычно реализуются поверх статически выделенного буфера памяти. При достижении емкости буфера выделяется новый, больший буфер, а старые элементы копируются (реаллокация). Это обеспечивает амортизированную O(1) для добавления в конец.