Списки с последовательным доступом
Последовательный доступ к элементам списка, как правило, реализуется с использованием динамического выделения памяти во время исполнения программы. Поиск свободных участков памяти обычно возлагается на систему программирования. Мы будем называть такие списки связными. Преимущества связных списков перед списками с прямым доступом проявляются в тех случаях, когда часто используются вставки в списки и удаление элементов из списков. Еще одно преимущество динамического выделения памяти может проявиться, когда в алгоритме одновременно используется большое количество списков, каждый из которых в процессе работы может потребовать большой объем памяти, однако в совокупности эта память может быть ограничена приемлемой величиной.
Элементы связного списка, следующие друг за другом, не обязательно размещаются в последовательных ячейках памяти — доступ к следующему и предыдущему элементам осуществляется при помощи специальных ссылок (указателей). Чтобы обеспечить запоминание указателей на следующий и предыдущий элементы, каждый элемент списка "погружается" в узел, для которого в памяти компьютера формируется запись, состоящая из нескольких полей. В простейшем случае эта запись может состоять из двух полей. Одно из них — — предназначено для запоминания самого элемента, а другое — — для запоминания позиции следующего. Для обозначения такого узла будем использовать следующую форму:
где — позиция (адрес) узла в памяти. Поскольку у последнего элемента нет следующего, его поле заполняют значением . Иногда вместо используют ссылку на сам этот элемент, что также может являться признаком конца списка. Мы часто будем пользоваться именно этим способом распознавания конца списка. Представление списка с помощью таких узлов обеспечивает сканирование списка от начала к его концу. Доступ к самому списку осуществляется через его голову с помощью переменной , содержащей позицию первого элемента. Такие списки называются односторонними.
При описании операций со списками через будем обозначать узел, расположенный в позиции .
Для доступа к полям узла
используем форму ,
и т.д. Оператор для создания нового узла будем записывать в виде
Для обеспечения сканирования как от начала к концу, так и от конца к началу используют узлы следующего вида:
Поле служит для запоминания позиции элемента, предшествующего элементу, находящемуся в позиции . Доступ к такому списку может осуществляться как через его начало с помощью переменной , так и через конец с помощью переменной . Такие списки называются двусторонними.
На рис. 2.1—2.6 представлено несколько разновидностей списков. Узлы списков изображены прямоугольниками, разделенными на части по числу полей. Стрелки проведены в соответствии со значениями полей и .
Рис. 2.1. Односторонний список: вход через первый элемент, сканирование от начала к концу, признак конца — Next(pos) = nil
Рис. 2.2. Односторонний список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = pos
Рис. 2.3. Односторонний циклический список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = first
Рис. 2.4. Односторонний циклический список: вход через последний элемент с помощью ссылки Last^.next; сканирование от начала к концу, признак конца — pos = last
Рис. 2.5. Двусторонний список: вход через первый элемент, сканирование от начала к концу и от конца к началу; признак начала — Procede(pos) = nil; признак конца — Next(pos) = nil
Рис. 2.6. Двусторонний циклический список: вход через первый элемент; сканирование от начала к концу и от конца к началу, признак конца — Next(pos) = first
При ее использовании могут возникнуть проблемы, связанные с некорректным обращением, так как в процедуре не производится проверка, является ли позиция pos позицией какого-либо элемента списка . Ответственность за некорректное обращение несет вызывающая программа. Проверка этого условия с помощью сканирования списка могла бы оказаться слишком дорогой и свела бы на нет преимущества использования связных списков. Еще одна проблема, связанная с выполнением этой операции, заключается в том, что узел
может оказаться недоступным при потере значения переменной pos, но память будет оставаться занятой. Если это нежелательно, следует, воспользовавшись системными средствами, освободить занимаемую узлом память. Замечания по поводу некорректного обращения будут справедливы и для некоторых следующих процедур, однако мы не будем каждый раз напоминать об этом.
Вставить в список элемент после элемента, находящегося в позиции
Следующие две операции рассмотрим на примере одностороннего циклического списка (см. рис. 2.4).
Добавить элемент к концу списка
Добавить элемент к началу списка
Следующие три процедуры рассмотрим на примере двустороннего циклического списка (см. рис. 2.6).
Удалить последний элемент списка
Удалить первый элемент списка
Удалить из списка элемент, находящийся в позиции
