Определение

Хранит элементы данных на основе последовательного индекса, чаще всего с нулевой базой
В его основе лежат кортежи из теории множеств
Массив — одна из старейших и наиболее используемых структур данных

Что вам нужно знать

Массив оптимален для индексирования; плох для поиска, вставки и удаления (если не делать этого в самом конце массива)
Основная разновидность — линейные массивы, или одноразмерные
Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер
Динамические массивы подобны линейным, но в них зарезервировано пространство для дополнительных элементов
При заполнении динамического массива его содержимое копируется в массив большего размера
Двумерные массивы имеют два индекса x и y, как сетки или вложенные массивы

Эффективность («О» большое)

Индексирование: линейный массив — O(1), динамический массив — O(1)
Поиск: линейный массив — O(n), динамический массив — O(n)
Оптимизированный поиск: линейный массив — O(log n), динамический массив — O(log n)
Вставка: линейный массив — недопустимо, динамический массив — O(n)

Что такое массив?