Elenco doppiamente collegato: C++, Python (Code Esempio)

Che cos'è una lista doppiamente concatenata?

In una lista doppiamente concatenata, ogni nodo ha collegamenti sia al nodo precedente che a quello successivo. Ogni nodo è composto da tre elementi: uno contiene i dati, e gli altri due sono puntatori al nodo successivo e a quello precedente. Questi due puntatori consentono di spostarsi avanti o indietro da un determinato nodo.

Ecco la struttura di base della lista doppiamente concatenata.

Struttura di una lista doppiamente concatenata

Ogni lista concatenata ha un nodo di testa e un nodo di coda. Il nodo di testa non ha prev nodo (puntatore precedente) e il nodo di coda non ha GENERAZIONE nodo.

Ecco alcuni termini importanti relativi alle liste doppiamente concatenate:

• Indietro: Ogni nodo è collegato al suo nodo precedente. Viene utilizzato come puntatore o collegamento.
• Avanti: Ogni nodo è collegato al suo nodo successivo. Viene utilizzato come puntatore o collegamento.
• Data: Questo viene utilizzato per memorizzare i dati in un nodo. I dati possono contenere altri Strutture dati Al suo interno, ad esempio, è possibile memorizzare stringhe, dizionari, insiemi, mappe hash e altre strutture nel campo dati.

Ecco la struttura di base di un singolo nodo in una lista doppiamente concatenata:

Struttura di un nodo in una lista doppiamente concatenata

Operazioni della lista doppiamente collegata

Le operazioni su una lista doppiamente concatenata includono l'aggiunta, la cancellazione, l'inserimento e la rimozione di nodi, nonché l'attraversamento della lista dall'alto verso il basso o dal basso verso l'alto.

Ecco l'elenco delle operazioni che possono essere eseguite su una lista doppiamente concatenata:

• Inserimento davanti
• Inserimento nella coda o nell'ultimo nodo
• Inserimento dopo un nodo
• Inserimento prima di un nodo
• Eliminazione dalla parte anteriore
• Cancellazione dalla coda
• Cerca ed elimina un nodo
• Attraversa la testa alla coda
• Attraversa la coda verso la testa

Di seguito vengono riportati l'implementazione e lo pseudocodice per ciascuna di queste operazioni.

Inserimento all'inizio di una lista doppiamente concatenata

L'inserimento all'inizio consiste nel creare un nodo nella lista concatenata e posizionarlo all'inizio della lista.

Ad esempio, esiste un nodo dato 15Deve essere aggiunto come nodo principale.

Durante l'esecuzione di questa operazione, si applicano due condizioni importanti:

1. Il nuovo nodo diventa il nodo iniziale se la lista doppiamente concatenata è vuota.
2. Se è già presente un nodo principale, il nodo principale precedente viene sostituito dal nuovo nodo.

Ecco lo pseudocodice per questa operazione:

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

Inserimento nel nodo anteriore

Inserimento alla fine di una lista doppiamente concatenata

L'inserimento alla fine consiste nel creare un nodo nella lista concatenata e posizionarlo in coda.

Esistono due metodi per eseguire questa operazione:

• Metodo 1: Inizia la traversata dalla testa della lista doppiamente concatenata fino a GENERAZIONE diventa nullo. Quindi collega il nuovo nodo con il GENERAZIONE puntatore.
• Metodo 2: Prendi l'ultimo nodo della lista doppiamente concatenata. Quindi, il GENERAZIONE Il puntatore dell'ultimo nodo punta al nuovo nodo. Il nuovo nodo diventa il nodo di coda.

Ecco lo pseudocodice per l'inserimento nel nodo di coda:

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

Inserimento alla fine dell'elenco collegato

Inserimento dopo un nodo

Si consideri una lista doppiamente concatenata esistente come la seguente:

L'obiettivo è inserire un nodo dato che verrà collegato dopo il nodo con il valore 12.

Passo 1) Attraversa dalla testa all'ultimo nodo. Controlla quale nodo ha il valore 12.

Passo 2) Crea un nuovo nodo e assegnalo come puntatore successivo del nodo 12. GENERAZIONE il nodo del nuovo nodo sarà 15.

Ecco lo pseudocodice per inserire un nodo dopo un nodo in una lista doppiamente concatenata:

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

Inserimento dopo un nodo

Inserimento prima di un nodo

Questa operazione è simile all'inserimento dopo un nodo. Viene cercato un valore specifico del nodo, quindi viene creato un nuovo nodo che viene inserito prima del nodo cercato.

Per inserire un nodo specificato 15 prima del nodo 12, Segui questi passi:

Passo 1) Attraversa l'elenco collegato dal nodo testa al nodo coda.

Passo 2) Verifica se il puntatore successivo del nodo corrente ha il valore 12.

Passo 3) Inserisci il nuovo nodo come GENERAZIONE nodo del nodo corrente.

Ecco lo pseudocodice per inserire un nodo prima di un altro nodo in una lista doppiamente concatenata:

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

Inserimento di un nodo prima di un nodo

Elimina l'intestazione della lista doppiamente concatenata

Il nodo testa nella lista doppiamente concatenata non ha alcun nodo precedente. Quindi il GENERAZIONE Il puntatore diventa il nuovo nodo di testa quando il nodo di testa corrente viene rimosso. È inoltre necessario liberare la memoria occupata da un nodo eliminato.

Ecco i passaggi per eliminare il nodo principale:

Passo 1) Assegna una variabile al nodo head corrente.

Passo 2) Visita il GENERAZIONE nodo del nodo head corrente e renderlo prev puntatore NULL. Questo disconnette il secondo nodo dal primo nodo.

Passo 3) Liberare la memoria occupata dal nodo precedente.

Ecco lo pseudocodice per eliminare la testa da una lista doppiamente concatenata:

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

Eliminazione del nodo testa

Dopo ogni cancellazione è necessario liberare la memoria allocata. In caso contrario, la memoria del blocco cancellato rimane occupata per l'intera durata del programma e nessun'altra applicazione può utilizzare quel segmento di memoria.

Elimina la coda della lista doppiamente concatenata

Questa operazione è simile alla cancellazione della testa. Invece della testa, viene rimossa la coda. Per identificare un nodo come coda, si verifica se il puntatore successivo è nullo. Dopo aver eliminato la coda, la memoria deve essere liberata.

Questa operazione è anche nota come cancellazione dal retro.

Ecco i passaggi per farlo:

Passo 1) Attraversa la lista fino al nodo finale della lista doppiamente concatenata.

Passo 2) Assegna una variabile o un puntatore al nodo coda.

Passo 3) Impostare il GENERAZIONE puntatore a NULL e libera la memoria del nodo di coda.

Ecco lo pseudocodice per eliminare il nodo finale:

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

Cercare ed eliminare un nodo da una lista doppiamente concatenata

Questa operazione cerca un valore specifico in un nodo e lo elimina. È necessaria una ricerca lineare perché la lista concatenata è una struttura dati lineare. Dopo l'eliminazione, la memoria deve essere liberata.

Ecco i passaggi per cercare ed eliminare un nodo in una lista doppiamente concatenata:

Passo 1) Percorri la lista concatenata dall'inizio fino a quando il valore del nodo non corrisponde all'elemento cercato.

Passo 2) Assegna una variabile eliminaNodo al nodo corrispondente.

Passo 3) Collega il nodo precedente del eliminaNodo al suo nodo successivo e imposta il nodo successivo prev puntatore al nodo precedente.

Passo 4) Liberare la memoria del eliminaNodo.

Ecco lo pseudocodice per cercare ed eliminare un nodo da una lista concatenata:

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

Operazione di ricerca ed eliminazione

Attraversare una lista doppiamente concatenata dall'inizio

L'attraversamento a partire dal nodo iniziale itera sul nodo successivo finché non viene trovato NULL. Durante l'attraversamento di ciascun nodo, è possibile stampare il valore corrispondente. Ecco i passaggi per l'attraversamento in avanti:

Passo 1) Assegna un puntatore o una variabile al nodo head corrente.

Passo 2) Passa al nodo successivo della testa finché non trovi NULL.

Passo 3) Stampa i dati del nodo in ogni iterazione.

Passo 4) Restituisce il nodo principale.

Ecco lo pseudocodice per attraversare una lista doppiamente concatenata dall'inizio:

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

Il ritorno non è obbligatorio. Tuttavia, è buona norma restituire il nodo principale al termine delle operazioni.

Attraversare una lista doppiamente concatenata dall'indietro

Questa operazione è l'inverso della traversata dalla parte anteriore. L'approccio è lo stesso con una piccola differenza: raggiungere prima il nodo finale, quindi camminare all'indietro verso la testa usando il prev puntatore.

Ecco i passaggi per attraversare una lista doppiamente concatenata partendo dalla fine:

Passo 1) Proseguire fino a raggiungere il nodo terminale.

Passo 2) Dal nodo di coda, attraversare utilizzando prev fino a quando il nodo precedente non è NULL. Il prev Il puntatore al nodo head è nullo.

Passo 3) Ad ogni iterazione, stampa i dati del nodo.

Ecco lo pseudocodice per attraversare il percorso partendo da dietro:

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

Differenza tra lista concatenata singola e lista concatenata doppia

La principale differenza tra una lista concatenata semplice e una lista concatenata doppia risiede nel numero di collegamenti presenti in ciascun nodo.

Ecco la differenza tra i nodi di una lista concatenata semplice e di una lista concatenata doppia:

Elenco doppiamente collegato in C++

Di seguito è riportato un completo C++ Implementazione di una lista doppiamente concatenata con operazioni di inserimento, cancellazione, ricerca e attraversamento.

#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);
}

Uscita

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

Elenco doppiamente collegato in Python

Di seguito è riportato un completo Python Implementazione di una lista doppiamente concatenata utilizzando classi per i nodi e per la lista stessa.

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()

Uscita

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

Complessità della lista doppiamente collegata

La complessità temporale viene generalmente suddivisa in tre tipologie: caso migliore, caso medio e caso peggiore.

Complessità temporale nel caso migliore per una lista doppiamente collegata:

1. L'inserimento all'inizio o alla fine della lista ha un costo O(1) perché non è necessario alcun attraversamento all'interno della lista concatenata. I puntatori di testa e di coda consentono l'accesso diretto ai nodi di testa e di coda.
2. La cancellazione all'inizio o alla fine costa O(1).
3. La ricerca di un nodo ha un costo O(1) quando il nodo di destinazione è il nodo iniziale.

Complessità temporale nel caso medio per una lista doppiamente collegata:

1. L'inserimento all'inizio o alla fine costa O(1).
2. La cancellazione all'inizio o alla fine costa O(1).
3. La ricerca di un nodo ha un costo O(n), perché l'obiettivo può risiedere in qualsiasi punto della lista. Qui, n è il numero totale di nodi.

La complessità temporale nel caso peggiore della lista doppiamente concatenata è la stessa del caso medio.

Complessità di memoria della lista doppiamente collegata

La complessità della memoria è O(n), dove n è il numero totale di nodi. Durante l'implementazione della lista concatenata, la memoria deve essere liberata. Altrimenti, liste concatenate più grandi causano perdite di memoria.

Applicazioni delle liste doppiamente concatenate

Le liste doppiamente concatenate sono alla base di diverse strutture dati del mondo reale perché l'attraversamento bidirezionale semplifica molte operazioni comuni.

• Cache LRU: Le cache Least-Recently-Used utilizzano una lista doppiamente concatenata con una mappa hash per lo spostamento in avanti e l'eliminazione in O(1).
• Cronologia del browser: La navigazione avanti e indietro consente di scorrere l'elenco collegato in entrambe le direzioni.
• Stack Annulla e Ripristina: Editor e IDE track versioni del documento con puntatori precedente e successivo.
• Deque: DoubleLe code con terminazione - eseguono operazioni di push e pop da entrambe le estremità in tempo O(1).
• Playlist musicali: Continua e successivo tracI pulsanti k si basano su puntatori avanti e indietro.

DOMANDE FREQUENTI