Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 15 стр.

                    'a'                                       'c'      nil
    L                                    'b'


При этом в программе выражение L означает ссылку на первое звено в цепочке;
L↑ означает само первое звено, L↑.elem – первый элемент списка, L↑.next
– ссылка на второе звено. Далее,
L↑.next↑ – само второе звено,
L↑.next↑.elem – второй элемент списка,
L↑.next↑.next – ссылка на третье звено,
L↑.next↑.next↑ – само третье звено,
L↑.next↑.next↑.elem – третий элемент списка,
L↑.next↑.next↑.next – пустая ссылка (конец списка).
Выражение L имеет и другой смысл. Оно обозначает список в программе,
поскольку, зная ссылку на первое звено, мы имеем доступ ко всем остальным
звеньям, т.е. «знаем» весь список. С этой точки зрения выражение L↑.next в
нашем     примере     обозначает    список1   <'b','c'>,     а   выражение
L↑.next↑.next↑.next – пустой список.
      Подчеркнём, что соседние звенья цепочки располагаются в оперативной
памяти произвольно относительно друг друга, в отличие от соседних компонент
массива, всегда занимающих смежные участки памяти. Такое расположение
звеньев облегчает операции вставки и удаления, так как нет необходимости
перемещать элементы, как это было в случае реализации списков массивами.
Поясним это на примерах.
      Пусть из списка <'a','b','c'>, представленного в программе
переменной L, требуется удалить второй элемент. Для этого достаточно
исключить из цепочки второе звено – «носитель» второго элемента. Изменим
ссылку в поле next первого звена: L↑.next:= L↑.next↑.next. Теперь
после первого звена в цепочке идёт звено, содержащее элемент 'c'.
Получился список <'a','c'>. Чтобы исключённое звено не занимало места в
памяти, его следует уничтожить процедурой dispose, предварительно
запомнив ссылку на него во вспомогательной переменной q. Итак,
окончательное решение таково:
       q:=L↑.next; L↑.next:= L↑.next↑.next; dispose(q).
Покажем на рисунке происходящие после каждого действия изменения.
                          {q:=L↑.next}



                     'a'                                       'c'     nil
    L                                     'b'


    q


1
  По правилам Паскаля имена link и list обозначают один и тот же тип, и мы вправе
рассматривать L↑.next как переменную типа list, означающую список.

                                     - 15 -