Двусвязные списки

Для достижения большей гибкости в работе с линейными списками можно включить в каждый узел два атрибута связи – указатели на следующий узел (т.е. на “правого соседа”) и на предыдущий узел (т.е. на “левого соседа”). Списки с двумя связями занимают больше памяти, чем односвязные, однако в процессе прохода по списку они дают возможность продвигаться как “вперед”, так и “назад”, что повышает эффективность реализации алгоритмов обработки списков.

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

Type PDlist=^ Dlist; Dlist= record info: word; next: pDlist; prev: pDlist end;

{ указатель на узел списка } { описание узла списка } { информационное поле узла } { поле связи со следующим узлом } { поле связи с предыдущим узлом }

В двусвязном нециклическом списке первый узел не имеет предшественника (поле связи prev первого узла равно NIL), а последний узел не имеет последователя (поле связи next последнего узла равно NIL). На первый узел двусвязного списка, имеющего нециклическую структуру, указывает указатель first: pDlist. Выполнение условия first = nil означает, что двусвязный нециклический список пуст. Структура двусвязного нециклического списка представлена на рис. 33.

Рис. 33. Структура двусвязного нециклического списка

Нециклическая структура двусвязного списка порождает те же проблемы при включении / исключении первого и последнего узлов, что и структура односвязного нециклического списка.

На практике более широко применяются двусвязные циклические списки. В двусвязном циклическом списке поле связи next его последнего элемента не содержит значения NIL, а указывает на первый узел списка и поле связи prev его первого элемента также не содержит значения NIL, а указывает на последний узел списка. В целях удобства обработки в структуру двусвязного циклического списка включают специальный дополнительный узел с особым содержанием информационного поля (на рис. 34 это поле заштриховано), называемый “головой“ списка или “сторожем“. Заметим, что “левым соседом” первого узла двусвязного циклического списка является его последний узел, а “правым соседом” его последнего узла является первый узел, т.к. информационное поле головного узла имеет особое содержание (а нередко и вовсе не используется). Так что функция “сторожа” в двусвязном циклическом списке оказывается чисто технологической и полностью аналогичной функции “сторожа” в односвязном циклическом списке. Структура двусвязного циклического списка приведена на рис. 34.

Рис. 34. Структура двусвязного циклического списка

var head: pDlist;	{ указатель на голову списка }
p: pDlist;	{ вспомогательный указатель }

Выполнение условия head = nil означает, что двусвязный циклический список не существует. Выполнение условия head ^. next = head ^. prev = head означает, что двусвязный циклический список существует, но является пустым, т.е. содержит только головной элемент. Пустой циклический список с головным элементом представляется структурой элементарного кольца (рис. 35).

Рис. 35. Структура элементарного двусвязного кольца

Для любого узла двусвязного циклического списка, на который установлен указатель p (в том числе, и для головного), справедливо выражение: p^.next^.prev = p^.prev^.next = p;