Который предвартельно установлен указатель

 

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

 

 

 

Рис. 36. Включение узла “справа” от узла, на который предварительно установлен указатель

 

Procedure Ins_Right( head,p: pDlist );	{ head – указатель на “голову” списка }
	{ p – предварительно установленный указатель}
var q: pDlist;	{ q – указатель на новый узел }
Begin
if ( head <> nil ) and ( p <> nil ) then	{ указатель p действительно установлен? }
Begin
New( q );	{ создание нового узла }
Readln( q^ . info );	{ заполнение информационного поля нового узла }
q^. prev:=p;	{ 1 - установка связи нового узла с предыдущим }
q^. next:=p^ . next;	{ 2 - установка связи нового узла со следуюшим }
p^. next^. prev:=q;	{ 3 - установка связи следующего узла с новым }
p^. next:=q;	{ 4 - установка связи предыдущего узла с новым }
end;
end;

 

Процедура включения нового узла “слева” от узла, на который предварительно установлен указатель, выполняется аналогично (рис. 37). В отличие от односвязного списка, никакого прохода до узла, предшествующего узлу p^ не требуется, достаточно обратиться к соответствующему атрибуту связи узла p^ .

 

 

 

Рис. 37. Включение узла “слева” от узла, на который предварительно установлен указатель

 

Ниже приведена процедура создания двусвязного циклического списка из n узлов.

 

Procedure Create_Double( var head: PDlist; n: byte ); var p: PDlist; i: byte; begin new( head ); head^.next:=head; head^.prev:=head;	{ head – указатель на голову списка } { n – количество узлов в списке }     { создание элементарного кольца }
for i:=1 to n do begin	{ cоздание циклического списка из n узлов }
new( p );	{ создание узла списка }
readln(p^.info);	{ заполнение информационного поля узла }
p^.next:=head;	{ операции }
p^.prev:=head^.prev;	{ установки связей }
head^.prev^.next:=p;	{ нового узла }
head^.prev:=p;	{ и списка }
end; end;

 

Каким образом включаются узлы в список при выполнении процедуры Create_ Double: “за” головным узлом или “перед” ним?