Выбрать главу

Терминология

Элементы массива пронумерованы, причем нумерация начинается с 0, а не с 1. Например, в этом массиве значение 20 находится в позиции 1.

А значение 10 находится в позиции 0. Неопытных программистов этот факт обычно вводит в ступор. Тем не менее выбор нулевой начальной позиции упрощает написание кода по работе с массивами, поэтому программисты остановились на этом варианте. Почти во всех языках программирования нумерация элементов массива начинается с 0. Вскоре вы к этому привык­нете.

Позиция элемента называется его индексом. Таким образом, вместо того чтобы говорить «Значение 20 находится в позиции 1», правильно сказать «Значение 20 имеет индекс 1». В этой книге термин «индекс» означает то же, что и «позиция».

Ниже приведены примеры времени выполнения основных операций с массивами и списками.

Вопрос: почему вставка элемента в массив требует времени O(n)? Предположим, вы хотите вставить элемент в начало массива. Как бы вы это сделали? Сколько времени на это потребуется? Ответы на эти вопросы вы найдете в следующем разделе!

Упражнения

2.1 Допустим, вы строите приложение для управления финансами.

         1. Продукты

         2. Кино

         3. Велосипедный клуб

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

Вставка в середину списка

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

Неупорядоченный                                              Упорядоченный

Что лучше подойдет для вставки элементов в середину: массивы или списки? Со списком задача решается изменением указ ателя в предыдущем элементе.

А при работе с массивом придется сдвигать вниз все остальные элементы.

А если свободного места не осталось, все данные придется скопировать в новую область памяти! В общем, списки лучше подходят для вставки элементов в середину.

Удаление

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

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

Ниже приведены примеры времени выполнения основных операций с массивами и связанными списками.

Заметим, что вставка и удаление выполняются за время O(1) только в том случае, если вы можете мгновенно получить доступ к удаляемому элементу. На практике обычно сохраняются ссылки на первый и последний элементы связанного списка, поэтому время удаления этих элементов составит всего O(1).

Какая структура данных используется чаще: массивы или списки? Очевидно, это зависит от конкретного сценария использования. Массивы чрезвычайно популярны из-за того, что они поддерживают произвольный доступ. Всего существуют два вида доступа: произвольный и последовательный. При последовательном доступе элементы читаются по одному, начиная с первого. Связанные списки поддерживают только последовательный доступ. Если вы захотите прочитать 10-й элемент связанного списка, вам придется прочитать первые 9 элементов и перейти по ссылкам к 10-му элементу. Я часто говорю, что массивы обладают более высокой скоростью чтения; это объясняется тем, что они поддерживают произвольный доступ. Многие реальные ситуации требуют произвольного доступа, поэтому массивы часто применяются на практике. Также массивы и списки используются для реализации других структур данных (о которых будет рассказано в книге далее).