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

d0b4d0b2d183d181d0b2d18fd0b7d0bdd18bd0b9 d181d0bfd0b8d181d0bed0ba d180d0b5d0b0d0bbd0b8d0b7d0b0d186d0b8d18f d0bdd0b0 c статьи

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

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

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

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

  1. Инициализация
  2. Включение до рабочего указателя
  3. Включение после рабочего указателя
  4. Исключение до рабочего указателя
  5. Исключение после рабочего указателя
  6. Сдвиг рабочего указателя назад (к предыдущему элементу)
  7. Сдвиг рабочего указателя вперед (к следующему элементу)
  8. Установка рабочего указателя в начало списка
  9. Установка рабочего указателя в конец списка
  10. Проверка пустоты списка
  11. Удаление списка

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

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

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

Файл "List_Two.h"

Файл "List_Two.с"

Вот и все! Надеюсь все было доступно изложено. Если возникнут вопросы, Вы можете задать их в комментариях в конце статьи. Удачи!

Оцените статью
Секреты программирования
Добавить комментарий