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

ОГЛАВЛЕНИЕ

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

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

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

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

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