Списки с последовательным доступом

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

Преимущества связных списков перед списками с прямым доступом проявляются в тех случаях, когда часто используются операции вставки и удаления элементов списков. Еще одно преимущество динамического выделения памяти может проявиться, когда в алгоритме одновременно используется большое количество списков, каждый из которых в процессе работы может потребовать большой объем памяти, однако в совокупности эта память может быть ограничена приемлемой величиной.

Элементы связного списка, следующие друг за другом, не обязательно размещаются в последовательных ячейках памяти, доступ к следующему и предыдущему элементам осуществляется при помощи специальных ссылок (указателей). Чтобы обеспечить запоминание указателей на следующий и предыдущий элементы, каждый элемент списка «погружается» в узел, для которого формируется в памяти компьютера запись, состоящая из нескольких полей. В простейшем случае эта запись может состоять из двух полей. Одно из них Info предназначено для запоминания самого элемента, а другое – Next для запоминания позиции следующего. Для обозначения такого узла будем использовать следующую форму , где t позиция (адрес) узла в памяти. Поскольку у последнего элемента нет следующего, его поле Next заполняют значением nil. Иногда вместо nil используют ссылку на самого себя, или на первый элемент списка. Представление списка с помощью таких узлов обеспечивает сканирование списка от начала к его концу.

Для обеспечения сканирования как от начала к концу, так и от конца к началу, используют узлы следующего вида . Поле Preced используется для запоминания позиции элемента, предшествующего элементу, находящемуся в позиции t. Доступ к такому списку может осуществляться как через его начало, так и через его конец. Такие списки называются двусторонними. На рисунках 5-6 изображены примеры двусторонних списков.

Операции над списками.

При описании операций со списками через t^ будем обозначать узел, расположенный в позиции t. Оператор создания нового узла будем записывать в виде Create(t:[Info,Next,Preced]).

Рассмотрим основные отображения и операции на примере одностороннего циклического списка (рис. 4). Считаем, что дескриптор списка S имеет вид [last]. Основные отображения определяются следующим образом.

· Info(pos)=pos^.Info,

· Next(pos)=pos^.Next,

Признак конца pos=last..