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:

1. Novi čvor će biti glavni čvor ako nema čvora na dvostruko povezanom popisu.
2. 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:

1. Najbolji slučaj
2. Prosječan slučaj
3. Najgori slučaj

Vremenska složenost u najboljem slučaju za dvostruko povezani popis:

1. 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.
2. Brisanje na čelu ili repu koštat će O(1).
3. 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:

1. Umetanje na čelu ili repu imat će vremensku složenost troška O(1).
2. Brisanje na čelu ili repu imat će vremensku složenost troška O(1).
3. 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.