Двусвязный и двусвязный циклический списки

В линейном двусвязном списке продвижение возможно в любом из двух направлений по цепочке элементов. Каждый элемент двусвязного списка содержит два указателя: указатель на следующий элемент, или прямой указатель, и указатель на предыдущий элемент, или обратный указатель «рисунок 5». У первого элемента двусвязного списка обратный указатель пустой, а у последнего элемента двусвязного списка — прямой указатель.

Рисунок 5 — Линейный двусвязный список. Логическая структура Линейность такого списка обеспечивается тем, что каждый из двух указателей в любом элементе списка, кроме крайних, задает линейный порядок элементов, обратный по отношению к порядку, устанавливаемому другим указателем рисунок 6.

Рисунок 6 — Линейность двусвязного списка Логическая структура линейного двусвязного списка:

Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель конца списка, указатель текущего элемента списка.

Логическая структура элемента линейного двусвязного списка:

Данные или указатель на данные, указатель на следующий элемент списка, указатель на предыдущий элемент списка.

Рисунок 7 — Кольцевой двусвязный список. Логическая структура Продвижение в линейном двусвязном списке возможно в любом направлении. Операции включения элемента в линейный двусвязный список и исключения элемента из линейного двусвязного списка реализуются аналогично соответствующим операциям над линейным односвязным списком. Результат выполнения операций включения элемента в линейный двусвязный список и исключения элемента из линейного двусвязного списка — линейный двусвязный список.

Для получения из линейного двусвязного списка кольцевого двусвязного списка необходимо два пустых указателя заменить указателями противоположных концов списка рисунок 7.