Массив, или array, — базовая структура данных: упорядоченная коллекция элементов, доступ к которым осуществляется по индексу. Понимание массивов важно не только для начинающих программистов, но и для тех, кто оптимизирует производительность или работает с памятью.
Коротко о сути
В простейшем виде массив хранит элементы подряд в памяти. Это обеспечивает быстрый доступ по индексу, поскольку адрес элемента вычисляется по формуле: базовый адрес плюс индекс, умноженный на размер элемента.
Типы массивов
- Статические — фиксированный размер, выделяемый при создании. Пример: массив в C.
- Динамические — размер можно менять во время выполнения. Часто реализуются как обёртка над статическим буфером с перераспределением памяти при переполнении.
- Связанные представления — массивы с дополнительными свойствами, например, циклические буферы или растущие массивы в языках высокого уровня.
Основные операции и их сложность
Ниже перечислены типичные операции и их амортизированная временная сложность для простого массива:
- Доступ по индексу: O(1).
- Поиск по значению (без сортировки): O(n).
- Вставка или удаление в конце (для динамического массива): O(1) амортизированно.
- Вставка или удаление в середине: O(n), так как требуется сдвиг элементов.
Как это выглядит в разных языках
Ниже примеры, которые показывают поведение массивов в распространённых языках.
C
int a[5]; // статический массив из 5 элементов
a[2] = 10; // быстрый доступ по индексу
Python
lst = [1, 2, 3] # списки Python — динамические массивы
lst.append(4) # амортизированная вставка в конец
lst.insert(1, 99) # вставка в середину требует сдвига
JavaScript
let arr = [1, 2, 3];
arr.push(4); // вставка в конец
arr.splice(1, 0, 99); // вставка в середину, O(n)
Многомерные массивы
Двух- или многомерные массивы обычно представляют как массив массивов. В языках с непрерывной памятью можно встретить «плоское» представление с вычислением индекса по формуле. Выбор зависит от требований к производительности и удобству доступа.
Подводные камни и практические советы
- Не храните в массиве элементы сильно разных типов, если это приводит к большой разнице в размере или дополнительным накладным расходам.
- При частых вставках и удалениях в середине подумайте о связных списках или деке, если нужно избежать сдвигов.
- Для больших данных учитывайте расположение в памяти, кэш-локальность сильно влияет на скорость.
- Если нужно часто расширять массив, резервируйте место заранее, чтобы сократить число перераспределений.
Когда использовать массив, а когда нет
Выбирайте массив, когда важен быстрый доступ по индексу и когда число элементов относительно предсказуемо. Если операции вставки и удаления в середине превалируют, лучше рассмотреть другие структуры.
Заключение
Массив выглядит просто, но это одна из самых универсальных и производительных структур. Понимание её внутренностей помогает принимать правильные архитектурные решения и писать более быстрый код. Начните с базовых примеров в вашем языке, а затем попробуйте измерить влияние разных подходов на реальных данных.