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

Какво е двойно свързан списък?

В двойно свързан списък всеки възел има връзки към предишния и следващия възел. Всеки възел се състои от три елемента: единият съдържа данните, а други два са указателите на следващия и предишния възел. Тези два указателя ни помагат да вървим напред или назад от определен възел.

Ето основната структура на двойно свързания списък.

Всеки свързан списък има начален и опашен възел. Главният възел няма „предишен“ (предишен указател) възел, а опашният възел няма „следващ“ възел.

Ето някои важни термини за двойно свързан списък:

• Предишна: Всеки възел е свързан с предишния си възел. Използва се като указател или връзка.
• Следващия: Всеки възел е свързан със следващия си възел. Използва се като указател или връзка.
• Данни: Това се използва за съхраняване на данни във възел. „Данните“ могат да съдържат други Структури на данни вътре в него. Например низ, речник, набор, hashmap и т.н. могат да се съхраняват в „Данни“.

Ето основната структура на единичен възел в двойно свързания списък:

Operaции на двойно свързан списък

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

Ето списъка с операции, които можем да приложим с помощта на двойно свързания списък:

• Вмъкване отпред
• Вмъкване в опашката или последния възел
• Вмъкване след възел
• Вмъкване преди възел
• Изтриване отпред
• Изтриване от опашката
• Търсене и изтриване на възел
• Траверс от главата до опашката
• Траверс от опашка към глава

Ще видим изпълнението и псевдокода за всички операции по-горе.

Вмъкване пред двойно свързан списък

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

Например, има даден възел „15“. Трябва да добавим това към главния възел.

Ето две важни условия, докато извършвате тази операция:

1. Новият възел ще бъде главният възел, ако няма възел в двойно свързания списък.
2. Ако вече има главен възел, предишната глава ще бъде заменена от новия възел.

Ето псевдокода за тази операция:

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) Посетете „следващия“ възел на текущия главен възел и направете възела „предишен“ (предишен указател) като „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

Обхождане на двойно свързан списък от напред

За преминаване от главния възел и повторение на следващия възел, докато намерим „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“. „Предишен“ (предишен указател) ще бъде нулев за главния възел

Стъпка 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

Сложност на двойно свързания списък

Най-общо времевата сложност се разделя на три типа.

Те са:

1. Най -добрият случай
2. Среден случай
3. Най-лошия случай

Времева сложност в най-добрия случай за двойно свързан списък:

1. Вмъкването в главата или опашката ще струва O(1). Тъй като не е необходимо да преминаваме в свързания списък. Указателят на главата и опашката може да ни даде достъп до възела на главата и опашката с времева сложност O(1).
2. Изтриването в началото или опашката ще струва O(1).
3. Търсенето на възел ще има времева сложност O(1). Тъй като целевият възел може да бъде главният възел.

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

1. Вмъкването в началото или опашката ще има времева сложност на разходите O(1).
2. Изтриването в началото или опашката ще има времева сложност на разходите O(1).
3. Търсенето на възел ще има времева сложност O(n). Тъй като елементът за търсене може да се намира навсякъде между свързания списък. Тук „n“ е общият възел, присъстващ в свързания списък.

Времевата сложност в най-лошия случай на двойно свързания списък ще бъде същата като средния случай.

Сложност на паметта на двойно свързан списък

Сложността на паметта е O(n), където „n“ е общият брой възли. Докато прилагаме свързания списък, трябва да освободим паметта, която сме използвали. В противен случай, за по-голям свързан списък, това ще доведе до изтичане на памет.

Oбобщение

• Свързаният списък е вид линейна структура от данни, колекция от данни, представени по линеен начин.
• Двойно свързан списък е вид свързан списък, при който възел има връзки както с предишния, така и със следващия възел.
• Двойно свързаният списък съдържа всички операции като добавяне на възел, изтриване на възел, вмъкване на възел след или преди друг възел и преминаване на свързания списък от главата до опашката.
• Двойно свързан списък има едно поле за данни и две връзки. Един за предишния възел и друг за следващия възел.
• Сложност на двойно свързан списък Най-добър случай, среден случай
• И най-лошия случай.