Цепная организация данных. Список.

Списком называется множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи.
Адрес связи некоторой записи – атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработка записей в списке определяется возрастанием значений ключа в записях.
Возможны 2 способа организации списка:
-совместное размещение собственной и ассоциативной информации, когда запись и ее адрес связи образуют 1 целое,
-раздельное, когда имеется списковая организация адресов связи и последовательное хранение информации.
При формировании упорядоченного списка возможны 2 варианта:
-вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу,
-создать сначала неупорядоченный список, а потом отсортировать его.
В итоге время формирования упорядоченного списка пропорционально Т~М log M.
Для поиска данных в списках используют единственный метод –последовательный поиск.
Ключевой атрибут первой записи (ее адрес извлекается из указателя списка) сравнивается с искомым значением q, затем такое же сравнение выполняется для ключа второй записи, которая извлекается по адресу связи первой записи, и т.д., время поиска пропорционально Т~М.
Для ускорения доступа к списку могут быть рекомендованы такие варианты использования адресов связи, как двунаправленный и кольцевой список.