4.4.7. Включение нового узла в список за тем узлом, на

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

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

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

Procedure Ins( first, p: PList );				{ first – указатель на первый узел списка,
			p – предварительно установленный указатель}
var q: PList;					{ q – указатель на вставляемый узел }
begin
if ( first <> nil ) and ( p <> nil ) then				{ указатель p действительно установлен? }
begin
new( q );				{ создание нового узла списка для вставки }
readln( q^.info );		{ заполнение информационного поля нового узла }
q^.link:=p^.link;		{ заполнение поля связи нового узла }
p^.link:=q;	{ изменение поля связи того узла, за которым вставлен новый узел }
end;
end;

4.4.8. Исключение из списка узла за тем узлом, на

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

Исключение из списка элемента за тем элементом, на который предварительно установлен указатель, выполняется с использованием вспомогательного указателя на исключаемый элемент. Последовательность операций исключения иллюстрируется рис. 27. После выполнения операции исключения значение указателя на первый элемент списка не изменяется. Значение указателя на тот элемент, за которым выполнено исключение, также не изменяется.

Рис. 27. Исключение узла за тем узлом, на который предварительно установлен указатель

Procedure Del( first, p: PList );						{ first – указатель на первый узел списка,
					p – предварительно установленный указатель}
var q: PList;					{ q – указатель на исключаемый узел }
begin
if ( first <> nil ) and ( p <> nil ) and							{ указатель p действительно установлен?}
( p^.link <> nil ) then				{ указатель p не указывает на последний узел в списке? }
begin
q:=p^.link;	{ установить указатель q на узел, следующий за элементом p^ }
p^.link:=q^.link;			{ изменить поле связи узла, за которым выполняется исключение }
dispose ( q );		{ элемент хранения исключаемого узла списка вернуть в кучу }
end;
end;

4.4.9. Исключение из списка узла, на который предварительно

установлен указатель

Если требуется включение / исключение перед указанным элементом или исключение самого указанного элемента, то необходима предварительная установка указателя на элемент, предшествующий заданному, т.к. в этом случае с целью сохранения структуры списка у узла-предшественника должна быть изменена связь (см. рис. 28). Для установки указателя на узел, предшествующий данному узлу, необходим проход от начала списка до узла-предшественника, т.к. в элементе односвязного линейного списка нет ссылки на предыдущий узел. После исключения узла из списка и возвращения его элемента хранения в кучу, доступ к этому узлу по предварительно установленному указателю становится невозможным, поэтому данному указателю следует присвоить значениеNIL.

Рис. 28. Исключение узла, на который предварительно установлен указатель