На рис. 5.1 приведена структура односвязного списка. На нем
поле INF - информационное поле, данные, NEXT - указатель на сле-
дующий элемент списка. Каждый список должен иметь особый элемент,
называемый указателем начала списка или головой списка, который
обычно по формату отличен от остальных элементов. В поле указате-
ля последнего элемента списка находится специальный признак nil,
свидетельствующий о конце списка.
┌─────────────┬─┐ ┌────┬────┐ ┌────┬────┐ ┌────┬────┐
│голова списка│ ┼──>│INF │NEXT┼────>│INF │NEXT┼──>│INF │nil │
└─────────────┴─┘ └────┴────┘ ... └────┴────┘ └────┴────┘
Рис.5.1. Структура односвязного списка
Однако, обработка односвязного списка не всегда удобна, так
как отсутствует возможность продвижения в противоположную сторо-
ну. Такую возможность обеспечивает двухсвязный список, каждый
элемент которого содержит два указателя: на следующий и предыду-
щий элементы списка. Структура линейного двухсвязного списка при-
ведена на рис. 5.2, где поле NEXT - указатель на следующий эле-
мент, поле PREV - указатель на предыдущий элемент. В крайних эле-
ментах соответствующие указатели должны содержать nil, как и по-
казано на рис. 5.2.
Для удобства обработки списка добавляют еще один особый эле-
мент - указатель конца списка. Наличие двух указателей в каждом
элементе усложняет список и приводит к дополнительным затратам
памяти, но в то же время обеспечивает более эффективное выполне-
ние некоторых операций над списком.
┌─┬─────────────┐ ┌───────────────┬─┐
│ │голова списка│ │указатель конца│ │
└┼┴─────────────┘ └───────────────┴┼┘
│ ┌────┬───┬────┐ ┌────┬───┬────┐ └─>┌────┬───┬────┐
└>│ │ │ ─┼────>│ │ │ ─┼───>│ │ │ │
│nil │INF│NEXT│ │PREV│INF│NEXT│ │PREV│INF│ nil│
│ │ │ │<────┼─ │ │ │<───┼─ │ │ │
└────┴───┴────┘ ... └────┴───┴────┘ └────┴───┴────┘
Рис.5.2. Структура двухсвязного списка
Разновидностью рассмотренных видов линейных списков является
кольцевой список, который может быть организован на основе как
односвязного, так и двухсвязного списков. При этом в односвязном
списке указатель последнего элемента должен указывать на первый
элемент; в двухсвязном списке в первом и последнем элементах со-
ответствующие указатели переопределяются, как показано на
рис.5.3.
При работе с такими списками несколько упрощаются некоторые
процедуры, выполняемые над списком. Однако, при просмотре такого
списка следует принять некоторых мер предосторожности, чтобы не
попасть в бесконечный цикл.
┌─┬─────────────┐
│ │голова списка│
└┼┴─────────────┘ ┌────────────────┐
┌───┘ │ │
└>┌────┬───┬────┐ ┌────┬───┬────┐ └>┌────┬───┬────┐│
┌>│ │ │ ─┼─> ─>│ │ │ ─┼───>│ │ │ ─┼┼┐
│ │PREV│INF│NEXT│ ... │PREV│INF│NEXT│ │PREV│INF│NEXT│││
│┌┼─ │ │ │<─ <─┼─ │ │ │<───┼─ │ │ │││
││└────┴───┴────┘ └────┴───┴────┘ └────┴───┴────┘││
│└──────────────────────────────────────────────────────────┘│
└────────────────────────────────────────────────────────────┘
Рис.5.3. Структура кольцевого двухсвязного списка
В памяти список представляет собой совокупность дескриптора
и одинаковых по размеру и формату записей,
размещенных произвольно в некоторой области памяти и связанных
друг с другом в линейно упорядоченную цепочку с помощью указате-
лей. Запись содержит информационные поля и поля ука-
зателей на соседние элементы списка, причем некоторыми полями ин-
формационной части могут быть указатели на блоки памяти с
дополнительной информацией, относящейся к элементу списка. Деск-
риптор списка реализуется в виде особой записи и содержит такую
информацию о списке, как адрес начала списка, код структуры, имя
списка, текущее число элементов в списке, описание элемента и
т.д., и т.п. Дескриптор может находиться в той же области памяти,
в которой располагаются элементы списка, или для него выделяется
какое-нибудь другое место.