естятся все четыре задачи, а потом переместить все свои задачи туда.
Если вдруг придет еще один друг, места опять не хватит, и вам всем придется перемещаться снова! Сплошная суета. Кроме того, добавление новых элементов в массив станет серьезной проблемой. Если свободного места нет и вам каждый раз приходится перемещаться в новую область в памяти, операция добавления нового элемента будет выполняться очень медленно. Простейшее решение — «бронирование мест»: даже если список состоит всего из 3 задач, вы запрашиваете у компьютера место на 10 позиций… просто на всякий случай. Тогда в список можно будет добавить до 10 задач, и ничего перемещать не придется. Это неплохое обходное решение, но у него есть пара недостатков:
• Лишнее место может не понадобиться, и тогда память будет расходоваться неэффективно. Вы ее не используете, однако никто другой ее использовать тоже не может.
• Если в список будет добавлено более 10 задач, перемещаться все равно придется.
В общем, прием неплохой, но его нельзя назвать идеальным. Связанные списки решают проблему добавления новых элементов.
Связанные списки
При использовании связанного списка элементы могут размещаться где угодно в памяти.
В каждом элементе хранится адрес следующего элемента списка. Таким образом, набор произвольных адресов памяти объединяется в цепочку.
Связанные адреса памяти
Все как в игре «Найди клад». Вы приходите по первому адресу, там написано: «Следующий элемент находится по адресу 123». Вы идете по адресу 123, там написано: «Следующий элемент находится по адресу 847» и т.д. Добавить новый элемент в связанный список проще простого: просто разместите его по любому адресу памяти и сохраните этот адрес в предыдущем элементе.
Со связанными списками ничего перемещать в памяти не нужно. Также сама собой решается другая проблема: допустим, вы пришли в кино с пятью друзьями. Вы пытаетесь найти место на шестерых, но кинотеатр уже забит, и найти шесть соседних мест невозможно. Нечто похожее происходит и с массивами. Допустим, вы пытаетесь найти для массива блок на 10 000 элементов. В памяти можно найти место для 10 000 элементов, но только не смежное. Для массива не хватает места! При хранении данных в связанном списке вы фактически говорите: «Ладно, тогда садимся на свободные места и смотрим кино». Если необходимое место есть в памяти, вы сможете сохранить данные в связанном списке.
Если связанные списки так хорошо справляются со вставкой, то чем тогда хороши массивы?
Массивы
На сайтах со всевозможными хит-парадами и «первыми десятками» применяется жульническая тактика для увеличения количества просмотров. Вместо того чтобы вывести весь список на одной странице, они размещают по одному элементу на странице и заставляют вас нажимать кнопку Next для перехода к следующему элементу. Например, «Десятка лучших злодеев в сериалах» не выводится на одной странице. Вместо этого вы начинаете с № 10 (Ньюман из «Сайнфелда») и нажимаете Next на каждой странице, пока не доберетесь до № 1 (Густаво Фринг из «Во все тяжкие»). В результате сайту удается показать вам рекламу на целых 10 страницах, но нажимать Next 9 раз для перехода к первому месту скучно. Было бы гораздо лучше, если бы весь список помещался на одной странице, а вы бы могли просто щелкнуть на имени человека для получения дополнительной информации.
Похожая проблема существует и у связанных списков. Допустим, вы хотите получить последний элемент связанного списка. Просто прочитать нужное значение не удастся, потому что вы не знаете, по какому адресу оно хранится. Вместо этого придется сначала обратиться к элементу № 1 и узнать адрес элемента № 2, потом обратиться к элементу № 2 и узнать адрес элемента № 3… и так далее, пока не доберетесь до последнего элемента. Связанные списки отлично подходят в тех ситуациях, когда данные должны читаться последовательно: сначала вы читаете один элемент, по адресу переходите к следующему элементу и т.д. Но если вы намерены прыгать по списку туда-сюда, держитесь подальше от связанных списков.
С массивами дело обстоит совершенно иначе. Работая с массивом, вы заранее знаете адрес каждого его элемента. Допустим, массив содержит пять элементов и вы знаете, что он начинается с адреса 00. По какому адресу хранится пятый элемент?
Простейшая математика дает ответ: это адрес 04. Массивы прекрасно подходят для чтения элементов в произвольных позициях, потому что обращение к любому элементу в массиве происходит мгновенно. В связанном списке элементы не хранятся рядом друг с другом, поэтому мгновенно определить позицию i-го элемента в памяти невозможно — нужно обратиться к первому элементу, чтобы получить адрес второго элемента, затем обратиться ко второму элементу для получения адреса третьего — и так далее, пока вы не доберетесь до i-го.
Терминология
Элементы массива пронумерованы, причем нумерация начинается с 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-му элементу. Я часто говорю, что массивы обладают более высокой скоростью чтения; это объясняется тем, что они поддерживают произвольный доступ. Многие реальные ситуации требуют произвольного доступа, поэтому массивы часто применяются на практике. Также массивы и списки используются для реализации других структур данных (о которых будет рассказано в книге далее).
Упражнения
2.2 Допустим, вы пишете приложение для приема заказов от посетителей ресторана. Приложение должно хранить список заказов. Официанты добавляют заказы в список, а повара читают заказы из списка и выполняют их. Заказы образуют очередь: официанты добавляют заказы в конец очереди, а повар берет первый заказ из очереди и начинает готовить.
Какую структуру данных вы бы использовали для реализации этой очереди: массив или связанный список? (Подсказка: связанные списки хорошо подходят для вставки/удаления, а массивы — для произвольного доступа к элементам. Что из этого понадобится в данном случае?)
2.3 Проведем мысленный эксперимент. Допустим, Facebook хранит список имен пользователей. Когда кто-то пытается зайти на сайт Facebook, система пытается найти имя пользователя. Если имя входит в список имен зарегистрированных пользователей, то вход разрешается. Пользователи приходят на Facebook достаточно часто, поэтому поиск по списку имен пользователей будет выполняться часто. Будем считать, что Facebook использует бинарный поиск для поиска в списке. Бинарному поиску необходим произвольный доступ — алгоритм должен мгновенно обратиться к среднему элементу текущей части списка. Зная это обстоятельство, как бы вы реализовали список пользователей: в виде массива или в виде связанного списка?