Elenco doppiamente collegato: C++, Python (Esempio di codice)
Sara Chen
Cos'è una lista doppiamente collegata?
In un elenco doppiamente collegato, ogni nodo ha collegamenti sia al nodo precedente che a quello successivo. Ogni nodo è costituito da tre elementi: uno contiene i dati e altri due sono i puntatori del nodo successivo e precedente. Questi due puntatori ci aiutano ad andare avanti o indietro da un nodo particolare.
Ecco la struttura di base dell'elenco doppiamente collegato.
Ogni lista concatenata ha un nodo testa e uno coda. Il nodo Head non ha un nodo “prev” (puntatore precedente) e il nodo tail non ha un nodo “next”.
Ecco alcuni termini importanti per un elenco doppiamente collegato:
- 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: Viene utilizzato per archiviare i dati in un nodo. I “dati” possono contenere altro Strutture dati dentro. Ad esempio, stringa, dizionario, set, hashmap, ecc. possono essere archiviati in "Dati".
Ecco la struttura di base di un singolo nodo nella lista doppiamente collegata:
Operazioni della lista doppiamente collegata
Le operazioni di un elenco doppiamente collegato includono l'aggiunta e l'eliminazione di nodi, l'inserimento e la rimozione di nodi e l'attraversamento dell'elenco collegato dall'alto verso il basso.
Ecco l'elenco delle operazioni che possiamo implementare utilizzando la lista doppiamente collegata:
- Inserimento davanti
- Inserimento nella coda o 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
Vedremo l'implementazione e lo pseudocodice per tutte le operazioni sopra.
Inserimento davanti alla lista doppiamente collegata
L'inserimento in primo piano significa che dobbiamo creare un nodo nell'elenco collegato e posizionarlo all'inizio dell'elenco collegato.
Ad esempio, c'è un dato nodo "15". Dobbiamo aggiungerlo al nodo head.
Ecco due condizioni importanti durante l'esecuzione di questa operazione:
- Il nuovo nodo sarà il nodo principale se non è presente alcun nodo nella lista doppiamente collegata.
- Se esiste già un nodo testa, la testa precedente verrà sostituita dal nuovo nodo.
Ecco lo pseudo-codice per questa operazione:
function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead
Inserimento alla fine della Lista Doppiamente Collegata
"Inserimento alla fine" significa che creeremo un nodo nell'elenco collegato e lo posizioneremo alla fine.
Per eseguire ciò possiamo utilizzare due metodi:
- Metodo 1: Inizia a scorrere dall'inizio della lista doppiamente collegata fino a quando il "successivo" diventa nullo. Quindi collega il nuovo nodo con il “successivo”.
- Metodo 2: Prendi l'ultimo nodo della lista doppiamente collegata. Quindi, il nodo "successivo" dell'ultimo nodo si collegherà al nuovo nodo. Ora, il nuovo nodo sarà il nodo di coda.
Ecco lo pseudo-codice per l'inserimento nel nodo coda:
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
Inserimento dopo un nodo
Supponiamo di avere una lista doppiamente concatenata come la seguente:
Vogliamo inserire un dato nodo che verrà collegato dopo il nodo, che ha il valore di “12”.
Ecco i passaggi per questo:
Passo 1) Attraversare 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". Il nodo “successivo” del nuovo nodo sarà 15.
Ecco lo pseudo-codice per inserire un nodo dopo un nodo nell'elenco doppiamente collegato:
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
Inserimento prima di un nodo
Questa operazione è più simile all'“inserimento dopo un nodo”. Dobbiamo cercare il valore di un nodo specifico per eseguire questa operazione. Quindi creeremo un nuovo nodo e lo inseriremo prima del nodo cercato.
Diciamo di voler inserire un dato nodo “15” prima del nodo “12”. Quindi ecco i passaggi per farlo:
Passo 1) Attraversa l'elenco collegato dal nodo testa al nodo coda.
Passo 2) Controlla se il puntatore successivo del nodo corrente ha il valore "12" o meno.
Passo 3) Inserisci il nuovo nodo come nodo “successivo” del nodo corrente.
Ecco lo pseudo-codice per inserire un nodo prima di un nodo nella lista doppiamente collegata:
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
Elimina l'inizio dell'elenco doppiamente collegato
Il nodo principale nell'elenco doppiamente collegato che non ha alcun nodo precedente. Quindi, il puntatore successivo sarà il nuovo nodo head se vogliamo eliminare il nodo head. Dobbiamo anche liberare la memoria occupata da un nodo durante l'eliminazione di un nodo.
Ecco i passaggi per eliminare il nodo head:
Passo 1) Assegna una variabile al nodo head corrente.
Passo 2) Visita il nodo "successivo" del nodo head corrente e imposta il nodo "precedente" (puntatore precedente) come "NULL". Ciò significa che stiamo disconnettendo il secondo nodo dal primo nodo.
Passo 3) Liberare la memoria occupata dal nodo head precedente.
Ecco lo pseudo-codice per eliminare la testa da una lista doppiamente collegata:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
È necessario eliminare la memoria allocata dopo aver eseguito qualsiasi tipo di operazione di eliminazione. Altrimenti, durante l'intero runtime del programma, la memoria per il blocco eliminato rimarrà occupata. Nessun'altra applicazione può utilizzare quel segmento di memoria.
Elimina la coda dell'elenco doppiamente collegato.
Questa operazione è simile alla cancellazione della testa. Qui, al posto della testa, dobbiamo eliminare la coda. Per identificare un nodo come nodo di coda, dovremmo controllare se il puntatore successivo o il nodo successivo è nullo o meno. Dopo aver eliminato la coda, dobbiamo liberare la memoria.
Questa operazione è detta anche “cancellazione dal retro”.
Ecco i passaggi per eseguire questa operazione:
Passo 1) Attraversare fino al nodo finale della lista doppiamente concatenata.
Passo 2) Assegna una variabile o un puntatore al nodo coda.
Passo 3) Rendi NULL il nodo "successivo" e libera la memoria del nodo coda.
Ecco lo pseudo-codice per eliminare il nodo coda:
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
Cerca ed elimina un nodo dalla lista doppiamente collegata
Questa operazione ci consente di cercare i dati di un nodo specifico ed eliminare quel nodo. Dobbiamo eseguire una ricerca lineare poiché l'elenco collegato è una struttura di dati lineare. Dopo l'eliminazione, dobbiamo anche liberare la memoria.
Ecco i passaggi per cercare ed eliminare un nodo nella lista doppiamente concatenata:
Passo 1) Attraversa l'elenco collegato dall'inizio finché il valore del nodo non equivale all'elemento di ricerca.
Passo 2) Assegna una variabile "deleteNode" al nodo corrispondente.
Passo 3) Assegna il nodo precedente del “deleteNode” al nodo successivo.
Passo 4) Liberare la memoria del “deleteNode”
Ecco lo pseudocodice per cercare ed eliminare un nodo da una lista concatenata:
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
Attraversa un elenco doppiamente collegato da avanti
Per attraversare dal nodo head e scorrere il nodo successivo finché non troviamo "NULL". Mentre attraversiamo ciascun nodo, possiamo stampare il valore del nodo. Ecco i passaggi per la traslazione dalla parte anteriore (direzione in avanti):
Passo 1) Assegna un puntatore o una variabile al nodo head corrente.
Passo 2) Iterare al nodo successivo della testa fino a ottenere "NULL"
Passo 3) Stampa i dati del nodo in ogni iterazione.
Passo 4) Restituisce il nodo principale.
Ecco lo pseudo-codice per attraversare una lista doppiamente collegata dalla parte anteriore:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
In questo caso la restituzione non è obbligatoria. Ma è buona norma restituire il nodo head dopo le operazioni.
Attraversa un elenco doppiamente collegato dall'indietro
Questa operazione è l'inverso della traversata frontale. L'approccio è lo stesso con una piccola differenza. Dobbiamo attraversare fino al nodo finale e poi attraversare dal nodo finale al nodo anteriore.
Ecco i passaggi per attraversare un elenco doppiamente collegato dal retro:
Passo 1) Attraversare fino a raggiungere il nodo della coda.
Passo 2) Dal nodo di coda, lo attraverseremo finché non otterremo il nodo precedente come “NULL”. Il “prev” (puntatore precedente) sarà nullo per il nodo head
Passo 3) Ad ogni iterazione, stamperemo i dati del nodo.
Ecco lo pseudo-codice per l'attraversamento da dietro:
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
Differenza tra elenco collegato singolarmente e doppiamente
La differenza principale tra l'elenco Singly e l'elenco Doubly Linked è il numero di collegamenti.
Ecco la differenza tra i nodi di una lista concatenata singolarmente e la struttura dei nodi della lista concatenata doppia:
| Settore | Elenco collegato singolarmente | Elenco doppiamente collegato |
|---|---|---|
| Structure | Elenco collegato singolarmente ha un campo dati e un collegamento al nodo successivo. | L'elenco doppiamente collegato ha un campo dati e due collegamenti. Uno per il nodo precedente e un altro per il nodo successivo. |
| Traversal | Può spostarsi solo dalla testa alla coda. | Può spostarsi sia in avanti che all'indietro. |
| Memorie | Occupa meno memoria. | Occupa più memoria di un elenco collegato singolarmente. |
| Accessibilità | Gli elenchi collegati singolarmente sono meno efficienti poiché utilizzano un solo collegamento al nodo successivo. Non è presente alcun collegamento per il nodo precedente. | Gli elenchi concatenati doppiamente sono più efficienti degli elenchi concatenati singolarmente. |
Elenco doppiamente collegato in 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);
}
Uscita
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
Elenco doppiamente collegato in 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()
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
In genere, la complessità temporale si divide in tre tipi.
Essi sono:
- Caso migliore
- Caso medio
- Caso peggiore
Complessità temporale nel caso migliore per una lista doppiamente collegata:
- L'inserimento in testa o coda costerà O(1). Perché non abbiamo bisogno di attraversare all'interno della lista concatenata. Il puntatore di testa e di coda può darci accesso al nodo di testa e di coda con complessità temporale O(1).
- La cancellazione in testa o in coda costerà O(1).
- La ricerca di un nodo avrà una complessità temporale di O(1). Poiché il nodo di destinazione può essere il nodo principale.
Complessità temporale nel caso medio per una lista doppiamente collegata:
- L'inserimento in testa o in coda avrà una complessità temporale di costo O(1).
- L'eliminazione in testa o in coda avrà una complessità temporale di costo O(1).
- La ricerca di un nodo avrà una complessità temporale di O(n). Poiché l'elemento di ricerca può risiedere ovunque nella lista concatenata. Qui, "n" è il nodo totale presente nella lista concatenata.
La complessità temporale nel caso peggiore della lista doppiamente concatenata sarà 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 dobbiamo liberare la memoria che abbiamo utilizzato. Altrimenti, per una lista concatenata più grande, si verificheranno perdite di memoria.
Sommario
- Una lista concatenata è una sorta di struttura dati lineare, una raccolta di dati rappresentati in modo lineare.
- Un elenco doppiamente collegato è un tipo di elenco collegato in cui un nodo ha collegamenti sia con il nodo precedente che con quello successivo.
- L'elenco doppiamente collegato contiene tutte le operazioni come l'aggiunta di un nodo, l'eliminazione di un nodo, l'inserimento di un nodo dopo o prima di un altro nodo e l'attraversamento dell'elenco collegato dalla testa alla coda.
- L'elenco doppiamente collegato ha un campo dati e due collegamenti. Uno per il nodo precedente e un altro per il nodo successivo.
- Complessità della lista doppiamente collegata caso migliore, caso medio
- E nel peggiore dei casi.
