Listă dublu legată: C++, Python (Exemplu de cod)

Ce este o listă dublu legată?

Într-o listă dublu legată, fiecare nod are legături atât către nodul anterior, cât și către cel următor. Fiecare nod este format din trei elemente: unul deține datele, iar alte două sunt indicatorii nodului următor și anterior. Aceste două indicatoare ne ajută să mergem înainte sau înapoi de la un anumit nod.

Iată structura de bază a listei dublu legate.

Fiecare listă legată are un nod cap și coadă. Nodul Head nu are un nod „prev” (indicator anterior), iar nodul de coadă nu are un nod „următorul”.

Iată câțiva termeni importanți pentru o listă dublu legată:

• Anterior: Fiecare nod este legat de nodul său anterior. Este folosit ca indicator sau link.
• Următor →: Fiecare nod este legat de următorul său nod. Este folosit ca indicator sau link.
• Date: Acesta este folosit pentru a stoca date într-un nod. „Date” poate deține altele Structuri de date inauntru. De exemplu, șir, dicționar, set, hashmap, etc pot fi stocate în „Date”.

Iată structura de bază a unui singur nod din lista dublu legată:

Operalistei dublu legate

Operațiunile unei liste dublu legate includ adăugarea și ștergerea nodurilor, inserarea și eliminarea nodurilor și parcurgerea listei legate de sus în jos.

Iată lista operațiunilor pe care le putem implementa folosind lista dublu legată:

• Inserare in fata
• Inserție în coadă sau ultimul nod
• Inserarea după un nod
• Inserarea înaintea unui nod
• Ștergerea din față
• Ștergerea din coadă
• Căutați și ștergeți un nod
• Traversează cap la coadă
• Traversează coada spre cap

Vom vedea implementarea și pseudocodul pentru toate operațiunile de mai sus.

Inserare în fața listei dublu conectate

Inserarea în față înseamnă că trebuie să creăm un nod în lista legată și să-l plasăm la începutul listei legate.

De exemplu, există un nod dat „15”. Trebuie să adăugăm acest lucru la nodul principal.

Iată două condiții importante în timpul efectuării acestei operațiuni:

1. Noul nod va fi nodul principal dacă nu există niciun nod în Lista dublu legată.
2. Dacă există deja un nod principal, capul anterior va fi înlocuit cu noul nod.

Iată pseudo-codul pentru această operație:

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

Inserarea la sfârșitul listei dublu conectate

„Inserare la sfârșit” înseamnă că vom crea un nod în lista legată și îl vom plasa la sfârșit.

Pentru a realiza acest lucru, putem folosi două metode:

• Metoda 1: Începeți să traversați din capul Listei dublu legate până când „următorul” devine nul. Apoi legați noul nod cu „următorul”.
• Metoda 2: Luați ultimul nod din Lista dublu legată. Apoi, nodul „următorul” al ultimului nod se va conecta la noul nod. Acum, noul nod va fi nodul de coadă.

Iată pseudo-codul pentru inserarea la nodul de coadă:

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

Inserarea după un nod

Să presupunem că avem o listă dublu legată, cum ar fi următoarea:

Dorim să inserăm un nod dat care va fi legat după nod, care are valoarea „12”.

Iată pașii pentru asta:

Pas 1) Traversează de la cap până la ultimul nod. Verificați care nod are valoarea „12”.

Pas 2) Creați un nou nod și atribuiți-l ca următor indicator al nodului „12”. Nodul „următorul” al noului nod va fi 15.

Iată pseudo-codul pentru inserarea unui nod după un nod în lista dublu legată:

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

Inserarea înaintea unui nod

Această operație este mai asemănătoare cu „inserarea după un nod”. Trebuie să căutăm valoarea unui anumit nod pentru a realiza acest lucru. Apoi vom crea un nou nod și îl vom introduce înaintea nodului căutat.

Să presupunem că vrem să inserăm un nod dat „15” înainte de nodul „12”. Apoi, iată pașii pentru a o face:

Pas 1) Traversați lista legată de la nodul principal la nodul de coadă.

Pas 2) Verificați dacă următorul pointer al nodului curent are valoarea „12” sau nu.

Pas 3) Inserați noul nod ca „următorul” nod al nodului curent.

Iată pseudo-codul pentru inserarea unui nod înaintea unui nod în lista dublu legată:

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

Ștergeți capul listei dublu legate

Nodul principal din lista dublu legată care nu are niciun nod anterior. Deci, următorul pointer va fi noul nod principal dacă dorim să ștergem nodul principal. De asemenea, trebuie să eliberăm memoria ocupată de un nod în timp ce ștergem un nod.

Iată pașii pentru ștergerea nodului principal:

Pas 1) Atribuiți o variabilă nodului principal curent.

Pas 2) Vizitați nodul „următorul” al nodului principal curent și faceți nodul „prev” (indicatorul anterior) ca „NULL”. Aceasta înseamnă că deconectăm al doilea nod de primul nod.

Pas 3) Eliberați memoria ocupată de nodul principal anterior.

Iată pseudo-codul pentru ștergerea capului dintr-o listă dublu legată:

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

Este necesar să ștergeți memoria alocată după efectuarea oricărui fel de operație de ștergere. În caz contrar, pe toată durata de rulare a programului, memoria pentru blocul șters va rămâne ocupată. Nicio altă aplicație nu poate folosi acel segment de memorie.

Ștergeți coada listei dublu legate.

Această operație este cam aceeași cu ștergerea capului. Aici, în loc de cap, trebuie să ștergem coada. Pentru a identifica un nod ca nod de coadă, ar trebui să verificăm dacă următorul pointer sau următorul nod este nul sau nu. După ștergerea cozii, trebuie să eliberăm memoria.

Această operațiune este cunoscută și sub numele de „ștergerea din spate”.

Iată pașii pentru a face acest lucru:

Pas 1) Traversați până la nodul de coadă al listei dublu legate.

Pas 2) Atribuiți o variabilă sau un pointer nodului de coadă.

Pas 3) Faceți nodul „următorul” ca NULL și eliberați memoria nodului de coadă.

Iată pseudo-codul pentru ștergerea nodului de coadă:

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

Căutați și ștergeți un nod din Lista dublu conectată

Această operațiune ne permite să căutăm un anumit nod și să ștergem acel nod. Trebuie să efectuăm o căutare liniară deoarece lista legată este o structură de date liniară. După ștergere, trebuie să eliberăm și memoria.

Iată pașii pentru căutarea și ștergerea unui nod din lista dublu legată:

Pas 1) Parcurgeți lista legată de la cap până când valoarea nodului este egală cu elementul de căutare.

Pas 2) Atribuiți o variabilă „deleteNode” nodului potrivit.

Pas 3) Atribuiți nodul anterior al „deleteNode” următorului nod.

Pas 4) Eliberați memoria „deleteNode”

Iată pseudocodul pentru căutarea și ștergerea unui nod dintr-o listă legată:

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

Parcurgeți o listă dublu conectată de la înainte

Pentru a trece de la nodul principal și a itera peste nodul următor până găsim „NULL”. În timp ce parcurgem fiecare nod, putem tipări valoarea nodului. Iată pașii pentru traversarea din față (direcția înainte):

Pas 1) Atribuiți un pointer sau o variabilă nodului principal curent.

Pas 2) Iterați la următorul nod al capului până când obțineți „NULL”

Pas 3) Tipăriți datele nodului în fiecare iterație.

Pas 4) Întoarceți nodul principal.

Iată pseudo-codul pentru a parcurge o listă dublu legată din față:

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

Aici, returul nu este obligatoriu. Dar este o practică bună să returnați nodul principal după operații.

Parcurgeți o listă dublu legată din spate

Această operație este inversul traversării din față. Abordarea este aceeași, cu o mică diferență. Trebuie să traversăm până la nodul final și apoi să traversăm de la nodul final la nodul frontal.

Iată pașii pentru a parcurge o listă dublu legată din spate:

Pas 1) Traversează până ajungem la nodul de coadă.

Pas 2) Din nodul de coadă, vom traversa până când obținem nodul anterior ca „NULL”. „prev” (indicatorul anterior) va fi nul pentru nodul principal

Pas 3) La fiecare iterație, vom tipări datele nodului.

Iată pseudo-codul pentru traversarea din spate:

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

Diferența dintre lista cu legătură individuală și dublă

Principala diferență dintre lista Single și Double Linked este numărul de link-uri.

Iată diferența dintre nodurile unei liste cu legături unice și structura de noduri a listei dublu legate:

Câmp	Lista legată individual	Listă dublu legată
Structure	Lista legată individual are un câmp de date și o legătură către următorul nod.	Lista dublu legată are un câmp de date și două legături. Unul pentru nodul anterior și altul pentru nodul următor.
traversal	Nu poate traversa decât de la cap la coadă.	Poate traversa atât înainte, cât și înapoi.
Memorie	Ocupă mai puțină memorie.	Ocupă mai multă memorie decât o listă unică legată.
Accesibilitate	Listele legate individual sunt mai puțin eficiente, deoarece folosesc doar o legătură către următorul nod. Nu există nicio legătură pentru nodul anterior.	Listele dublu legate sunt mai eficiente decât listele cu legături individuale.

Listă dublu conectată în 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);
}

producție

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

Listă dublu conectată în 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()

producție

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

Complexitatea listei dublu legate

În general, complexitatea timpului este împărțită în trei tipuri.

Acestea sunt:

1. Cel mai bun caz
2. Caz mediu
3. Cel mai rău caz

Complexitatea timpului în cel mai bun caz pentru Lista dublu legată:

1. Inserarea în cap sau coadă va costa O(1). Pentru că nu trebuie să traversăm în interiorul listei legate. Capul și indicatorul de coadă ne pot oferi acces la nodul cap și coadă cu complexitate de timp O(1).
2. Ștergerea la cap sau coadă va costa O(1).
3. Căutarea unui nod va avea complexitatea temporală a lui O(1). Deoarece nodul țintă poate fi nodul principal.

Complexitatea timpului în cazul mediu pentru Lista dublu legată:

1. Inserarea la cap sau coadă va avea complexitatea de timp a costului O(1).
2. Ștergerea la cap sau coadă va avea complexitatea în timp a costului O(1).
3. Căutarea unui nod va avea complexitatea de timp de O(n). Deoarece elementul de căutare poate locui oriunde între lista legată. Aici, „n” este nodul total prezent în lista legată.

Complexitatea timpului în cel mai rău caz a listei dublu legate va fi aceeași cu cazul mediu.

Complexitatea memoriei listei duble legate

Complexitatea memoriei este O(n), unde „n” este numărul total de noduri. În timp ce implementăm lista legată, trebuie să eliberăm memoria pe care am folosit-o. În caz contrar, pentru o listă legată mai mare, va cauza pierderi de memorie.

Rezumat

• O listă legată este un fel de structură de date liniară, o colecție de date reprezentate într-o manieră liniară.
• O listă dublu legată este un tip de listă legată în care un nod are legături atât cu nodul anterior, cât și cu cel următor.
• Lista dublu legată conține toate operațiunile precum adăugarea unui nod, ștergerea unui nod, inserarea unui nod după sau înaintea altui nod și parcurgerea listei legate de la cap la coadă.
• Lista dublu legată are un câmp de date și două legături. Unul pentru nodul anterior și altul pentru nodul următor.
• Complexitatea listei dublu legate cel mai bun caz, caz mediu
• Și cel mai rău caz.