Массивы (Arrays)

Массивы - это структура данных для хранения элементов. Элементами могут быть целые числа, строки, объекты и т.д. Все элементы хранятся непрерывно, т.е. в соседних участках памяти. Если понадобится добавить новый элемент в массив, а места под него рядом не окажется, то придётся запросить другой блок памяти.

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

Создание массива

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

Если создать массив, который может содержать 15 элементов, то при получении 16-го нужно будет создавать новый массив. При этом не стоит создавать массив, например, на 1 000 000 элементов, так сказать с запасом. Причина этого в том, что он будет занимать много места в памяти. Ведь память резервируется для хранения 1 000 000 элементов, даже если по факту элементов будет всего 15. И эту память нельзя будет использовать для чего-то другого.

Доступ к элементам массива

Есть две самые примитивные операции с массивами - это запись элементов в массив и чтение - получение значения элемента из массива. Все остальные операции с массивами построены на основе этих двух.

Поместить элемент в массив можно в любое из зарезервированных мест. Каждое из них идентифицируется с помощью индекса - положительного числового значения. Стоит запомнить, что самый первый элемент в массиве имеет индекс 0, а далее в порядке возрастания. Таким образом, если массив состоит из 15 элементов, то последним индексом будет 14.

Мы можем обратиться к определённому элементу по его индексу и тогда получим информацию о нём - его значение.

Для помещения большого количества элементов в массив или для получения информации о них используется цикл.

Ёмкость и длина массива

Ёмкость массива - это количество элементов, которое можно поместить в массив. Это то самое значение, которое указывается при создании массива. И это значение нельзя изменить. Если же ёмкость массива исчерпана, но нам нужно записать ещё один элемент, то придётся создать новый массив с большей ёмкостью и переместить в него все существующие элементы вместе с новым.

Длина массива - это количество элементов, непосредственно находящихся в массиве.

Несмотря на то, что ёмкость и длина массива - это разные понятия, а их значения могут отличаться, в различных задачах может встречаться такое, когда методу в качестве параметра передаётся массив без указания этих значений. В этом случае предполагается, что длина == ёмкость.

Вставка элемента в массив

Вставку элементов в массив можно разделить на 3 вида:

• вставка элемента в конец массива
• вставка элемента в начало массива
• вставка элемента по заданному индексу

Для вставки элемента в конец массива нам нужно знать его длину и ёмкость. Любой язык программирования позволяет в любое время узнать эти значения. Если ёмкость массива позволяет добавить новый элемент, то нам достаточно вставить новый элемент по последнему индексу. В противном случае нам потребуется создать новый массив с ёмкостью, достаточной для добавления нового массива, и переместить в него все элементы из старого массива и добавить новый.

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

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

Удаление элемента из массива

Также как и вставку, удаление элемента из массива можно разделить на 3 вида:

• удаление последнего элемента массива
• удаление первого элемента массива
• удаление элемента по заданному индексу

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

Удаление первого элемента массива означает, что появится свободное место по индексу 0. Чтобы заполнить это место, все элементы потребуется сдвинуть на один индекс влево.

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

Поиск элементов

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

Линейный поиск

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

В худшем случае линейный поиск заканчивается проверкой всего массива. Следовательно, его временная сложность равна O(n).

Бинарный поиск

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

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

Временная сложность операций