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

Ce este o listă dublu înlănțuită?

Într-o listă dublu înlănțuită, 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 conține datele, iar celelalte două sunt pointeri către nodul următor și către cel anterior. Acești doi pointeri ajută la deplasarea înainte sau înapoi de la un anumit nod.

Iată structura de bază a listei dublu înlănțuite.

Structura unei liste dublu legate

Fiecare listă înlănțuită are un nod principal și un nod de coadă. Nodul principal nu are precedentă nodul (indicatorul anterior), iar nodul de coadă nu are următor nodul.

Iată câțiva termeni importanți pentru o listă dublu înlănțuită:

• 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: Aceasta este utilizată pentru stocarea datelor într-un nod. Datele pot conține și alte Structuri de date în interiorul acestuia. De exemplu, în câmpul de date pot fi stocate șiruri de caractere, dicționare, seturi, hashmap-uri și alte structuri.

Iată structura de bază a unui singur nod din Lista Dublu Înlănțuită:

Structura unui nod într-o listă dublu legată

Operalistei dublu legate

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

Iată lista operațiilor care pot fi implementate pe o listă dublu înlănțuită:

• Inserare in fata
• Inserție la coadă sau la 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

Implementarea și pseudocodul pentru fiecare dintre aceste operațiuni sunt prezentate mai jos.

Inserarea în fața unei liste dublu înlănțuite

Inserarea în față înseamnă crearea unui nod în lista înlănțuită și plasarea acestuia la începutul listei.

De exemplu, există un nod dat 15Trebuie adăugat ca nod principal.

Două condiții importante se aplică la efectuarea acestei operațiuni:

1. Noul nod devine nodul principal dacă Lista Dublu Înlănțuită este goală.
2. Dacă există deja un nod principal, nodul principal anterior este înlocuit cu noul nod.

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

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

Inserție în nodul frontal

Inserarea la sfârșitul listei dublu înlănțuite

Inserarea la sfârșit înseamnă crearea unui nod în lista înlănțuită și plasarea acestuia la coadă.

Două metode efectuează această operațiune:

• Metoda 1: Începeți traversarea de la începutul Listei Dublu Înlănțuite până când următor devine nul. Apoi conectați noul nod cu următor indicator.
• Metoda 2: Luați ultimul nod al Listei Dublu Înlănțuite. Apoi, următor Indicatorul ultimului nod indică noul nod. Noul nod devine nodul de coadă.

Iată pseudocodul pentru inserarea la nodul de coadă:

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

Inserare la sfârșitul listei legate

Inserarea după un nod

Luați în considerare o listă dublu înlănțuită existentă, cum ar fi următoarea:

Scopul este de a insera un nod dat care va fi legat după nodul cu valoarea 12.

Pas 1) Traversați de la cap la ultimul nod. Verificați care nod are valoarea 12.

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

Iată pseudo-codul pentru inserarea unui nod după un nod într-o listă dublu înlănțuită:

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

Inserarea după un Nod

Inserare înaintea unui nod

Această operațiune este similară cu inserarea după un nod. Se caută o valoare specifică a unui nod, apoi se creează un nou nod și se inserează acesta înaintea nodului căutat.

Pentru a insera un nod dat 15 înainte de nod 12, urmați acești pași:

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.

Pas 3) Introduceți noul nod ca următor nodul nodului curent.

Iată pseudo-codul pentru inserarea unui nod înaintea unui alt nod într-o listă dublu înlănțuită:

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

Inserarea unui nod înaintea unui nod

Ștergeți capul listei dublu înlănțuite

Nodul principal din Lista Dublu Înlănțuită nu are niciun nod anterior. Deci următor Indicatorul devine noul nod principal atunci când nodul principal curent este eliminat. De asemenea, este necesară eliberarea memoriei ocupate de un nod șters.

Iată pașii pentru ștergerea nodului principal:

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

Pas 2) Vizitați următor nodul nodului principal curent și faceți precedentă pointer NULL. Aceasta deconectează al doilea nod de primul nod.

Pas 3) Eliberează memoria ocupată de nodul principal anterior.

Iată pseudo-codul pentru ștergerea capului dintr-o listă dublu înlănțuită:

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

Ștergerea nodului principal

Eliberarea memoriei alocate după orice ștergere este necesară. În caz contrar, memoria pentru blocul șters rămâne ocupată pe întreaga durată de execuție a programului și nicio altă aplicație nu poate utiliza acel segment de memorie.

Ștergeți coada listei dublu înlănțuite

Această operație este similară cu ștergerea capului. În loc de cap, se elimină coada. Pentru a identifica un nod drept coadă, se verifică dacă următorul pointer este nul. După ștergerea cozii, memoria trebuie eliberată.

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 Înlănțuite.

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

Pas 3) Seteaza următor pointerul către NULL și eliberează 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
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

Căutarea și ștergerea unui nod dintr-o listă dublu legată

Această operație caută o valoare specifică a unui nod și șterge acel nod. Este necesară o căutare liniară deoarece lista înlănțuită este o structură de date liniară. După ștergere, memoria trebuie eliberată.

Iată pașii pentru căutarea și ștergerea unui nod din Lista Dublu Înlănțuită:

Pas 1) Parcurgeți lista înlănțuită de la început până când valoarea nodului este egală cu elementul căutat.

Pas 2) Atribuiți o variabilă ștergeNode către nodul potrivit.

Pas 3) Legați nodul anterior al ștergeNode la următorul său nod și setează următorul nod precedentă pointer către nodul anterior.

Pas 4) Eliberează memoria ștergeNode.

Iată pseudocodul pentru căutarea și ștergerea unui nod dintr-o listă înlănțuită:

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

Operațiune de căutare și ștergere

Parcurgerea unei liste dublu înlănțuite de la început până la sfârșit

Traversarea de la nodul principal iterează peste următorul nod până când se găsește valoarea NULL. În timp ce se traversează fiecare nod, valoarea poate fi afișată. Iată pașii pentru traversarea în direcția înainte:

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

Pas 2) Iterează la următorul nod al head-ului până când obține NULL.

Pas 3) Afișează datele nodului în fiecare iterație.

Pas 4) Întoarceți nodul principal.

Iată pseudo-codul pentru parcurgerea unei liste dublu înlănțuite din față:

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

Returnarea nu este obligatorie. Cu toate acestea, returnarea nodului principal după operații este o practică bună.

Parcurgerea unei liste dublu înlănțuite dinspre înapoi

Această operație este inversa traversării din față. Abordarea este aceeași cu o mică diferență: se ajunge mai întâi la nodul final, apoi se merge înapoi spre capăt folosind precedentă indicator.

Iată pașii pentru parcurgerea unei liste dublu înlănțuite din spate:

Pas 1) Traversați până când se ajunge la nodul de coadă.

Pas 2) De la nodul de coadă, traversați folosind precedentă până când nodul anterior este NULL. precedentă pointerul este nul pentru nodul principal.

Pas 3) La fiecare iterație, afișați datele nodului.

Iată pseudo-codul pentru traversarea din spate:

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

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

Principala diferență dintre o listă singular înlănțuită și o listă dublu înlănțuită constă în numărul de legături pe care le deține fiecare nod.

Iată diferența dintre nodurile unei liste înlănțuite simplu și ale unei liste dublu înlănțuite:

Listă dublu conectată în C++

Mai jos este o versiune completă C++ Implementarea unei liste dublu înlănțuite cu operații de inserare, ștergere, căutare și traversare.

#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);
    return;
  }
  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 = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\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 = (*listHead);
  while(head != 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;
}
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
Added 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 tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Listă dublu conectată în Python

Mai jos este o versiune completă Python Implementarea unei liste dublu înlănțuite folosind clase pentru noduri și lista în sine.

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.head = newNode
      print("Added {} at the end".format(val))
      return
    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 is not None:
      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 != 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 != 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 is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == 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))
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

Complexitatea timpului este în general împărțită în trei tipuri: cel mai bun caz, cazul mediu și cel mai rău caz.

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

1. Inserarea la cap sau la coadă costă O(1) deoarece nu este necesară traversarea în interiorul listei înlănțuite. Pointerii de cap și coadă oferă acces direct la nodurile cap și coadă.
2. Ștergerea la vârf sau la coadă costă O(1).
3. Căutarea unui nod costă O(1) atunci când nodul țintă este nodul principal.

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

1. Inserarea la vârf sau la coadă costă O(1).
2. Ștergerea la vârf sau la coadă costă O(1).
3. Căutarea unui nod costă O(n), deoarece ținta poate fi localizată oriunde în listă. Aici, n este numărul total de noduri.

Complexitatea temporală în cazul cel mai defavorabil al Listei Dublu Înlănțuite este aceeași cu cea din cazul mediu.

Complexitatea memoriei listei duble legate

Complexitatea memoriei este O(n), unde n este numărul total de noduri. La implementarea listei înlănțuite, memoria trebuie eliberată. În caz contrar, listele înlănțuite mai mari cauzează pierderi de memorie.

Aplicații ale listei dublu înlănțuite

Listele dublu înlănțuite alimentează mai multe structuri de date din lumea reală, deoarece traversarea bidirecțională simplifică multe operații comune.

• Cache LRU: Memoriile cache utilizate cel mai puțin recent utilizează o listă dublu legată cu o hartă hash pentru mutarea în față și evictarea O(1).
• Istoricul browserului: Navigarea înainte și înapoi parcurge lista legată în ambele direcții.
• Anulați și refaceți stive: Editori și IDE-uri track versiuni de documente cu pointeri prev și next.
• Deque: DoubleCozile cu capăt fix de serie sunt trimise prin push și extrase de la ambele capete în timp O(1).
• Liste de redare muzicală: Anterior și următorul tracButoanele k se bazează pe indicatori înainte și înapoi.

Întrebări frecvente