Dvostruko povezani popis: C++, Python (Primjer koda)
Što je dvostruko povezana lista?
U dvostruko povezanom popisu, svaki čvor ima veze i na prethodni i na sljedeći čvor. Svaki čvor se sastoji od tri elementa: jedan sadrži podatke, a druga dva su pokazivači sljedećeg i prethodnog čvora. Ova dva pokazivača nam pomažu da idemo naprijed ili nazad od određenog čvora.
Ovdje je osnovna struktura dvostruko povezane liste.

Svaki povezani popis ima glavni i zadnji čvor. Glavni čvor nema "prethodni" (prethodni pokazivač) čvor, a repni čvor nema "sljedeći" čvor.
Evo nekoliko važnih pojmova za dvostruko povezani popis:
- Prethodna: Svaki čvor je povezan sa svojim prethodnim čvorom. Koristi se kao pokazivač ili poveznica.
- Sljedeći: Svaki čvor je povezan sa svojim sljedećim čvorom. Koristi se kao pokazivač ili poveznica.
- Podaci: Ovo se koristi za pohranu podataka u čvor. "Podaci" mogu sadržavati druge Strukture podataka unutar. Na primjer, niz, rječnik, skup, hashmapa itd. mogu se pohraniti u "Podatke".
Ovdje je osnovna struktura jednog čvora na dvostruko povezanom popisu:

Operacije dvostruko povezanog popisa
Operacije dvostruko povezanog popisa uključuju dodavanje i brisanje čvorova, umetanje i uklanjanje čvorova i prelaženje povezanog popisa od vrha do dna.
Evo popisa operacija koje možemo implementirati pomoću dvostruko povezanog popisa:
- Umetanje ispred
- Umetanje u rep ili zadnji čvor
- Umetanje nakon čvora
- Umetanje prije čvora
- Brisanje sprijeda
- Brisanje iz repa
- Pretraživanje i brisanje čvora
- Traverza od glave do repa
- Pređite repom u glavu
Vidjet ćemo implementaciju i pseudokod za sve gore navedene operacije.
Umetanje ispred dvostruko povezane liste
Umetanje ispred znači da moramo stvoriti čvor na povezanom popisu i postaviti ga na početak povezanog popisa.
Na primjer, postoji čvor "15". Ovo moramo dodati u glavni čvor.
Evo dva važna uvjeta pri izvođenju ove operacije:
- Novi čvor će biti glavni čvor ako nema čvora na dvostruko povezanom popisu.
- Ako već postoji glavni čvor, prethodni će biti zamijenjen novim čvorom.
Evo pseudokoda za ovu operaciju:
function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead
Umetanje na kraj dvostruko povezane liste
"Umetanje na kraju" znači da ćemo stvoriti čvor na povezanoj listi i postaviti ga na kraj.
Da bismo to izveli, možemo koristiti dvije metode:
- Metoda 1: Počnite prelaziti od glave dvostruko povezane liste dok "sljedeće" ne postane null. Zatim povežite novi čvor sa "sljedećim".
- Metoda 2: Uzmite posljednji čvor dvostruko povezane liste. Zatim će se "sljedeći" čvor posljednjeg čvora povezati s novim čvorom. Sada će novi čvor biti repni čvor.
Evo pseudokoda za umetanje u repni čvor:
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
Umetanje nakon čvora
Recimo da imamo postojeći dvostruko povezani popis poput sljedećeg:
Želimo umetnuti dati čvor koji će biti povezan nakon čvora, koji ima vrijednost "12".
Evo koraka za to:
Korak 1) Prijeđi od glave do posljednjeg čvora. Provjerite koji čvor ima vrijednost "12".
Korak 2) Napravite novi čvor i dodijelite ga kao sljedeći pokazivač čvora “12”. "Sljedeći" čvor novog čvora bit će 15.
Evo pseudokoda za umetanje čvora nakon čvora u dvostruko povezanu listu:
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
Umetanje prije čvora
Ova je operacija sličnija "umetanju nakon čvora". Moramo potražiti vrijednost određenog čvora da bismo to izveli. Zatim ćemo stvoriti novi čvor i umetnuti ga ispred traženog čvora.
Recimo da želimo umetnuti dati čvor “15” prije čvora “12”. Zatim evo koraka za to:
Korak 1) Pređite povezanim popisom od glavnog čvora do repnog čvora.
Korak 2) Provjerite ima li sljedeći pokazivač trenutnog čvora vrijednost “12” ili ne.
Korak 3) Umetnite novi čvor kao "sljedeći" čvor trenutnog čvora.
Evo pseudokoda za umetanje čvora ispred čvora na dvostruko povezanom popisu:
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
Izbrišite glavu dvostruko povezane liste
Glavni čvor na dvostruko povezanom popisu koji nema prethodni čvor. Dakle, sljedeći pokazivač će biti novi glavni čvor ako želimo izbrisati glavni čvor. Također moramo osloboditi memoriju koju zauzima čvor dok brišemo čvor.
Evo koraka za brisanje glavnog čvora:
Korak 1) Dodijelite varijablu trenutnom glavnom čvoru.
Korak 2) Posjetite “sljedeći” čvor trenutnog glavnog čvora i napravite “prev” (prethodni pokazivač) čvor kao ''NULL''. To znači da odspajamo drugi čvor od prvog čvora.
Korak 3) Oslobodite memoriju koju je zauzeo prethodni glavni čvor.
Evo pseudokoda za brisanje glave s dvostruko povezane liste:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
Potrebno je izbrisati dodijeljenu memoriju nakon izvođenja bilo koje operacije brisanja. U protivnom, tijekom cijelog vremena izvođenja programa, memorija za izbrisani blok ostat će zauzeta. Nijedna druga aplikacija ne može koristiti taj segment memorije.
Izbrišite rep dvostruko povezane liste.
Ova operacija je ista kao i brisanje glave. Ovdje, umjesto glave, moramo izbrisati rep. Da bismo identificirali čvor kao repni čvor, trebali bismo provjeriti je li sljedeći pokazivač ili sljedeći čvor null ili ne. Nakon brisanja repa, moramo osloboditi memoriju.
Ova operacija je također poznata kao "brisanje s leđa".
Evo koraka za to:
Korak 1) Pređite do repnog čvora dvostruko povezane liste.
Korak 2) Dodijelite varijablu ili pokazivač repnom čvoru.
Korak 3) Napravite "sljedeći" čvor kao NULL i oslobodite memoriju repnog čvora.
Evo pseudokoda za brisanje repnog čvora:
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
Pretražite i izbrišite čvor s dvostruko povezanog popisa
Ova nam operacija omogućuje traženje podataka određenog čvora i brisanje tog čvora. Moramo izvršiti linearno pretraživanje jer je povezani popis linearna struktura podataka. Nakon brisanja trebamo osloboditi i memoriju.
Evo koraka za pretraživanje i brisanje čvora na dvostruko povezanom popisu:
Korak 1) Pređite povezanim popisom od glave sve dok vrijednost čvora ne bude jednaka stavci pretraživanja.
Korak 2) Dodijelite varijablu "deleteNode" odgovarajućem čvoru.
Korak 3) Dodijelite prethodni čvor "deleteNode" sljedećem čvoru.
Korak 4) Oslobodite memoriju za "deleteNode"
Evo pseudokoda za pretraživanje i brisanje čvora s povezanog popisa:
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
Prelazi dvostruko povezani popis od naprijed
Za kretanje od glavnog čvora i ponavljanje preko sljedećeg čvora dok ne pronađemo "NULL". Dok obilazimo svaki čvor, možemo ispisati vrijednost čvora. Evo koraka za kretanje sprijeda (smjer prema naprijed):
Korak 1) Dodijelite pokazivač ili varijablu trenutnom glavnom čvoru.
Korak 2) Iterirajte do sljedećeg čvora glave dok ne dobijete "NULL"
Korak 3) Ispišite podatke čvora u svakoj iteraciji.
Korak 4) Vratite glavni čvor.
Evo pseudokoda za obilazak dvostruko povezanog popisa s prednje strane:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
Ovdje vraćanje nije obavezno. Ali dobra je praksa vratiti čvor glave nakon operacije.
Pređite dvostruko povezanu listu odnatrag
Ova operacija je obratna od prijelaza sprijeda. Pristup je isti s malom razlikom. Moramo prijeći do krajnjeg čvora i zatim prijeći od krajnjeg čvora do prednjeg čvora.
Evo koraka za obilazak dvostruko povezanog popisa odostraga:
Korak 1) Prelazimo dok ne dođemo do repnog čvora.
Korak 2) Od repnog čvora, prelazit ćemo sve dok prethodni čvor ne dobijemo kao "NULL". "prev" (prethodni pokazivač) bit će null za glavni čvor
Korak 3) U svakoj iteraciji ispisat ćemo podatke čvora.
Evo pseudo-koda za kretanje odostraga:
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
Razlika između jednostruko i dvostruko povezanih popisa
Glavna razlika između pojedinačnog i dvostruko povezanog popisa je broj poveznica.
Evo razlike između čvorova jednostruko povezanog popisa i strukture čvorova dvostruko povezanog popisa:
Polje | Pojedinačno povezani popis | Dvostruko povezana lista |
---|---|---|
Struktura | Pojedinačno povezani popis ima jedno podatkovno polje i jednu vezu na sljedeći čvor. | Dvostruko povezani popis ima jedno podatkovno polje i dvije veze. Jedan za prethodni čvor i drugi za sljedeći čvor. |
obuhvaćanje | Može ići samo od glave do repa. | Može se kretati i naprijed i natrag. |
memorija | Zauzima manje memorije. | Zauzima više memorije od pojedinačno povezanog popisa. |
Pristupačnost | Pojedinačno povezani popisi manje su učinkoviti jer koriste samo jednu vezu do sljedećeg čvora. Ne postoji poveznica za prethodni čvor. | Dvostruko povezani popisi učinkovitiji su od jednostruko povezanih popisa. |
Dvostruko povezani popis u 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); }
Izlaz
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
Dvostruko povezani popis u 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()
Izlaz
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
Složenost dvostruko povezane liste
Općenito, vremenska složenost se dijeli na tri vrste.
Oni su:
- Najbolji slučaj
- Prosječan slučaj
- Najgori slučaj
Vremenska složenost u najboljem slučaju za dvostruko povezani popis:
- Umetanje u glavu ili rep će koštati O(1). Jer ne trebamo prelaziti unutar povezanog popisa. Pokazivač glave i repa može nam dati pristup čvoru glave i repa s O(1) vremenskom složenošću.
- Brisanje na čelu ili repu koštat će O(1).
- Traženje čvora imat će vremensku složenost O(1). Budući da ciljni čvor može biti glavni čvor.
Vremenska složenost u prosječnom slučaju za dvostruko povezani popis:
- Umetanje na čelu ili repu imat će vremensku složenost troška O(1).
- Brisanje na čelu ili repu imat će vremensku složenost troška O(1).
- Traženje čvora imat će vremensku složenost O(n). Budući da se stavka pretraživanja može nalaziti bilo gdje između povezanog popisa. Ovdje je "n" ukupni čvor prisutan na povezanom popisu.
Vremenska složenost dvostruko povezane liste u najgorem slučaju bit će ista kao i prosječni slučaj.
Memorijska složenost dvostruko povezanog popisa
Složenost memorije je O(n), gdje je "n" ukupan broj čvorova. Tijekom implementacije povezane liste moramo osloboditi memoriju koju smo koristili. U suprotnom, za veći povezani popis, to će uzrokovati curenje memorije.
Rezime
- Povezani popis vrsta je linearne strukture podataka, zbirka podataka predstavljenih na linearan način.
- Dvostruko povezani popis vrsta je povezanog popisa gdje čvor ima veze i s prethodnim i sa sljedećim čvorom.
- Dvostruko povezani popis sadrži sve operacije kao što su dodavanje čvora, brisanje čvora, umetanje čvora iza ili prije drugog čvora i prelaženje povezanog popisa od glave do repa.
- Dvostruko povezani popis ima jedno podatkovno polje i dvije veze. Jedan za prethodni čvor i drugi za sljedeći čvor.
- Složenost dvostruko povezane liste Najbolji slučaj, prosječan slučaj
- I u najgorem slučaju.