|
Для достижения большей гибкости в работе с линейными списками можно включить в каждый узел два атрибута связи – указатели на следующий узел (т.е. на “правого соседа”) и на предыдущий узел (т.е. на “левого соседа”). Списки с двумя связями занимают больше памяти, чем односвязные, однако в процессе прохода по списку они дают возможность продвигаться как “вперед”, так и “назад”, что повышает эффективность реализации алгоритмов обработки списков.
В двусвязном нециклическом списке первый узел не имеет предшественника (поле связи prev первого узла равно NIL), а последний узел не имеет последователя (поле связи next последнего узла равно NIL). На первый узел двусвязного списка, имеющего нециклическую структуру, указывает указатель first: pDlist. Выполнение условия first = nil означает, что двусвязный нециклический список пуст.
Нециклическая структура двусвязного списка порождает те же проблемы при включении / исключении первого и последнего узлов, что и структура односвязного нециклического списка.
На практике более широко применяются двусвязные циклические списки. В двусвязном циклическом списке поле связи next его последнего элемента не содержит значения NIL, а указывает на первый узел списка и поле связи prev его первого элемента также не содержит значения NIL, а указывает на последний узел списка. В целях удобства обработки в структуру двусвязного циклического списка включают специальный дополнительный узел с особым содержанием информационного поля (на рис. 34 это поле заштриховано), называемый “головой“ списка или “сторожем“. Заметим, что “левым соседом” первого узла двусвязного циклического списка является его последний узел, а “правым соседом” его последнего узла является первый узел, т.к. информационное поле головного узла имеет особое содержание (а нередко и вовсе не используется). Так что функция “сторожа” в двусвязном циклическом списке оказывается чисто технологической и полностью аналогичной функции “сторожа” в односвязном циклическом списке.
Выполнение условия head = nil означает, что двусвязный циклический список не существует. Выполнение условия head ^. next = head ^. prev = head означает, что двусвязный циклический список существует, но является пустым, т.е. содержит только головной элемент.
|
