В деке с ограниченным входом этот путь закрыт

Здесь FIRST — переменная связи, указывающая на первый узел в списке.

Теперь мы можем сопоставить эти две основные формы хранения информации:

1) Связанное распределение требует дополнительного пространства в памяти для связей. В некоторых ситуациях этот фактор может быть доминирующим. Однако мы часто встречаемся с таким положением, когда информация в узле не занимает все слово целиком, и поэтому место для поля связи уже существует. Кроме того, во многих применениях несколько элементов можно объединять в один узел, и, следовательно, потребуется лишь одна связь на несколько элементов информации. Но гораздо важнее тот факт, что при использовании связанной памяти часто возникает неявный выигрыш в памяти, поскольку можно совмещать общие части таблиц; и во многих случаях последовательное распределение не будет столь эффективным, как связанное, если так или иначе не остается пустым довольно большое количество ячеек памяти.

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

3) Если используется связанная схема, то легко включить элемент в список. Например, чтобы включить элемент после 2-го элемента, то необходимо изменить лишь две связи:

Такая операция заняла бы значительное время при работе с длинной последовательной таблицей.

4) При последовательном распределении значительно быстрее выполняются обращения к произвольным частям списка. Доступ к k-му элементу списка, если k — переменная, для последовательного распределения занимает фиксированное время, а для связанного — необходимо k итераций, чтобы добраться до требуемого места. При использовании схемы со связями упрощается задача объединения двух списков или разбиения списка на части.

5) Схема со связями годится для структур более сложных, чем простые линейные списки. У нас может быть переменное количество списков, размер которых непостоянен; любой узел одного списка может быть началом другого списка; в одно и то же время узлы могут быть связаны в несколько последовательностей, соответствующих различным спискам, и т. д.

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