Структуры данных и модели вычислений
Списки с последовательным доступом
Последовательный доступ к элементам списка, как правило, реализуется с использованием динамического выделения памяти во время исполнения программы. Поиск свободных участков памяти обычно возлагается на систему программирования. Мы будем называть такие списки связными. Преимущества связных списков перед списками с прямым доступом проявляются в тех случаях, когда часто используются вставки в списки и удаление элементов из списков. Еще одно преимущество динамического выделения памяти может проявиться, когда в алгоритме одновременно используется большое количество списков, каждый из которых в процессе работы может потребовать большой объем памяти, однако в совокупности эта память может быть ограничена приемлемой величиной.
Элементы связного списка, следующие друг за другом, не обязательно размещаются в последовательных ячейках памяти — доступ к следующему и предыдущему элементам осуществляется при помощи специальных ссылок (указателей). Чтобы обеспечить запоминание указателей на следующий и предыдущий элементы, каждый элемент списка "погружается" в узел, для которого в памяти компьютера формируется запись, состоящая из нескольких полей. В простейшем случае эта запись может состоять из двух полей. Одно из них — — предназначено для запоминания самого элемента, а другое — — для запоминания позиции следующего. Для обозначения такого узла будем использовать следующую форму:
где — позиция (адрес) узла в памяти. Поскольку у последнего элемента нет следующего, его поле заполняют значением . Иногда вместо используют ссылку на сам этот элемент, что также может являться признаком конца списка. Мы часто будем пользоваться именно этим способом распознавания конца списка. Представление списка с помощью таких узлов обеспечивает сканирование списка от начала к его концу. Доступ к самому списку осуществляется через его голову с помощью переменной , содержащей позицию первого элемента. Такие списки называются односторонними.
При описании операций со списками через будем обозначать узел, расположенный в позиции .
