Массив — одна из самых привычных и полезных структур данных. Под этим словом обычно понимают упорядоченное множество элементов одного или разных типов, доступ к которым осуществляется по индексу. На практике массивы встречаются повсюду: в базах данных, интерфейсах, алгоритмах и в самом железе компьютера.
Почему массивы важны
Главное преимущество — предсказуемость доступа к элементу. В большинстве реализаций чтение или запись по индексу выполняются за постоянное время. Это делает массивы удобными для хранения коллекций, когда важно быстро получить значение по позиции.
Ключевые характеристики
- Память: элементы обычно размещаются подряд в оперативной памяти. Это даёт хорошую локальность и экономию места на служебные структуры.
- Доступ по индексу: прямой доступ к любому элементу обеспечивает высокую скорость операций чтения и записи.
- Размер: в статических массивах размер фиксирован; в динамических — он может изменяться, но при расширении часто требуется копирование всех элементов в новый блок памяти.
- Типизация: в языках с явными типами массивы могут быть строго типизированы; в языках с динамической типизацией элементы могут иметь разные типы.
Основные операции и их сложность
- Доступ по индексу: O(1).
- Поиск (линейный): O(n). Если элементы отсортированы, можно использовать двоичный поиск: O(log n).
- Вставка или удаление в конце динамического массива: амортизированно O(1). Вставка/удаление в середине или в начале: O(n) из‑за сдвига элементов.
- Копирование массива: O(n).
Виды массивов
- Статические массивы: выделение фиксированного блока памяти при создании. Примеры: массивы в C.
- Динамические массивы: размер может увеличиваться. Примеры: std::vector в C++, ArrayList в Java.
- Многомерные массивы: таблицы, матрицы. Внутренне это часто один непрерывный блок с вычислением смещений по формулам.
- Срезы и представления: в некоторых языках срезы представляют часть массива без копирования, например в Go или Python.
- Типизированные массивы: используются для быстрой работы с бинарными данными, например TypedArray в JavaScript или массивы в NumPy.
Когда массив не лучший выбор
Если требуется частая вставка и удаление в середине коллекции, лучше рассмотреть списки или деревья. Для быстрого поиска по ключу предпочтительнее хеш-таблицы. Если важна устойчивость к частым перераспределениям памяти, есть смысл выбрать структуры с более гибким доступом к элементам.
Примеры кода
Короткие примеры показывают, как выглядят массивы в разных языках.
// JavaScript
let a = [1, 2, 3];
a.push(4); // добавление в конец
let x = a[2]; // доступ по индексу
# Python
a = [1, 2, 3]
a.append(4)
x = a[2]
/* C */
int a[3] = {1, 2, 3};
int x = a[1];
Практические советы
- Планируйте размер: если известен приблизительный объём данных, выделите его сразу, чтобы уменьшить число перераспределений.
- Избегайте лишних копий: срезы и представления помогают работать с частями массива без копирования данных.
- Пользуйтесь типизированными массивами для числовых расчётов: они быстрее и экономнее по памяти.
- Внимательно обрабатывайте границы массива, чтобы избежать ошибок выхода за пределы и атак, связанных с переполнением.
Короткий итог
Массив — это простая и эффективная структура для хранения упорядоченных данных с быстрым доступом по индексу. Она незаменима там, где важна скорость чтения и компактность хранения. При выборе между массивом и другой структурой данных ориентируйтесь на характер операций: чтение и случайный доступ — в пользу массива; частые вставки и удаления — скорее нет.