Односвязные списки

Каждый элемент односвязного списка содержит одно или несколько информационных полей и единственное поле связи.

Элемент хранения односвязного списка описывается следующим образом:

Type Plist=^List; List= record info: word; link: plist; end;	{ указатель на узел списка } { описание узла списка } { информационное поле узла } { поле связи узла }
Var first: PList; p: PList; x: word;	{ указатель на первый узел списка } { вспомогательный указатель }

На рис. 21 представлен пример структуры односвязного списка.

Рис. 21. Структура односвязного списка

На первый элемент списка указывает указатель first. Если список пуст, то first = nil. Если список не пуст, то к атрибуту любого его элемента (например, первого) можно получить доступ через указатель.

x:=first ^.info; p:=first ^.link;

{ значение информационного поля первого элемента } { значение поля связи первого элемента – адрес второго элемента }

К атрибутам любого элемента списка, кроме первого, возможен дистанционный доступ.

x:=first ^.link ^.info;

{ значение информационного поля второго элемента }

Дистанционный доступ ко второму узлу списка эквивалентен следующей последовательности операторов:

p:=first ^.link; x:=p^.info;

{ установка вспомогательного указателя на второй узел списка } { значение информационного поля второго узла списка }