В голове списка можно хранить
В голове списка можно хранить различную слу-ясебную информацию, необходимую при обработке списка (идентификатор списка, количество узлов в списке и т. п.).
Важной разновидностью представления в памяти линейного списка является циклический список. Циклически связанный линейный список обладает той особенностью, что связь от последнего узла идет к первому узлу списка (рис. 3.6). Циклический список позволяет получить доступ к любому узлу списка, отправляясь от любого заданного узла. Циклические списки называются также кольцевыми структурами или кольцами.
Рис. 3.6. Пример однонаправленного циклического списка
Наряду с однонаправленными используются двунаправленные циклические списки. В ряде случаев удобно использовать циклический список с указателями на голову списка из каждого узла, за исключением последнего узла, поскольку используется прямой указатель на голову списка [17].
Базируясь на использовании способов представления связанных линейных списков, можно реализовать в памяти ЭВМ сложные нелинейные структуры, например древовидные или сетевые. Такие представления структур называются многосвязанными списками. Для построения многосвязанного списка требуется иметь в узлах достаточное количество указателей. Наличие большого числа указателей в многосвязанной структуре в ряде случаев повышает эффективность обработки.
Таким образом, основой построения связанных списковых структур являются указатели.
При практической реализации на ЭВМ можно использовать три типа указателей (адресов записей):
– машинный (действительный);
– относительный;
– символический (идентификатор).
Первый тип указателей - действительный адрес -используется тогда, когда необходимо получить наибольшую скорость обработки данных, организованных в связанные списковые структуры. Этот тип указателей имеет серьезный недостаток - жесткую привязку записей к конкретному месту расположения в памяти.
