Protected. fHead, fRear: pItem; // поля – указатели на начало и конец списка

fHead, fRear: pItem; // поля – указатели на начало и конец списка

fSize: Word; // поле – число элементов списка

Public

// Свойство - число элементов списка (доступ по чтению и записи)

property Size: Word read fSize write fSize;

// Свойство – указатель на начало списка (доступ по чтению и записи)

property Head: pItem read fHead write fHead;

// Свойство – указатель на конец списка (доступ по чтению и записи)

property Rear: pItem read fRear write fRear;

// Включение элемента со значением v справа от элемента с адресом Addr

procedure InsertRight(Addr: pItem; v: tValue);

// Включение элемента со значением v слева от элемента с адресом Addr

procedure InsertLeft(Addr: pItem; v: tValue);

// Исключение элемента справа от элемента с указателем Addr

function DeleteRight(Addr: pItem): tValue;

// Исключение из списка элемента с указателем Addr

function Delete(Addr: pItem): tValue;

// Возвращение адреса элемента со значением v

function Search(v: tValue): pItem;

// Включение элемента со значением v в начало списка

procedure InsertHead(v: tValue);

// Включение элемента со значением v в конец списка

procedure InsertRear(v: tValue);

function DeleteHead: tValue; // исключение из начала

function DeleteRear: tValue; // исключение из конца

function Empty: Boolean; // возвращение true, если список пуст

procedure Clear; // очистка списка

constructor Create; // конструктор - создание пустого списка

destructor Destroy; override; // деструктор - удаление списка

end; // tDCList

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

Addr^.Left^.Right = Addr = Addr^.Right^.Left.

10. Реализация основных операций над двусвязным списком

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

Реализация операции приведена ниже. Предполагается, что значение Addr отлично от nil и элемент с адресом Addr присутствует в списке. Если список пуст, то новый элемент включается в начало списка. При включении в конец списка указатель Rear передвигается на включенный элемент.

procedure tDCList.InsertRight(Addr: pItem; v: tValue);

Var

NewItem: pItem; // указатель на новый элемент

Begin

NewItem: = New(pItem); // выделение памяти под новый элемент списка

NewItem^.Value: = v;

if Empty

then begin // если список пуст, включаем в его начало

NewItem^.Left: = nil; NewItem^.Right: = nil;

fHead: = NewItem; fRear: = NewItem; end

else begin // список не пуст

NewItem^.Left: = Addr;

NewItem^.Right: = Addr^.Right;

if Addr=fRear

then fRear: = NewItem // если включение в конец списка

else Addr^.Right^.Left: = NewItem; // если включение в середину

Addr^.Right: = NewItem;

end;

Inc(fSize); // увеличение числа элементов списка на 1

end; // procedure tDCList.InsertRight

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

Исключение из двусвязного списка элемента с указателем Addr. При реализации операции необходимо рассмотреть следующие частные случаи:

– если исключается элемент в начале списка (Addr=fHead), то расположенный справа от удаляемого элемент должен стать первым;

– если исключается элемент в конце списка (Addr=fRear), то расположенный слева от удаляемого элемент должен стать последним.

function tDCList.Delete(Addr: pItem): tValue;

Begin

Delete: = Addr^.Value;

if Addr=fHead

then fHead: =Addr^.Right // исключается первый элемент

else Addr^.Left^.Right: =Addr^.Right; // исключается не первый элемент

if Addr=fRear

then fRear: =Addr^.Left // исключается последний элемент

else Addr^.Right^.Left: =Addr^.Left; // исключается не последний элемент

Dispose(Addr);

Dec(fSize); // уменьшение числа элементов на 1

end; // function tDCList.Delete

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

function tDCList.DeleteRight(Addr: pItem): tValue;

Begin

if Addr=fRear

then WriteLn('Исключаемый элемент отсутствует')