Двусвязный список структуры данных в C++

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

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

Двусвязный список, как и односвязный список имеет начало и конец. Предыдущему указателю заголовка присваивается значение NULL, поскольку это первый узел. Следующему указателю конечного узла присваивается значение NULL, поскольку это последний узел.

Базовая компоновка двусвязного списка показана на схеме ниже:

Базовая компоновка двусвязного списка

На приведенной выше схеме видно, что каждый узел имеет два указателя, один из которых указывает на предыдущий узел, а другой указывает на следующий узел. Только для первого узла (head) предыдущему узлу присвоено значение null, а для последнего узла (tail) следующему указателю присвоено значение null.

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

Объявление

В объявлении в стиле C++ узел двусвязного списка представлен следующим образом:

Помимо приведенного выше объявления, мы также можем представить узел в двусвязном списке как класс в C ++. Двусвязный список представляется в виде класса, когда мы используем STL в C ++. Мы также можем реализовать двусвязный список, используя класс в Java.

Основные операции

Ниже приведены некоторые операции, которые мы можем выполнить с двусвязным списком:

Вставка

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

  • Вставка спереди – вставляет новый узел в качестве первого узла.
  • Вставка в конце – вставляет новый узел в конце как последний узел.
  • Вставка перед узлом – учитывая узел, вставляет новый узел перед этим узлом.
  • Вставка после узла – учитывая узел, вставляет новый узел после этого узла.

Читать также:  Моделирование робота с дифференциальным приводом

Удаление

Операция удаления удаляет узел из заданной позиции в двусвязном списке:

  • Удаление первого узла – удаляет первый узел в списке.
  • Удаление последнего узла – удаляет последний узел в списке.
  • Удаление узла с учетом данных – учитывая данные, операция сопоставляет данные с данными узла в связном списке и удаляет этот узел.

Обход

Обход — это метод посещения каждого узла в связном списке. В двусвязном списке есть два типа обходов, поскольку у нас есть два указателя с разными направлениями в двусвязном списке.

  • Прямой обход – обход выполняется с использованием следующего указателя, который находится в прямом направлении.
  • Обратный обход – обход выполняется с использованием предыдущего указателя, который является обратным направлением.

Реверс

Эта операция меняет местами узлы в двусвязном списке, так что первый узел становится последним узлом, а последний узел становится первым узлом.

Поиск

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

Вставка

Схема вставки узла спереди:

Вставка узла спереди

Вставка нового узла в начало списка показана выше. Как видно, предыдущему новому узлу N присвоено значение null. Заголовок указывает на новый узел. Следующий указатель N теперь указывает на N1, а предыдущий указатель N1, который ранее указывал на Null, теперь указывает на N.

Схема вставки узла в конец:

Вставка узла в конец

Вставка узла в конец двусвязного списка достигается путем указания следующего указателя нового узла N на значение null. Предыдущий указатель N указывает на N5. ‘Следующий’ указатель N5 указывает на N.

Схема вставка узла до / после заданного узла:

Вставка узла до и после заданного узла

Как показано на приведенной выше схеме, когда нам нужно добавить узел до или после определенного узла, мы изменяем предыдущий и следующий указатели узлов before и after, чтобы соответствующим образом указывать на новый узел. Кроме того, новые указатели узлов соответствующим образом указывают на существующие узлы.

Читать также:  Конструкции принятия решений в C++

Следующая программа на C ++ демонстрирует все вышеупомянутые методы для вставки узлов в двусвязный список:

Вывод данных:

Двусвязный список выглядит следующим образом:
10<==>20<==>30<==>40<==>50<==> NULL

Приведенная выше программа создает двусвязный список путем вставки узлов с использованием трех методов вставки, т.е. вставки узла спереди, вставки узла в конце и вставки узла после заданного узла.

Далее мы продемонстрируем ту же программу, но на языке Java:

Вывод данных:

Созданный двусвязный список выглядит следующим образом:
10<==>20<==>30<==>40<==>50<==> NULL

Удаление

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

При удалении узла из двусвязного списка мы сначала перемещаем указатель, указывающий на этот конкретный узел, чтобы предыдущий и последующие узлы не имели никакой связи с удаляемым узлом. Затем мы можем легко удалить узел.

Рассмотрим следующий двусвязный список с тремя узлами A, B, C. Предположим, что нам нужно удалить узел B:

Двусвязный список с тремя узлами A, B, C

В приведенной выше схеме, мы продемонстрировали удаление узла B из данного связного списка. Последовательность операций остается неизменной, даже если узел является первым или последним. Единственное, что следует предпринять, это то, что если в случае удаления первого узла предыдущий указатель второго узла будет установлен в значение null.

Аналогично, когда последний узел удаляется, следующему указателю предыдущего узла присваивается значение null. Если промежуточные узлы удалены, то последовательность будет такой, как указано выше.

Реверс двусвязного списка

Реверс или переворачивание двусвязного списка является важной операцией. Мы просто меняем местами предыдущий и следующий указатели всех узлов, а также меняем местами головной и конечный указатели.

Читать также:  Карты в STL

Ниже приведен двусвязный список:

Реверс двусвязного списка

Следующая программа на C ++ показывает реверс двусвязного списка:

Вывод данных:

Оригинальный двусвязный список:
1 <==> 2 <==> 3 <==> 4 <==> 5
Перевернутый двусвязный список:
5 <==> 4 <==> 3 <==> 2 <==> 1

В программе мы меняем местами левый и правый указатели и перемещаем их навстречу друг другу, пока они не встретятся или не пересекутся. Затем первый и последний узлы меняются местами.

Следующая программа реализована на Java. В этой программе мы также используем замену левого и правого узлов, как мы делали в предыдущей программе:

Вывод данных:

Оригинальный двусвязный список:
1 <==> 2 <==> 3 <==> 4 <==> 5
Перевернутый двусвязный список:
5 <==> 4 <==> 3 <==> 2 <==> 1

Преимущества и недостатки двусвязного списка по сравнению с односвязным списком

Давайте обсудим некоторые преимущества и недостатки двусвязного списка по сравнению с односвязным списком.

Преимущества:

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

Недостатки:

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

Поскольку присутствуют два указателя, т.е. предыдущий и следующий, все операции, выполняемые над двусвязным списком, должны обрабатывать эти указатели и поддерживать их, что приводит к меньшей эффективности в производительности.

Итог

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

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

В нашей следующей статье мы расскажем о циклическом (кольцевом) связном списке.

С Уважением, МониторБанк

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