5.4.2. Вставка заданного элемента в отсортированный 2-связный список.

Procedure Ins2List ( Var h :u; a :Integer );

Var t, s :u;

Begin t := h; New (s ); s^.i := a;

While t <> Nil Do Цикл поиска и вставки узла в надлежащее место списка}

If a <= t^.i

Then

If t = h { если место вставки найдено }

Then Begin s^.L := Nil; s^.R := h; { вставка в начало списка }

t^.L := s; h := s; Exit;

End

Else Begin s^.L := t^.L; t^.L := s; { вставка в середину списка }

s^.R := t; s^.L^.R := s; Exit;

End

Else If t^.R = Nil {если t указывает на последний элемент,

Then Break { то выход,

Else t := t^.R; иначе продвигаемся вперед}

{ конец цикла While }

If h = Nil

Then Begin h := s; s^.L := Nil; s^.R := Nil; End{ вставка в пустой список }

Else Begin s^.L := t; s^.R := Nil; t^.R := s; End; { вставка в конец списка }

End;

Замечания.

1. Обратите внимание, что Pascal допускает многократное применение операции ^(разыменование) в одном выражении, что позволяет, имея указатель на какой-либо узел, обращаться к полям нескольких соседних узлов, продвигаясь по ссылкам. Такая «косвенная адресация» к различным элементам списка является удобным средством обработки.

2. Часто для ускорения доступа к элементам 2-связного списка его снабжают еще одним указателем h2 на конец списка.

3. В операциях с 2-связными списками удается избавиться от рабочего указателя p на предыдущий элемент.

4. На основе рассмотренных операций над списками можно сделать прос­тые и важные выводы. Если имеется последовательность элементов одного типа, то пред­ставление ее в виде списка особенно удобно в тех ситуациях, когда часто должны выполняться операции удаления и/или вставки произвольных элементов последовательности и когда использу­ется прохождение всего списка. Массивы и файлы, безусловно, хуже списков, если рассматривать операции удаления и/или вставки произволь­ных элементов. Для массивов требуется смеще­ние элементов, а для фай­лов — перезапись. Последовательная обработка массивов происходит не­сколько быстрее, чем последовательная обработка спи­сков, а последова­тельная обработка файлов — медленнее. Массивы имеют определен­ные пре­имущества перед списками при произвольном доступе к элемен­там, осо­бенно эффективен поиск определенного элемента в упорядочен­ном масси­ве. Этот тип поиска в случае списков относится к очень медленному и тре­бует в среднем п/2 обращений к элементам списка и сравнений. Если ожи­да­ется, что элементы будут выбираться из середины или конца списка, то не требу­ется его последовательно просматривать, а нужно хранить несколь­ко указателей на эти части списка.