На этом шаге вспомним понятия массива и связанного списка.
Рассмотрим работу памяти компьютера. Она представляет собой нечто вроде огромного шкафа с множеством ящиков, и у каждого ящика есть адрес.
Каждый раз, когда вы хотите сохранить в памяти отдельное значение, вы запрашиваете у компьютера место в памяти, а он выдает адрес для сохранения значения.
Если же вам понадобится сохранить несколько элементов, это можно сделать двумя основными способами: воспользоваться массивом или списком.
Предположим, вы пишете приложение для управления текущими делами. Описания задач должны храниться в виде списка в памяти. Что использовать - массив или связанный список? Для начала попробуем сохранить задачи в массиве. При использовании массива все задачи хранятся в памяти непрерывно (то есть рядом друг с другом).
Теперь предположим, что вы захотели добавить четвертую задачу. Но следующий ящик уже занят.
Приходится искать новое место, где смогут разместиться все задачи. В этом случае вам придется запросить у компьютера другой блок памяти, в котором поместятся все четыре задачи, а потом переместить все свои задачи туда.
Простейшее решение - "бронирование мест": даже если список состоит всего из 3 задач, вы запрашиваете у компьютера место на 10 позиций просто на всякий случай. Тогда в список можно будет добавить до 10 задач, и ничего перемещать не придется. Это неплохое обходное решение, но у него есть пара недостатков:
- Лишнее место может не понадобиться, и тогда память будет расходоваться неэффективно. Вы ее не используете, однако никто другой ее использовать тоже не может.
- Если в список будет добавлено более 10 задач, перемещаться все равно придется.
Связанные списки решают проблему добавления новых элементов. При использовании связанного списка элементы могут размещаться где угодно в памяти.
В каждом элементе хранится адрес следующего элемента списка . Таким образом, набор произвольных адресов памяти объединяется в цепочку.
Допустим, вы хотите получить последний элемент связанного списка. Просто прочитать нужное значение не удастся, потому что вы не знаете, по какому адресу оно хранится. Вместо этого придется сначала обратиться к элементу № 1 и узнать адрес элемента № 2, потом обратиться к элементу № 2 и узнать адрес элемента № 3"... и так далее, пока не доберетесь до последнего элемента.
Связанные списки отлично подходят в тех ситуациях, когда данные должны читаться последовательно: сначала вы читаете один элемент, по адресу переходите к следующему элементу и т. д. Но если вы намерены прыгать по списку, то не используйте связанные списки.
Работая с массивом, вы заранее знаете адрес каждого его элемента.
Что лучше подойдет для вставки элементов в середину: массивы или списки? Со списком задача решается изменением указателя в предыдущем элементе.
А при работе с массивом придется сдвигать вниз все остальные элементы.
А если свободного места не осталось, все данные придется скопировать в новую область памяти. Cписки лучше подходят для вставки элементов в середину.
Что, если вы захотите удалить элемент? И снова список лучше подходит для этой операции, потому что в нем достаточно изменить указатель в предыдущем элементе. В массиве при удалении элемента все последующие элементы нужно будет сдвинуть вверх.
Ниже приведены примеры времени выполнения основных операций с массивами и связанными списками.
На следующем шаге рассмотрим сортировку выбором.
