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

Рисунок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.