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

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

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

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

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

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

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

Объявление

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

struct node
{
 struct node *prev;
 int data;
 struct node *next;
};

struct node

{

struct node *prev;

int data;

struct node *next;

};

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

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

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

Вставка

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

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

Читать также: Полиморфизм в С++

Удаление

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

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

Обход

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

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

Реверс

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

Поиск

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

Вставка

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

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

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

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

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

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

Читать также: Шаблоны в C++ с примерами

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

#include <iostream>
using namespace std;
  
// Узел двусвязного списка
struct Node {
   int data;
   struct Node* next;
   struct Node* prev;
};
  
//вставляет узел в начало списка
void insert_front(struct Node** head, int new_data)
{
   //выделение памяти для нового узла
   struct Node* newNode = new Node;
  
   //назначить данные новому узлу
   newNode->data = new_data;
  
   //новый узел является головным, а предыдущий равен нулю, так как мы добавляем узел спереди
   newNode->next = (*head);
   newNode->prev = NULL;
  
   //предыдущий из head - это новый узел
   if ((*head) != NULL)
   (*head)->prev = newNode;
  
   //заголовок указывает на новый узел
   (*head) = newNode;
}
/* Учитывая узел как prev_node, вставить новый узел после данного узла */
void insert_After(struct Node* prev_node, int new_data)
{
   //проверить, является ли предыдущий узел нулевым
   if (prev_node == NULL) {
   cout<<"Previous node is required , it cannot be NULL";
   return;
}
   //выделение памяти для нового узла
   struct Node* newNode = new Node;
  
   //назначить данные новому узлу
   newNode->data = new_data;
  
   //установить следующий из нового узла на следующий из предыдущего узла
   newNode->next = prev_node->next;
  
   //установить следующий из предыдущих узлов на новый узел
   prev_node->next = newNode;
  
   //установить prev нового узла на предыдущий узел
   newNode->prev = prev_node;
  
   //установить prev нового узла рядом с новым узлом
   if (newNode->next != NULL)
   newNode->next->prev = newNode;
}
  
//вставить новый узел в конец списка
void insert_end(struct Node** head, int new_data)
{
   //выделение памяти для узла
   struct Node* newNode = new Node;
  
   struct Node* last = *head; //установить значение последнего узла в head
  
   //набор данных для нового узла
   newNode->data = new_data;
  
   //новый узел является последним узлом, поэтому установить значение next of new node равным null
   newNode->next = NULL;
  
   //проверить, пуст ли список, если да, сделать новый узел главой списка
   if (*head == NULL) {
   newNode->prev = NULL;
   *head = newNode;
    return;
}
  
//в противном случае пройтись по списку, чтобы перейти к последнему узлу
while (last->next != NULL)
last = last->next;
  
//установить предпоследний на новый узел
last->next = newNode;
  
//установить last в prev нового узла
newNode->prev = last;
return;
}
  
// Эта функция выводит содержимое связного списка, начиная с данного узла
void displayList(struct Node* node) {
   struct Node* last;
  
   while (node != NULL) {
      cout<<node->data<<"<==>";
      last = node;
      node = node->next;
   }
   if(node == NULL)
   cout<<"NULL";
   }
  
//основная программа
int main() {
   /* Начать с пустого списка */
   struct Node* head = NULL;
  
   // Вставить 40 в качестве последнего узла
   insert_end(&head, 40);
  
   // вставить 20 в head
   insert_front(&head, 20);
  
   // Вставить 10 в начало.
   insert_front(&head, 10);
  
   // Вставить 50 в конец.
   insert_end(&head, 50);
  
   // Вставить 30, после 20.
   insert_After(head->next, 30);
  
   cout<<"Doubly linked list is as follows: "<<endl;
   displayList(head);
   return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

#include <iostream>

using namespace std;

// Узел двусвязного списка

struct Node {

int data;

struct Node* next;

struct Node* prev;

};

//вставляет узел в начало списка

void insert_front(struct Node** head, int new_data)

{

//выделение памяти для нового узла

struct Node* newNode = new Node;

//назначить данные новому узлу

newNode->data = new_data;

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

newNode->next = (*head);

newNode->prev = NULL;

//предыдущий из head - это новый узел

if ((*head) != NULL)

(*head)->prev = newNode;

//заголовок указывает на новый узел

(*head) = newNode;

}

/* Учитывая узел как prev_node, вставить новый узел после данного узла */

void insert_After(struct Node* prev_node, int new_data)

{

//проверить, является ли предыдущий узел нулевым

if (prev_node == NULL) {

cout<<"Previous node is required , it cannot be NULL";

return;

}

//выделение памяти для нового узла

struct Node* newNode = new Node;

//назначить данные новому узлу

newNode->data = new_data;

//установить следующий из нового узла на следующий из предыдущего узла

newNode->next = prev_node->next;

//установить следующий из предыдущих узлов на новый узел

prev_node->next = newNode;

//установить prev нового узла на предыдущий узел

newNode->prev = prev_node;

//установить prev нового узла рядом с новым узлом

if (newNode->next != NULL)

newNode->next->prev = newNode;

}

//вставить новый узел в конец списка

void insert_end(struct Node** head, int new_data)

{

//выделение памяти для узла

struct Node* newNode = new Node;

struct Node* last = *head; //установить значение последнего узла в head

//набор данных для нового узла

newNode->data = new_data;

//новый узел является последним узлом, поэтому установить значение next of new node равным null

newNode->next = NULL;

//проверить, пуст ли список, если да, сделать новый узел главой списка

if (*head == NULL) {

newNode->prev = NULL;

*head = newNode;

return;

}

//в противном случае пройтись по списку, чтобы перейти к последнему узлу

while (last->next != NULL)

last = last->next;

//установить предпоследний на новый узел

last->next = newNode;

//установить last в prev нового узла

newNode->prev = last;

return;

}

// Эта функция выводит содержимое связного списка, начиная с данного узла

void displayList(struct Node* node) {

struct Node* last;

while (node != NULL) {

cout<<node->data<<"<==>";

last = node;

node = node->next;

}

if(node == NULL)

cout<<"NULL";

}

//основная программа

int main() {

/* Начать с пустого списка */

struct Node* head = NULL;

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

insert_end(&head, 40);

// вставить 20 в head

insert_front(&head, 20);

// Вставить 10 в начало.

insert_front(&head, 10);

// Вставить 50 в конец.

insert_end(&head, 50);

// Вставить 30, после 20.

insert_After(head->next, 30);

cout<<"Doubly linked list is as follows: "<<endl;

displayList(head);

return 0;

}

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

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

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

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

// Класс Java для двусвязного списка
class Doubly_linkedList {
   Node head; // list head
  
    /* Узел двусвязного списка*/
   class Node {
      int data;
      Node prev;
      Node next;
  
      //создайте новый узел с помощью конструктора
      Node(int d) { data = d; }
   }
  
// вставьте узел в начало списка
public void insert_front(int new_data)
{
   /* 1. выделить узел
   * 2. введите данные */
   Node new_Node = new Node(new_data);
  
   /* 3. Сделайте следующий из нового узла заголовком, а предыдущий - нулевым */
   new_Node.next = head;
   new_Node.prev = null;
  
   /* 4. измените предыдущее значение головного узла на новый узел */
   if (head != null)
   head.prev = new_Node;
  
   /* 5. переместите head, чтобы указать на новый узел */
   head = new_Node;
}
//вставьте узел после заданного предыдущего узла
public void Insert_After(Node prev_Node, int new_data)
{
   //убедитесь, что предыдущий узел не равен нулю
   if (prev_Node == null) {
   System.out.println("The previous node is required,it cannot be NULL ");
   return;
}
  
   //выделите новый узел и установите для него значение data
   Node newNode = new Node(new_data);
  
   //установите следующий из newNode в качестве следующего из предыдущего узла
   newNode.next = prev_Node.next;
  
   //установите новый узел следующим за предыдущим узлом
   prev_Node.next = newNode;
  
   //установите prev нового узла в качестве предыдущего узла
   newNode.prev = prev_Node;
  
   //установите prev нового узла рядом с newnode
   if (newNode.next != null)
   newNode.next.prev = newNode;
}
  
// Добавьте узел в конец списка
void insert_end(int new_data)   {
   //выделите узел и задайте данные
   Node newNode = new Node(new_data);
   Node last = head; //установите последнюю в качестве head
   //установите для следующего нового узла значение null, так как это последний узел
   newNode.next = null;
  
   //установите новый узел в качестве заголовка, если список равен null
   if (head == null) {
      newNode.prev = null;
      head = newNode;
      return;
   }
   //если список не равен нулю, то пройдите по нему до последнего узла и установите last рядом с last
   while (last.next != null)
   last = last.next;
  
   last.next = newNode;           //установите последний рядом с новым узлом
  
   newNode.prev = last;           //установите last как предыдущий для нового узла
}
// отображение содержимого связанного списка, начиная с данного узла
public void displaylist(Node node)
{
   Node last = null;
   while (node != null) {
      System.out.print(node.data + "<==>");
      last = node;
      node = node.next;
   }
   if(node == null)
   System.out.print("null");
   System.out.println();
  
   }
}
class Main{
   public static void main(String[] args)
      {
      /* Начните с пустого списка */
      Doubly_linkedList dll = new Doubly_linkedList();
  
      // Вставка 40.
      dll.insert_end(40);
  
      // Вставить 20 в начало.
      dll.insert_front(20);
  
      // Вставить 10 в начало.
      dll.insert_front(10);
  
      // Вставьте 50 в конец.
      dll.insert_end(50);
  
      // Вставить 30, после 20.
      dll.Insert_After(dll.head.next, 30);
  
      System.out.println("Doubly linked list created is as follows: ");
      dll.displaylist(dll.head);
      }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

// Класс Java для двусвязного списка

class Doubly_linkedList {

Node head; // list head

/* Узел двусвязного списка*/

class Node {

int data;

Node prev;

Node next;

//создайте новый узел с помощью конструктора

Node(int d) { data = d; }

}

// вставьте узел в начало списка

public void insert_front(int new_data)

{

/* 1. выделить узел

* 2. введите данные */

Node new_Node = new Node(new_data);

/* 3. Сделайте следующий из нового узла заголовком, а предыдущий - нулевым */

new_Node.next = head;

new_Node.prev = null;

/* 4. измените предыдущее значение головного узла на новый узел */

if (head != null)

head.prev = new_Node;

/* 5. переместите head, чтобы указать на новый узел */

head = new_Node;

}

//вставьте узел после заданного предыдущего узла

public void Insert_After(Node prev_Node, int new_data)

{

//убедитесь, что предыдущий узел не равен нулю

if (prev_Node == null) {

System.out.println("The previous node is required,it cannot be NULL ");

return;

}

//выделите новый узел и установите для него значение data

Node newNode = new Node(new_data);

//установите следующий из newNode в качестве следующего из предыдущего узла

newNode.next = prev_Node.next;

//установите новый узел следующим за предыдущим узлом

prev_Node.next = newNode;

//установите prev нового узла в качестве предыдущего узла

newNode.prev = prev_Node;

//установите prev нового узла рядом с newnode

if (newNode.next != null)

newNode.next.prev = newNode;

}

// Добавьте узел в конец списка

void insert_end(int new_data) {

//выделите узел и задайте данные

Node newNode = new Node(new_data);

Node last = head; //установите последнюю в качестве head

//установите для следующего нового узла значение null, так как это последний узел

newNode.next = null;

//установите новый узел в качестве заголовка, если список равен null

if (head == null) {

newNode.prev = null;

head = newNode;

return;

}

//если список не равен нулю, то пройдите по нему до последнего узла и установите last рядом с last

while (last.next != null)

last = last.next;

last.next = newNode; //установите последний рядом с новым узлом

newNode.prev = last; //установите last как предыдущий для нового узла

}

// отображение содержимого связанного списка, начиная с данного узла

public void displaylist(Node node)

{

Node last = null;

while (node != null) {

System.out.print(node.data + "<==>");

last = node;

node = node.next;

}

if(node == null)

System.out.print("null");

System.out.println();

}

class Main{

public static void main(String[] args)

{

/* Начните с пустого списка */

Doubly_linkedList dll = new Doubly_linkedList();

// Вставка 40.

dll.insert_end(40);

// Вставить 20 в начало.

dll.insert_front(20);

// Вставить 10 в начало.

dll.insert_front(10);

// Вставьте 50 в конец.

dll.insert_end(50);

// Вставить 30, после 20.

dll.Insert_After(dll.head.next, 30);

System.out.println("Doubly linked list created is as follows: ");

dll.displaylist(dll.head);

}

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

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

Удаление

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

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

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

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

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

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

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

Читать также: Множество в STL

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

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

#include <iostream>
using namespace std;
//объявление узла для двусвязного списка
struct Node {
   int data;
   struct Node *prev, *next;
};
  
Node* newNode(int val)
{
   Node* temp = new Node;
   temp->data = val;
   temp->prev = temp->next = nullptr;
   return temp;
}
void displayList(Node* head)
{
   while (head->next != nullptr) {
      cout << head->data << " <==> ";
      head = head->next;
      }
   cout << head->data << endl;
}
  
// Вставьте новый узел в начало списка
void insert(Node** head, int node_data)
{
   Node* temp = newNode(node_data);
   temp->next = *head;
   (*head)->prev = temp;
   (*head) = temp;
}
  
// переверните двусвязный список
void reverseList(Node** head)
{
   Node* left = *head, * right = *head;
  
   // пройдите по всему списку и установите прямо рядом с правой
   while (right->next != nullptr)
   right = right->next;
  
   //меняйте местами левые и правые данные, перемещая их навстречу друг другу, пока они не встретятся или не пересекутся
   while (left != right && left->prev != right) {
  
      // Поменяйте местами данные указателя влево и вправо
      swap(left->data, right->data);
  
      // Продвинуть левый указатель
      left = left->next;
  
      // Продвинуть правый указатель
      right = right->prev;
   }
}
int main()
{
   Node* headNode = newNode(5);
   insert(&headNode, 4);
   insert(&headNode, 3);
   insert(&headNode, 2);
   insert(&headNode, 1);
   cout << "Original doubly linked list: " << endl;
   displayList(headNode);
   cout << "Reverse doubly linked list: " << endl;
   reverseList(&headNode);
   displayList(headNode);
  
   return 0;
}

#include <iostream>

using namespace std;

//объявление узла для двусвязного списка

struct Node {

int data;

struct Node *prev, *next;

};

Node* newNode(int val)

{

Node* temp = new Node;

temp->data = val;

temp->prev = temp->next = nullptr;

return temp;

}

void displayList(Node* head)

{

while (head->next != nullptr) {

cout << head->data << " <==> ";

head = head->next;

}

cout << head->data << endl;

}

// Вставьте новый узел в начало списка

void insert(Node** head, int node_data)

{

Node* temp = newNode(node_data);

temp->next = *head;

(*head)->prev = temp;

(*head) = temp;

}

// переверните двусвязный список

void reverseList(Node** head)

{

Node* left = *head, * right = *head;

// пройдите по всему списку и установите прямо рядом с правой

while (right->next != nullptr)

right = right->next;

//меняйте местами левые и правые данные, перемещая их навстречу друг другу, пока они не встретятся или не пересекутся

while (left != right && left->prev != right) {

// Поменяйте местами данные указателя влево и вправо

swap(left->data, right->data);

// Продвинуть левый указатель

left = left->next;

// Продвинуть правый указатель

right = right->prev;

}

int main()

{

Node* headNode = newNode(5);

insert(&headNode, 4);

insert(&headNode, 3);

insert(&headNode, 2);

insert(&headNode, 1);

cout << "Original doubly linked list: " << endl;

displayList(headNode);

cout << "Reverse doubly linked list: " << endl;

reverseList(&headNode);

displayList(headNode);

return 0;

}

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

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

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

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

// Java-программа для обратного преобразования двусвязного списка с использованием обмена данными
class Main{
static class Node {
   int data;
   Node prev, next;
};
  
static Node newNode(int new_data)  {
   Node temp = new Node();
   temp.data = new_data;
   temp.prev = temp.next = null;
   return temp;
}
  
static void displayList(Node head)  {
   while (head.next != null)  {
   System.out.print(head.data+ " <==> ");
   head = head.next;
}
System.out.println( head.data );
}
  
// Вставьте новый узел в начало списка
static Node insert(Node head, int new_data)  {
   Node temp = newNode(new_data);
   temp.next = head;
   (head).prev = temp;
   (head) = temp;
   return head;
}
  
// Функция для изменения списка в обратном порядке
static Node reverseList(Node head)  {
    Node left = head, right = head;
   // пройдитесь по списку, установите правый указатель в конец списка
   while (right.next != null)
   right = right.next;
   // перемещайте указатели влево и вправо и меняйте местами их данные, пока они не встретятся или не пересекутся друг с другом
   while (left != right && left.prev != right)   {
   // Обмен данными левого и правого указателей
   int t = left.data;
   left.data = right.data;
   right.data = t;
  
   left = left.next;                        // Продвинуть левый указатель
   right = right.prev;                    // Продвинуть правый указатель
   }
return head;
}
public static void main(String args[])
   {
   Node headNode = newNode(5);
   headNode = insert(headNode, 4);
   headNode = insert(headNode, 3);
   headNode = insert(headNode, 2);
   headNode = insert(headNode, 1);
  
   System.out.println("Original doubly linked list:");
   displayList(headNode);
   System.out.println("Reversed doubly linked list:");
   headNode=reverseList(headNode);
   displayList(headNode);
  
   }
}

// Java-программа для обратного преобразования двусвязного списка с использованием обмена данными

class Main{

static class Node {

int data;

Node prev, next;

};

static Node newNode(int new_data) {

Node temp = new Node();

temp.data = new_data;

temp.prev = temp.next = null;

return temp;

}

static void displayList(Node head) {

while (head.next != null) {

System.out.print(head.data+ " <==> ");

head = head.next;

}

System.out.println( head.data );

}

// Вставьте новый узел в начало списка

static Node insert(Node head, int new_data) {

Node temp = newNode(new_data);

temp.next = head;

(head).prev = temp;

(head) = temp;

return head;

}

// Функция для изменения списка в обратном порядке

static Node reverseList(Node head) {

Node left = head, right = head;

// пройдитесь по списку, установите правый указатель в конец списка

while (right.next != null)

right = right.next;

// перемещайте указатели влево и вправо и меняйте местами их данные, пока они не встретятся или не пересекутся друг с другом

while (left != right && left.prev != right) {

// Обмен данными левого и правого указателей

int t = left.data;

left.data = right.data;

right.data = t;

left = left.next; // Продвинуть левый указатель

right = right.prev; // Продвинуть правый указатель

}

return head;

}

public static void main(String args[])

{

Node headNode = newNode(5);

headNode = insert(headNode, 4);

headNode = insert(headNode, 3);

headNode = insert(headNode, 2);

headNode = insert(headNode, 1);

System.out.println("Original doubly linked list:");

displayList(headNode);

System.out.println("Reversed doubly linked list:");

headNode=reverseList(headNode);

displayList(headNode);

}

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

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

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

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

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

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

Недостатки:

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

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

Итог

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

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

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

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

Объявление

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

Вставка

Удаление

Обход

Реверс

Поиск

Вставка

Удаление

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

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

Итог

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

Дерево AVL и структура данных кучи в C++

Функции преобразования символов в С++

Деревья в C++

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