Удаление элемента из списка

Удаление элемента из односвязного списка показано на рис.5.7.

Рис.5.7. Удаление элемента из 1-связного списка

Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис.5.7.а). Мы, однако, на рис. 5.7 и в примере 5.4 приводим процедуру для случая, когда удаляемый элемент задается своим адресом (del на рис.5.7). Процедура обеспечивает удаления как из середины, так и из начала списка.

{==== Программный пример 5.4 ====}

{ Удаление элемента из любого места 1-связного списка }

Procedure DeleteSll(

var head: sllptr; { указатель на начало списка, может

измениться в процедуре }

del: sllptr { указатель на эл-т, к-рый удаляется });

var prev: sllptr; { адрес предыдущего эл-та }

begin

if head=nil then begin { попытка удаления из пустого списка

асценивается как ошибка (в последующих примерах этот случай

учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

if del=head then { если удаляемый эл-т - 1-й в списке, то

следующий за ним становится первым }

head:=del^.next

else begin { удаление из середины списка }

{ приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле next к-рого совпадает с адресом удаляемого элемента }

prev:=head^.next;

while (prev^.next<>del) and (prev^.next<>nil) do

prev:=prev^.next;

if prev^.next=nil then begin

{ это случай, когда перебран весь список, но эл-т не найден, он отсутствует в списке; расценивается как ошибка (в последующих примерах этот случай учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

prev^.next:=del^.next; { предыдущий эл-т теперь указывает

на следующий за удаляемым }

end;

{ элемент исключен из списка, теперь можно освободить

занимаемую им память }

Dispose(del);

end;

Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рис.5.8.

Рис.5.8. Удаление элемента из 2-связного списка

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