Энциклопедия Turbo Pascal. Главы 1-4
Страница 24. Связанные списки

Связанные списки

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