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

Снимем теперь допущение, что записи, расположенные по соседству в линейном списке, занимают и соседние места в памяти. Подобное несоответствие между логическим и физическим расположением записей допускается в связанных списках. Связанные линейные списки бывают одно и двух связанные. В одно связанном списке каждая запись имеет одно специальное поле, содержащее указатель на соседнюю запись в списке (рис. 22). Указатель – это адрес соседней записи, пользуясь которым можно найти эту соседнюю запись в памяти. Переменной F может и не быть, т.к. двигаться справа налево мы все равно не сможем. Единственное применение данной переменной – добавление новой записи в конец списка. Указатель    есть пустой указатель. Часто он кодируется помещением в поле указателя нуля.

Рис. 24. Пример линейного одно связанного списка

    В двух связанном списке каждая запись имеет два поля указателей на обе соседние записи (рис. 25).

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

Рис. 25. Двух связанный линейный список

В отличие от несвязанных, связанные списки могут быть нелинейными. Важнейшим видом нелинейных списков является дерево (рис. 26). Запись 1 называется корнем дерева. Записи, у которых нет сыновей, называются листьями. Это – 1.1, 1.2.1, 1.2.2.1, 1.2.2.2, 1.2.3. Совокупность записей, начиная от корня и кончая каким-то листом, называется путем. Пример пути: “1, 1.2, 1.2.1”.

Рис. 26. Пример дерева