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

Элемент односвязного списка содержит два поля (рис 3.2): информационное поле (INFO) и поле указателя (PTR).

Рис. 3.2

Особенностью указателя является то, что он дает только адрес последующего элемента списка. Поле указателя по последнего элемента в списке является пустым (NIL). LST указатель на начало списка. Список может быть пустым, то тогда LST будет равен NIL.

Доступ к элементу списка осуществляется только от его начала, то есть обратной связи в этом списке нет.

Терминология:

l p - указатель

l node(p) – узел, на который ссылается указатель p (при этом неважно в какое место изображения элемента (узла) списка он направлен на рисунке)

l ptr(p) – ссылка на последующий элемент узла node(p)

l ptr(ptr(p)) – ссылка последующего для node(p) узла на последующий для него элемент