Вставка элемента в список

Вставка элемента в середину односвязного списка показана на рис.5.4 и в примере 5.2.

Рис.5.4. Вставка элемента в середину 1-связного списка

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

{ Вставка элемента в середину 1-связного списка }

Procedure InsertSll(prev: sllptr; inf: data);

{ prev - адрес предыдущего эл-та; inf - данные нового эл-та }

var cur: sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

cur^.next:=prev^.next; { эл-т, следовавший за предыдущим теперь

будет следовать за новым }

prev^.next:=cur; { новый эл-т следует за предыдущим }

end;

Рисунок 5.5 представляет вставку в двухсвязный список.

Рис.5.5. Вставка элемента в середину 2-связного списка

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

Рис.5.6. Вставка элемента в начало 1-связного списка

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

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

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

Procedure InsertSll

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

процедуре, если head=nil - список пустой }

prev: sllptr; { указатель на эл-т, после к-рого делается вставка,

если prev-nil - вставка перед 1-ым эл-том }

inf: data { - данные нового эл-та }

var cur: sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

if prev <> nil then begin { если есть предыдущий эл-т - вставка в

середину списка, см. прим.5.2 }

cur^.next:=prev^.next; prev^.next:=cur;

end

else begin { вставка в начало списка }

cur^.next:=head; { новый эл-т указывает на бывший 1-й эл-т списка;

если head=nil, то новый эл-т будет и последним эл-том списка }

head:=cur; { новый эл-т становится 1-ым в списке, указатель на

начало теперь указывает на него }

end; end;