Реализация ДВУНАПРАВЛЕННОГО СПИСКА на базе ссылок.

8.1 Реализация.

1) Сделать список пустым.(Процедура)
2) Проверить наличие элементов в списке.(Функция)
3) Добавить элемент в начало,середину или конец списка.(Процедура)
4) Взять элемент из начала или конка списка.(Процедура)
5) Удалить элемент из списка.(Процедура)
6) Удалить список.(Процедура)

8.2 Процедуры и функции.

8.2.1 Основные типы и переменные :

Пусть Type InformType=byte;{Информационная часть}
LPtr=^spisok;
spisok=record
Inf:InformType;
next,prev:LPtr;
end;

var a1,a2:Lptr;

{a1-указывает на начало а2-указывает на конец}

8.2.2 Алгоритмы :

{Устанавливает указатель в начало списка}
procedure SetToHome(a1:LPtr;var b:LPtr);
begin
b:=a1;
end;

{Устанавливает указатель в конец списка}
procedure SetToHome(a2:LPtr;var b:LPtr);
begin
b:=a2;
end;

{Передвигает указатель на 1 эл-т вперед}
procedure Mov1(var b:LPtr);
begin
if(a<>nil)then b:=b^.next
end;

{Передвигает указатель на 1 эл-т назад}
procedure Mov2(var b:LPtr);
begin
if(a<>nil)then b:=b^.prev
end;

{Добавить элемент в начало}
procedure AddElemToHome(var a1,a2:Lptr;inf:InformType);
var n:Lptr;
begin
new(n);
n^.inf:=inf;
n^.prev:=nil;
n^.next:=a1;
if a1=nil then a2:=n else
a1^.prev:=n;
a1:=n;
end;

{Добавить элемент в конец}
procedure AddElemToEnd(var a1,a2:Lptr;inf:InformType);
var n:Lptr;
begin
new(n);
n^.inf:=inf;
n^.next:=nil;
n^.prev:=a2;
if a2=nil then a1:=n else a2^.next:=n;
a2:=n;
end;

{Добавить элемент в середину}
procedure AddToMid(var p:Lptr;inf:InformType);
var l:lptr;
begin
if(p<>nil)and(p^.prev<>nil)and(p^.next<>nil)
{В середину} then
begin
new(l);
l^.inf:=inf;
l^.next:=p^.next;
l^.next^.prev:=l;
l^.prev:=p;
p^.next:=l;
end;
end;

{Взять элемент начала,kонца}

{Очевидно соответствие процедур которые берут элемент в однонаправленном и двунаправленном списках}

{Удаляем элемент :}

{Из начала}
procedure DelElemHome(Var a1,a2:LPtr);
var n:Lptr;
begin
if a1<>nil then
begin
if a1<>a2 then begin
a1:=a1^.next;
dispose(a1^.prev);
a1^.prev:=nil;
end else begin
dispose(a1);
a1:=nil;
a2:=nil;
end;
end;
end;

{Удалить элемент из конца списка.} procedure DelElemEnd(Var a1,a2:Lptr); var n:Lptr; begin if a1<>nil then begin if a1<>a2 then begin a2:=a2^.prev;
dispose(a2^.next);
a2^.next:=nil;
end else begin
dispose(a2);
a1:=nil;
a2:=nil;
end;
end;
end;

{Удалить элемент из середины списка.}
procedure DelElemMid(Var p:Lptr);
begin if(p<>nil)and(p^.prev<>nil)and(p^.next<>nil)then begin
p^.prev^.next:=p^.next;
p^.next^.prev:=p^.prev;
dispose(p); p:=nil;
end;
end;

{Сделаем список Пустым.}
procedure Delsp(var a1,a2:LPtr);
begin
while a1<>nil do DelElemHome(a1,a2);
end;