Двунаправленные линейные списки

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

Для этого каждый элемент должен иметь не одно, а два связующих поля: указатель на элемент слева и указатель на элемент справа.

 

	Элем. 1 правый левый		Элем. 2 правый левый		Элем. 3 правый левый		Элем. N правый левый

 

...

 

 

pHead

Аналогично обычным спискам, удобно ввести фиктивный заголовочный элемент, а поскольку двунаправленные списки являются симметричными, удобно сделать их замкнутыми, кольцевыми: правая ссылка последнего элемента указывает на заголовок, а левая ссылка заголовка – на последний элемент. Адрес заголовка определяется указателем pHead.

 

			Элем. 2 правый левый		Элем. N правый левый

 

...

 

Отметим достоинства и недостатки двунаправленных списков. Достоинство – простота перехода от текущего элемента к любому его соседу. Недостатки – увеличиваются затраты памяти и число операций на поддержку дополнительного указателя.

Двунаправленный список можно реализовать как на основе массива (причем – обеими способами), так и динамически.

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

type pDin2Item = ^ TDin2Item; {ссылочный тип}

TDin2Item = record {базовый тип}

inf: <тип информационной части>;

left, right: pDin2Item; {адреса соседних элементов}

end;

Если pHead есть указатель на заголовок, то пустой список создается так:

· выделяется память под заголовок, адресуемая указателем pHead

· оба ссылочных поля заголовка устанавливаются в адрес самого заголовка: pHead^.left:= pHead; pHead^.right:= pHead;

(при этом пустая ссылка nil нигде НЕ используется!)

Набор операций расширяется просмотром и поиском не только в прямом, но и в обратном направлениях. Немного изменяется условие достижения конца списка – вместо условия появления пустой ссылки надо использовать условие получения на текущем шаге адреса заголовка. Например, проход в обратном направлении реализуется так:

· устанавливаем начальное значение указателя текущего элемента на последний элемент списка: pCurrent:= pHead^.left;

· организуем цикл прохода до достижения заголовка

while pCurrent <> pHead do pCurrent:= pCurrent^.left;

 

pCurrent

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

 

Если удаляемый элемент адресуется указателем pCurrent, то pCurrent^.left определяет адрес левого соседа, а pCurrent^.right – адрес правого соседа. Тогда необходимые изменения реализуются так:

pCurrent^.left^.right:= pCurrent^.right;

pCurrent^.right^.left:= pCurrent^.left;

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

 

 

Необходимые присваивания (порядок следования важен!):

pTemp^.right:= pCurrent^.right;

pTemp^.left:= pCurrent;

pCurrent^.right^.left:= pTemp;

pCurrent^.right:= pTemp;

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