Что такое массив и как он устроен

В языках программирования информация представлена разными типами данных: целые числа, числа с плавающей точкой, символы, строки, булевы значения и так далее. Благодаря этому компьютер понимает, как хранить информацию и что с ней делать.

Но есть и более сложные сущности, которые называются структурами данных. Они содержат данные, которые, как правило, связаны определённым образом. Одна из таких структур — массивы.

В этой статье мы расскажем, что такое массивы и зачем они нужны. Если же вы хотите научиться работать с ними в коде, почитайте материалы про массивы в C++ и в Java.

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

Массив в программировании — это структура данных, которая хранит упорядоченный набор однотипных элементов. Его можно представить в виде шкафчика или камеры хранения на вокзале или в магазине: набор ячеек, в каждой из которых может что-то лежать.

Как и в шкафчике, каждая ячейка массива пронумерована, номер — это её индекс. Причём счёт идёт не от единицы, а от нуля.

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

При этом в разных языках программирования их могут называть по-разному и даже предлагать несколько реализаций. Например, в Python это lists (списки) и tuples (кортежи), в C++ — arrays (массивы) и vectors (векторы). Всё это массивы, но разных видов.

Для чего нужны массивы

Представьте: мы пишем программу, в которой будет храниться температура окружающей среды по дням за декабрь. Если не использовать массивы, для каждого значения температуры придётся создавать свою переменную.

Эта информация хранится разрозненно, и переменные никак не связаны друг с другом. Если мы захотим посчитать среднюю температуру за декабрь, придётся писать длинную формулу:

А если вдруг окажется, что термометр даёт ошибку в +3 градуса? Чтобы исправить ошибку, придётся вручную отнимать от каждой переменной 3 — и так для каждой из 31 строки кода.

Или, допустим, мы захотим учитывать температуру не только в нашем городе, но и в соседнем. Тогда в названии каждой переменной нужно будет дополнительно указывать не только дату, но и название города — так и запутаться можно.

Гораздо проще пойти другим путём: создать массив «Декабрь» и записывать температуру уже внутри него.

Так программа понимает, что эти элементы связаны между собой. Теперь мы за пару строчек кода можем найти среднемесячную температуру — достаточно сказать программе: сложи все элементы и раздели их на длину массива. Или прибавить три градуса (сказать: прибавь 3 к каждому элементу).

Если захотим измерять температуру в другом городе, можно просто создать другой массив — и их значения точно не перемешаются.

При этом обратиться к температуре любого — легче лёгкого, ведь каждый элемент имеет свой индекс, как номер ячейки в камере хранения. Нужно лишь запомнить, что нумерация обычно идёт от нуля.

Данные хранятся более упорядоченно, нет никакого нагромождения из десятков и сотен переменных, которые нужно держать в голове, чтобы не запутаться и не ошибиться.

В некоторых массивах можно хранить даже другие массивы. Например, мы можем объявить переменную Город_N_2022 и положить в неё массивы каждого из месяцев.

Массивы — очень полезный инструмент, о котором нередко спрашивают на собеседованиях. В разных языках программирования с ними можно совершать множество разных операций. Например, в PHP есть 13 способов для одной только сортировки массивов.

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

Память в компьютере поделена на ячейки — фрагменты информации, которые имеют свой адрес. Можно сказать, это такой супермассив для всех данных внутри машины.

При создании массива компьютер выделяет непрерывный участок памяти и складывает в него элементы один за другим. Рассмотрим этот процесс подробнее.

Как резервируется память

Когда мы объявляем классический массив, мы также указываем его длину (сколько в нём будет элементов) и тип данных, которые будут в нём храниться. В случае массива «Декабрь» длина будет равна 31, а тип данных — float (число с плавающей запятой — мы всё-таки температуру записываем).

Так как все элементы принадлежат одному типу, они занимают одинаковый объём памяти. Допустим, в нашей архитектуре числа с плавающей запятой весят 4 байта. Компьютер умножает вес одного элемента на длину списка и получает количество памяти, которое ему нужно зарезервировать:

4 * 31 = 124 байта

И вот эти 124 соседних байта резервируются под массив «Декабрь». А до и после них в памяти могут быть какие угодно данные.

Как работает обращение по индексу

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

Для этого он определяет начальный адрес массива. Это адрес ячейки памяти, с которой начинается массив. Если он будет 54921, то память компьютера будет выглядеть следующим образом.

Извлечь из такой структуры элемент с нужным индексом несложно. Это делается по следующей формуле:

Для наглядности подставим в эту формулу несколько индексов.

Индекс 0: 54921 + 0 * 4 = 54921 + 0 = 54921

Индекс 1: 54921 + 1 * 4 = 54921 + 4 = 54925

Индекс 2: 54921 + 2 * 4 = 54921 + 8 = 54929

За каждый индекс после нуля адрес ячейки смещается на 4, потому что именно столько весит каждый элемент массива. А если индекс равен нулю, смещения нет. Именно поэтому индексы считают с нуля, а не с единицы.

Теперь становится понятно, почему для классических массивов нужно заранее указывать тип данных и количество элементов:

• Если компьютер не знает тип данных, то он не понимает, сколько памяти нужно выделять под каждый элемент и на сколько ячеек смещаться при поиске элемента по индексу.
• Если компьютер не знает длину массива, то он не понимает, сколько памяти нужно под него выделить.

Виды массивов

Классический массив понятен, предсказуем, занимает мало места и быстро работает, но и возможности его применения ограничены. Чтобы массивы были более гибкими и подходили под разные задачи, в некоторых языках программирования придумали их более сложные реализации.

Статические и динамические

Длина статического массива определена заранее. При его создании программист сразу пишет, сколько в массиве будет элементов. Если положить в него меньше элементов, чем объявлено, то в остальных будут находиться пустые значения.

Это удобно, когда программист сразу знает, сколько элементов ему нужно. Если он записывает среднесуточную температуру за каждый день в декабре, то понадобится 31 элемент, если буквы русского алфавита — 33 элемента.

Длина динамических массивов, напротив, может изменяться во время выполнения программы. Например, программа должна хранить оценки школьника по информатике. Учитель ставит новую оценку — в массив добавляется новый элемент. Так это выглядит со стороны.

На самом деле при добавлении нового элемента компьютер создаёт новый массив, в который копирует старые элементы и добавляет новые. Старый массив при этом удаляется.

Так что по сути динамический массив — это тот же статический, но способный пересоздаваться с другой длиной.

Часто компьютер резервирует под динамические массивы немного больше места, чем нужно при создании. Он делает это для того, чтобы не пришлось пересоздавать массив, когда в него добавляют всего один или два новых элемента.

Однородные и гетерогенные

Однородные массивы состоят из элементов одинакового типа данных. Например, только целые числа или только строки. Хранить элементы разных типов в них нельзя.

В гетерогенных массивах одним элементом может быть целое число, другим — строка, третьим — вообще другой массив. Часто это может быть удобно, но среднее арифметическое всех его элементов, конечно, не посчитаешь. И ладно, если программа выдаст ошибку, — а если действительно решит посчитать и выведет результат?

На самом деле гетерогенные массивы хранят в себе не сами данные, а ссылку на них. Например, питоновский список может выглядеть так: [1, 'строка', False]. Но внутреннее его устройство сложнее: [ссылка на 1, ссылка на 'строка', ссылка на False]. А сами данные хранятся где-то ещё в разрозненном виде, никак не связанные друг с другом.

Получается, с технической точки зрения гетерогенный массив практически не отличается от гомогенного. Он тоже хранит в себе один тип данных — ссылочный.

Одномерные и многомерные

Одномерный массив — это ряд пронумерованных элементов. Они, как вагоны поезда, следуют друг за другом, и к ним можно обратиться по номеру: первый, второй, третий, десятый.

Двумерный массив — несколько рядов элементов. Его можно представить как таблицу, в которой есть строки и столбцы, а сами элементы находятся на их пересечении. Соответственно, индекс такого массива состоит из двух чисел: номера ряда (столбца) и номера элемента в этом ряду.

С точки зрения реализации он представляет собой массив, в котором лежат одномерные массивы.

Также бывают массивы трёхмерные, четырёхмерные, пятимерные и так далее. Чем больше измерений, тем сложнее структура и тем из большего количества чисел состоят индексы элементов.

Итоги

• Массив — это структура данных фиксированной длины для хранения упорядоченного набора элементов. Элементы при этом должны относиться к одному типу данных.
• Элементы массива физически хранятся в соседних ячейках памяти. К каждому из них можно обратиться по индексу.
• У массива может быть более сложная реализация в зависимости от языка программирования. Длину динамического можно изменять, гетерогенные могут хранить ссылки на разные типы данных, а в многомерных каждый элемент имеет сразу несколько индексов.