Двусвязный список: C++, Python (Пример кода)

Что такое двусвязный список?

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

Вот базовая структура двусвязного списка.

Каждый связанный список имеет головной и хвостовой узел. Головной узел не имеет узла «prev» (предыдущий указатель), а хвостовой узел не имеет узла «следующий».

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

Предыдущая: Каждый узел связан со своим предыдущим узлом. Он используется как указатель или ссылка.
Далее: Каждый узел связан со своим следующим узлом. Он используется как указатель или ссылка.
Данные: Это используется для хранения данных в узле. «Данные» могут содержать другие Структуры данных внутри него. Например, в разделе «Данные» можно хранить строку, словарь, набор, хэш-карту и т. д.

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

Operaции двусвязного списка

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

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

Вставка спереди
Вставка в хвост или последний узел
Вставка после узла
Вставка перед узлом
Удаление спереди
Удаление из хвоста
Найти и удалить узел
Траверс голова к хвосту
Траверс хвостом к голове

Мы увидим реализацию и псевдокод для всех вышеописанных операций.

Вставка перед двусвязным списком

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

Например, есть заданный узел «15». Нам нужно добавить это в головной узел.

Вот два важных условия при выполнении этой операции:

Новый узел будет головным узлом, если в двусвязном списке нет узла.
Если головной узел уже существует, предыдущий головной узел будет заменен новым узлом.

Вот псевдокод этой операции:

function insertAtFront (ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = NewNode
  NewNode.next = ListHead
  newNode.prev = NULL
  return ListHead

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

«Вставка в конец» означает, что мы создадим узел в связанном списке и поместим его в конец.

Для этого мы можем использовать два метода:

Метод 1: Начните перемещение с начала двусвязного списка, пока «следующий» не станет нулевым. Затем свяжите новый узел со «следующим».
Метод 2: Возьмите последний узел двусвязного списка. Затем «следующий» узел последнего узла будет связан с новым узлом. Теперь новый узел будет хвостовым узлом.

Вот псевдокод для вставки в хвостовой узел:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
	then ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Вставка после узла

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

Мы хотим вставить данный узел, который будет связан после узла, имеющего значение «12».

Вот шаги для этого:

Шаг 1) Траверс от головы до последнего узла. Проверьте, какой узел имеет значение «12».

Шаг 2) Создайте новый узел и назначьте его следующим указателем узла «12». «Следующим» узлом нового узла будет номер 15.

Вот псевдокод для вставки узла после узла в двусвязном списке:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.value is not equal searchItem
	then List = ListHead.next
  List = List.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode

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

Эта операция больше похожа на «вставку после узла». Для этого нам нужно найти значение конкретного узла. Затем мы создадим новый узел и вставим его перед искомым узлом.

Допустим, мы хотим вставить данный узел «15» перед узлом «12». Тогда вот шаги для этого:

Шаг 1) Перейдите по связанному списку от головного узла к хвостовому узлу.

Шаг 2) Проверьте, имеет ли следующий указатель текущего узла значение «12» или нет.

Шаг 3) Вставьте новый узел как «следующий» узел текущего узла.

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

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.next.value is not equal searchItem
	then List = ListHead.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode

Удалить заголовок двусвязного списка

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

Вот шаги для удаления головного узла:

Шаг 1) Назначьте переменную текущему головному узлу.

Шаг 2) Посетите «следующий» узел текущего головного узла и установите для узла «prev» (предыдущий указатель) значение «NULL». Это означает, что мы отключаем второй узел от первого узла.

Шаг 3) Освободите память, занятую предыдущим головным узлом.

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

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

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

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

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

Эта операция также известна как «удаление со спины».

Вот шаги, которые нужно сделать:

Шаг 1) Пройдите до хвостового узла двусвязного списка.

Шаг 2) Назначьте переменную или указатель хвостовому узлу.

Шаг 3) Сделайте «следующий» узел равным NULL и освободите память хвостового узла.

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

function DeleteTail( ListHead ):
  head = ListHead
  while ListHead.next is not NULL:
	ListHead = ListHead.next
  Tail = ListHead.next
  ListHead.next = NULL
  free memory( Tail )
  return head

Найдите и удалите узел из двусвязного списка.

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

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

Шаг 1) Перемещайтесь по связанному списку от головы до тех пор, пока значение узла не станет равным искомому элементу.

Шаг 2) Назначьте переменную «deleteNode» соответствующему узлу.

Шаг 3) Назначьте предыдущий узел «deleteNode» следующему узлу.

Шаг 4) Освободите память «deleteNode»

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

function SearchAndDelete(ListHead, searchItem):
  head = ListHead
  while ListHead.next.value not equals searchItem:
	head = head.next
  deleteNode = head.next
  head.next = head.next.next
  head.next.prev = head
  deleteNode.next, deleteNode.next = NULL
  free memory(deleteNode)
  return ListHead

Найти и удалить Operaпроизводство — Операция поиска и удаления

Обход двусвязного списка вперед

Чтобы пройти от головного узла и перебирать следующий узел, пока не найдем «NULL». Проходя каждый узел, мы можем напечатать значение узла. Вот шаги для перемещения спереди (вперед):

Шаг 1) Назначьте указатель или переменную текущему головному узлу.

Шаг 2) Перейдите к следующему узлу головы, пока не получите «NULL».

Шаг 3) Распечатывайте данные узла на каждой итерации.

Шаг 4) Верните головной узел.

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

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals to NULL:
	print head.data
	head = head.next
  return ListHead

Здесь возврат не является обязательным. Но после выполнения операций рекомендуется возвращать головной узел.

Обход двусвязного списка сзади

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

Вот шаги для обхода двусвязного списка сзади:

Шаг 1) Траверс, пока не достигнем хвостового узла.

Шаг 2) От хвостового узла мы будем перемещаться до тех пор, пока предыдущий узел не будет иметь значение «NULL». «prev» (предыдущий указатель) будет нулевым для головного узла.

Шаг 3) На каждой итерации мы будем печатать данные узла.

Вот псевдокод для перемещения сзади:

function traverseFromBack(ListHead):
  head = ListHead
  while head not equals NULL:
	head = head.next
  tail = head
  while tail not equal to NULL:
	print tail.value
	tail = tail.prev
  return ListHead

Разница между односвязным и двусвязным списком

Основное различие между одиночным списком и двусвязным списком заключается в количестве ссылок.

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

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

Двусвязный список в C++

#include<iostream>
using namespace std;
  struct node{
  int data;
  struct node *next;
  struct node *prev;
  };
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead!=NULL)
  {
	listHead->prev = newNode;
  	newNode->next = listHead;
  }
  
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
  }
void insertEnd(node * &listHead, int value){
  if(listHead==NULL)
  {
  	insertFront(listHead,value);
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next!=NULL){
  head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
  }
void insertAfter(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;
  node *head = listHead;	
  while(head->next!=NULL &&  head->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
  }
void insertBefore(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;	
  node *head = listHead;	
  while(head->next!=NULL &&  head->next->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;	
  }
void traverseFromFront(node *listHead){
  node* head = new node();
  head = listHead;
  cout<<"Traversal from head:\t";	
  while(head!=NULL){	
  cout<<head->data<<"\t ";	
  head = head->next;	
  }	
  cout<<endl;
  }	
void traverseFromEnd(node *listHead){
  node* head = new node();
  head = listHead;	
  cout<<"Traversal from head:\t";	
  while(head->next!=NULL){	
  head = head->next;	
  }	
  node *tail = head;	
  while(tail!=NULL){	
  cout<<tail->data<<"\t";	
  tail = tail->prev;	
  }	
  cout<<endl;	
  }
void searchAndDelete(node **listHead, int searchItem){
  node* head = new node();
  head = (*listHead);
  while(head->next!=NULL &&  head->data!=searchItem){
  head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
  	*listHead = head->next;
  }
  if(head->next != NULL){
  	head->next->prev = head->prev;
  }
  
  if(head->prev != NULL){
  	head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
  }
int main(){
  node *head = NULL;
  insertFront(head,5);
  insertFront(head,6);
  insertFront(head,7);
  insertEnd(head,9);
  insertEnd(head,10);
  insertAfter(head,5,11);
  insertBefore(head,5,20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head,7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Результат

Added 5 at the front
Added 6 at the front
Added 7 at the front
Aded 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7        6       20      5       11      9       10
Traversal from head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6

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

class node:
  def __init__(self,data = None, prev=None, next = None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None

  def insertFront(self, val):
    newNode = node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))

  def insertEnd(self,val):
    newNode = node(data=val)
    if self.head is None:
      self.insertFront(val)
    
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))

  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()

  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from Tail:\t",end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data),end="")
      tail = tail.prev
    print()
  
  def insertAfter(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value,searchItem))

  def insertBefore(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value,searchItem))

  def searchAndDelete(self,searchItem):
    temp = self.head

    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    if self.head is None or temp is None:
      return

    if self.head.data is temp.data:
      self.head = temp.next

    if temp.next is not None:
      temp.next.prev = temp.prev
    
    if temp.prev is not None:
      temp.prev.next = temp.next
    
    print("Deleted Node\t{}".format(searchItem))
    return

doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Результат

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7       6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6       7
Deleted Node    7
Traversing from head:   6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6

Сложность двусвязного списка

Обычно временная сложность делится на три типа.

К ним относятся:

лучший случай
Средний случай
Худший случай

Временная сложность в лучшем случае для двусвязного списка:

Вставка в заголовок или хвост будет стоить O(1). Потому что нам не нужно перемещаться внутри связанного списка. Указатель головы и хвоста может дать нам доступ к узлу головы и хвоста с временной сложностью O (1).
Удаление в начале или в хвосте будет стоить O(1).
Поиск узла будет иметь временную сложность O(1). Потому что целевой узел может быть головным узлом.

Временная сложность в среднем случае для двусвязного списка:

Вставка в начале или в конце будет иметь временную сложность стоимости O(1).
Удаление в начале или в хвосте будет иметь временную сложность O(1).
Поиск узла будет иметь временную сложность O(n). Потому что элемент поиска может находиться где угодно в связанном списке. Здесь «n» — это общее количество узлов, присутствующих в связанном списке.

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

Сложность памяти двусвязного списка

Сложность памяти равна O(n), где «n» — общее количество узлов. При реализации связанного списка мы должны освободить использованную память. В противном случае для большего связанного списка это приведет к утечкам памяти.

Резюме

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

Вы могли бы:

Что такое двусвязный список?

Operaции двусвязного списка

Вставка перед двусвязным списком

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

СТАТЬИ ПО ТЕМЕ

Вставка после узла

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

Удалить заголовок двусвязного списка

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

Найдите и удалите узел из двусвязного списка.

Обход двусвязного списка вперед

Обход двусвязного списка сзади

Разница между односвязным и двусвязным списком

Двусвязный список в C++

Результат

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

Результат

Сложность двусвязного списка

Резюме