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

Ранее я писал о том, что такое односвязный линейный список (ОЛС). Однако на практике часто вместо односвязных списков используются так называемые двусвязные линейные списки (ДЛС), о чем и пойдет речь в данной статье. Зачастую использовать ДЛС намного удобнее, правда не всегда. Для таких списков требуется больше памяти, чем для односвязных (в чем мы вскоре убедимся). Так что, если в памяти Вы не ограничены, можете спокойно использовать ДЛС для своих нужд.

Двусвязный список — последовательность элементов, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы.

Так как каждый элемент списка содержит, помимо поля с данными, два указателя, то отсюда вытекает то, что для ДЛС требуется больше памяти.

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

Инициализация
Включение до рабочего указателя
Включение после рабочего указателя
Исключение до рабочего указателя
Исключение после рабочего указателя
Сдвиг рабочего указателя назад (к предыдущему элементу)
Сдвиг рабочего указателя вперед (к следующему элементу)
Установка рабочего указателя в начало списка
Установка рабочего указателя в конец списка
Проверка пустоты списка
Удаление списка

Как и с односвязным списком, в статической памяти будет располагаться дескриптор. Этот дескриптор будет в точности таким же, как и у ОЛС. Единственное отличие — два указателя.

Суть инициализации состоит в том, чтобы создать фиктивные элементы, то есть выделить для них память. Интерес вызывает то, что эти указатели должны указывать друг на друга.

Как видите, суть такая же, как это было с односвязным списком. Остальные операции реализуются по такому же принципу, как и соответствующие операции ОЛС. Как я уже говорил, единственное, нужно заботиться о втором указателе.