Двусвязный список — это тип связанного списка, в котором узлы содержат информацию и два указателя, то есть левый указатель и правый указатель. Левый указатель в двусвязном списке указывает на предыдущий узел, а правый указатель указывает на следующий узел в связанном списке. Левый указатель первого узла двусвязного списка имеет значение NULL, а правый указатель последнего узла двусвязного списка имеет значение NULL.
Работа с двусвязным списком
Узел двусвязного списка содержит три поля:
- Левый указатель,
- Информация и
- Правый указатель.
Левый указатель указывает на узел, который находится перед текущим узлом, а правый указатель указывает на узел после текущего узла. Двусвязный список позволяет при необходимости вернуться назад. Все остальные функции аналогичны связному списку.
Применение двусвязного списка:
- Двусвязный список можно использовать в навигационных системах, где требуется как прямой, так и обратный обход.
- Его можно использовать для реализации различных древовидных структур данных.
- Его можно использовать для реализации операций отмены/повтора.
Применение двусвязного списка в реальном времени:
- Двусвязные списки используются для навигации по веб-страницам как в прямом, так и в обратном направлении.
- Его можно использовать в таких играх, как колода карт.
Преимущества двусвязного списка :
- Двусвязный список позволяет перемещаться как в прямом, так и в обратном направлении.
- Удаление узлов может быть сделано легко.
- Обратить связанный список легко.
Недостатки двусвязного списка :
- В двусвязном списке каждый узел имеет дополнительный указатель, который требует дополнительного места.
- Операции с двусвязным списком требуют обработки большего количества указателей, следовательно, больше времени.
- Произвольный доступ к элементам запрещен.
