Линейный двунаправленный список

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

Рисунок 3.2 – Линейный двусвязный список

Основные операции, осуществляемые с линейным двунаправленным списком те же, что и с однонаправленным линейным списком:

– вставка элемента;

– просмотр;

– поиск;

– удаление элемента.

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

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

type

PElement = ^TypeElement;{указатель на тип элемента}

TypeElement = record {тип элемента списка}

Data: TypeData; {поле данных элемента}

Next, {поле указателя на следующий элемент}

Last: PElement; {поле указателя на предыдующий элемент}

end;

var

ptrHead: PElement; {указатель на первый элемент списка}

ptrCurrent: PElement; {указатель на текущий элемент}

Операция вставки реализовывается с помощью двух процедур, аналогичных процедурам вставки для линейного однонаправленного списка: InsFirst_LineDubleList и Ins_LineDubleList. Однако, при вставке последующего элемента придется учитывать особенности добавления элемента в конец списка.

procedure Ins_LineDubleList(DataElem: TypeData;

var ptrHead, ptrCurrent: PElement);

{Вставка непервого элемента в линейный двунаправленный список}

{справа от элемента, на который указывает ptrCurrent}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

New(ptrAddition);

ptrAddition^.Data := DataElem;

if ptrHead = nil then begin {список пуст}

{создаем первый элемент списка}

ptrAddition^.Next := nil;

ptrAddition^.Last := nil;

ptrHead := ptrAddition;

end else begin {список не пуст}

{вставляем элемент списка справа от элемента,}

{на который указывает ptrCurrent}

if ptrCurrent^.Next <> nil then {вставляем не последний}

ptrCurrent^.Next^.Last := ptrAddition;

ptrAddition^.Next := ptrCurrent^.Next;

ptrCurrent^.Next := ptrAddition;

ptrAddition^.Last := ptrCurrent;

end;

ptrCurrent := ptrAddition;

end;

procedure InsFirst_LineDubleList(DataElem: TypeData;

var ptrHead: PElement);

{Вставка первого элемента в линейный двунаправленный список}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

New(ptrAddition);

ptrAddition^.Data := DataElem;

ptrAddition^.Last := nil;

if ptrHead = nil then begin {список пуст}

{создаем первый элемент списка}

ptrAddition^.Next := nil;

end else begin {список не пуст}

{вставляем новый элемент слева (перед) первым элементом}

ptrAddition^.Next := ptrHead;

ptrHead^.Last := ptrAddition;

end;

ptrHead := ptrAddition;

end;

Листинг 3.4 – Процедуры добавления элемента в двусвязный список (в хвост и голову)

Порядок следования операторов присваивания обеих процедур здесь также очень важен. При неправильном переопределении указателей возможен разрыв списка или потери указателя на первый элемент, что приводит к потере доступа к части или всему списку.

Ниже представлен псевдокод процедуры List-Insert, которая добавляет элемент х к списку L, помещая его в голову списка.

Листинг 3.5 – Добавление элемента в голову списка

Процедура List-Insert выполняется за время O(1) (не зависящее от длины списка).

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

Операция удаления элемента также осуществляется во многом аналогично удалению из линейного однонаправленного списка.

procedure Del_LineDubleList(var ptrHead,

ptrCurrent: PElement);

{Удаление элемента из линейного двунаправленного списка}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

if ptrCurrent <> nil then begin {вх.параметр корректен}

if ptrCurrent = ptrHead then begin {удаляем первый}

ptrHead := ptrHead^.Next;

dispose(ptrCurrent);

ptrHead^.Last := nil;

ptrCurrent := ptrHead;

end else begin { удаляем не первый }

if ptrCurrent^.Next = nil then begin {удаляем последний}

ptrCurrent^.Last^.Next := nil;

dispose(ptrCurrent);

ptrCurrent := ptrHead;

end else begin {удаляем не последний и не первый}

ptrAddition := ptrCurrent^.Next;

ptrCurrent^.Last^.Next := ptrCurrent^.Next;

ptrCurrent^.Next^.Last := ptrCurrent^.Last;

dispose(ptrCurrent);

ptrCurrent := ptrAddition;

end;

end;

end;

end;

Листинг 3.6 – Процедура удаления элемента из двусвязного списка

Ниже представлена процедура List-Delete на псевдокоде, которая удаляет элемент х из списка L, направляя указатели «в обход» этого элемента. При этом в качестве аргумента ей передаётся указатель на х. Если задан ключ элемента х, то перед удалением надо найти его указатель с помощью процедуры List-Search.

Листинг 3.7 – Удаление элемента из двусвязного списка

Процедура List-Delete работает за время O(1); однако для удаления элемента с заданные ключом его надо сначала найти, что потребует времени (n).

Использование двух указателей в линейном двунаправленном списке позволяет ускорить операции, связанные с передвижением по списку за счет двунаправленности этого движения. Однако, элементы списка за счет дополнительного поля занимают больший объем памяти. Кроме того, усложнились операции вставки и удаления элементов за счет необходимости манипулирования большим числом указателей.