Двусвязный список #5

Доброй ночи всем.

В столь поздний час, как ни странно, я хочу рассказать о двусвязных списках (они уже были упомянуты в этой статье).

Двусвязный список — это динамическая структура данных, а именно, он является разновидностью связных списков. Его «двусвязность» заключается в наличии двух ячеек для хранения адресов. В одной хранится адрес следующего элемента, а в другой — предыдущего (привет Кэп :) ). В этом и все отличие от односвязного списка.

Крайний слева элемент так же называется головой, а крайний справа — хвостом.

Вот небольшая иллюстрация двусвязного списка:

 

twolist

Здесь А3 — голова, А1 — хвост. Еще бывают случаи, когда А1 и А3 связаны — такой список называется кольцевым.

circular

Преимущества двусвязного списка перед односвязным заключается в более удобной навигации (перемещении) по списку, при этом элемент двусвязного списка занимает больше памяти, что является минусом (в наши времена этот минус незначителен — вон недавно вышла планка оперативки на 128 ГБ). Наиболее серьезным минусом сабжа является сложная реализация вставки и удаления элементов — это обусловлено тем, что приходится изменять постоянно две ячейки адреса у элементов списка.

Но не так страшен черт, как его малюют. Его реализация на С++ вполне понятна и не должна вызывать недоумения (я надеюсь). Вот, собственно, и она:

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

Вот такие вот пирожки с котятами…

Пример использования класса:

После запуска программы получаем следующее:

 

output

К вышесказанному  добавить особо нечего. Примером использования двусвязного списка является файловая система NTFS, а вот FAT основана на односвязном списке.

На этой ноте мы завершаем увлекательное погружение в динамические структуры.

В следующей статье я расскажу о бинарных деревьях — не пропустите!

До скрой встречи.

Поддержать сайт и автора: Z208212694629
R429062753687
Яндекс деньги - https://money.yandex.ru/to/410013974912682

Подпишись:
На мой канал youtube
На рассылку свежих статей
На группу ВК
На группу в ОК

Понравилась статья? Поделись с друзьями)

Опубликовать в Google Buzz
Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники

Двусвязный список #5: 2 комментария

  1. Уведомление: Указатели? Это просто! С++ #1 | Всего наилучшего — 73!

Добавить комментарий