2) Операция удаления элемента в связанном списке выполняется проще. Например, для удаления элемента 3 необходимо только изменить связь с ним в элементе 2. А при последовательном выделении памяти такое удаление в общем случае подразумевает перемещение значительной части списка в другие ячейки.

3) При использовании схемы связанного распределения памяти проще выполняется и вставка элемента в середину списка. Например, для вставки элемента 2 в список (1) потребуется изменить только две связи.

FIRST -> ЭлементТ" »- -> Элемент 2 ♦ Элемент 3 »- -> Элемент 4 *- -Ц Элемент 5 J

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

4) Обращения к произвольным элементам списка гораздо быстрее осуществляются при последовательном выделении памяти. Для доступа к fc-му элементу списка, где fc - некоторая переменная, в случае последовательного распределения памяти потребуется фиксированное время, но для доступа к нужному элементу в случае связанного распределения памяти потребуется выполнить fc итераций. Таким образом, полезность связанного распределения памяти основывается на том, что в большинстве приложений доступ к элементам списка вьшолняется в последовательном, а не произвольном порядке. Для доступа к элементам в середине или в конце списка можно создать дополнительную переменную связь или целый список переменных связи, которые указывают на нужные позиции списка.

5) В схеме связанного распределения памяти проще организовать объединение двух списков или разбиение списка на два других списка, которые могут увеличиваться независимо.

6) Схема связанного распределения памяти прекрасно подходит для организации более сложных структур, чем простые линейные списки. Например, ее можно применить для создания переменного количества списков переменного размера. Причем каждый узел одного из них может быть началом другого списка, к тому же узлы могут быть связаны между собой несколькими способами и образовывать другие списки и т. д.

7) Такие простые операции, как последовательная обработка элементов списка, на многих компьютерах выполняется немного быстрее. Для компьютера MIX операторы INC1 с и LD1 0,1 (LINK) отличаются только одним тактом, но на многих компьютерах не реализована возможность загрузки индексного регистра из индексированной ячейки. Если элементы связанного списка принадлежат разным страницам устройства хранения большого объема, то операция доступа к ним может выполняться значительно дольше.

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

в следующих нескольких примерах предположим для удобства, что узел состоит из одного слова, которое содержит два поля- INFO и LINK:

INFO

I-I 1-

LINK

При использовании связанного распределения памяти обычно подразумевается, что существует некоторый механизм поиска свободного места для нового узла при вставке новых данных в список. Это обычно выполняется с помощью специального списка свободного пространства. Здесь он будет называться списком AVAIL (или стеком AVAIL, поскольку он обычно обрабатывается, как стек магазинного типа, т. е. по принципу "последним вошел - первым вышел" (last-in-first-out)). Набор всех неиспользуемых в данный момент узлов связан в список, который устроен так же, как и все другие списки. Переменная связи AVAIL ссылается на самый верхний элемент этого списка. Таким образом, если необходимо присвоить переменной связи X адрес нового узла, а сам узел зарезервировать для дальнейшего использования, то можно выполнить следующие действия:

X <г- AVAIL, AVAIL 4- LINK(AVAIL). (4)

При этом из стека AVAIL будет удален самый верхний элемент, а X будет указывать на только что удаленный узел. Операция (4) в дальнейшем будет использоваться настолько часто, что для нее лучше ввести специальное обозначение: X <= AVAIL будет означать, что X указывает на новый узел.

Для удаления ненужного узла операцию (4) можно обратить:

LINK(X) <- AVAIL, AVAIL X. (5)

При этом узел с адресом, указанным с помощью X, будет возвращен в список свободного пространства, а вся операция (5) будет обозначаться как AVAIL •<= X.

При обсуждении правил работы со стеком AVAIL были опущены некоторые важные подробности. Например, ничего не было сказано о его создании после запуска программы. Очевидно, что стек может быть создан следующим образом: (а) за счет связывания всех узлов, которые предполагается использовать для организации связанной памяти, (Ь) путем присвоения адреса первого из этих узлов переменной связи AVAIL и (с) в результате присвоения значения Л связи последнего узла. Набор всех выделенных таким образом узлов называется пулом {storage pool).

Однако самой важной особенностью новой структуры является проверка переполнения. В операции (4) не предусмотрена проверка ситуации, когда в памяти исчерпано все свободное пространство. На самом деле для этого операция X AVAIL должна быть определена иначе:

Если AVAIL = Л, то OVERFLOW;

в противном случае X <- AVAIL, AVAIL <r- LINK(AVAIL). (6)

Возможность переполнения должна быть предусмотрена всегда! В данной ситуации переполнение (OVERFLOW) означает либо прекращение работы программы (к сожалению), либо запуск процедуры "сборки мусора" (garbage collection), которая предпримет попытку поиска свободного пространства. Сборка мусора более подробно описывается в разделе 2.3.5.

Для управления стеком AVAIL можно использовать другую технологию, поскольку часто заранее неизвестно, какой объем памяти потребуется для пула. Для этого можно применить подледовательную таблицу переменного размера, которая может сосуществовать в памяти вместе со связанными таблицами. В таком случае нужно позаботиться о том, чтобы связанная область памяти не занимала больше места, чем необходимо. Предположим, что связанная область памяти размещается в ячейках с возрастающими адресами, начиная с Lq, и что эта область никогда не выходит за пределы величины SEQMIN (которая представляет собой текушую нижнюю границу для последовательной таблицы). В таком случае в результате применения новой переменной POOLMAX происходит следующее.

a) Вьшолняется установка AVAIL Л и POOLMAX Lq.

b) Операция X AVAIL теперь выглядит так:

Если AVAIL ф А, тот (г- AVAIL, AVAIL Ч- LINK(AVAIL); иначе X POOLMAX и POOLMAX ч- X -f- с, где с - размер узла; OVERFLOW имеет место, если POOLMAX > SEQMIN.

c) Другие части программы при попытках уменьшить значение SEQMIN подают сигнал о переполнении (OVERFLOW), если SEQMIN < POOLMAX.

d) Операция AVAIL •<= X остается неизменной, т. е. такой же, как и в (5).

Эта идея на самом деле представляет собой просто вставку специальной процедуры восстановления, используемой при переполнении (OVERFLOW) в условии (6). Суммарный результат заключается в поддержании пула наименьшего размера. Многие склонны использовать эту идею, даже если все списки находятся в пуле (так что величина SEQMIN остается постоянной), поскольку с ее помощью можно избежать очень неэкономной операции исходного связывания всех ячеек и к тому же упростить отладку. Кроме того, последовательный список можно разместить снизу, а пул - сверху, используя POOLMIN и SEQMAX вместо POOLMAX и SEQMIN.

Следовательно, в пуле свободных узлов довольно просто и эффективно можно выполнять поиск и возврат свободных узлов. Описанные методы предоставляют возможность получить материал для использования в связанных таблицах. Эти рассуждения основаны на неявном предположении о том, что все узлы имеют одинаковый размер, с, хотя большое значение имеют также случаи с узлами разных размеров. Их рассмотрение будет продолжено в разделе 2.5. Теперь опишем несколько наиболее общих операций со списками при работе со стеками и очередями.

Простейшим типом связанного списка является стек. На рис. 5 показан типичный стек с указателем Т на верхний элемент стека. Когда стек пуст, этот указатель имеет значение Л.

Теперь ясно, какие операции следует выполнить для вставки ("проталкивания") нового элемента данных Y сверху такого стека, используя вспомогательный указатель Р:

Рис. 5. Связанный стек.

Р AVAIL, INFO(P) Ч- У, LINK(P) <- Т,