Dvostruko povezani popis: C++, Python (Code Primjer)

Što je dvostruko povezana lista?

U dvostruko povezanoj listi, svaki čvor ima veze i na prethodni i na sljedeći čvor. Svaki čvor sastoji se od tri elementa: jedan sadrži podatke, a druga dva su pokazivači na sljedeći i prethodni čvor. Ova dva pokazivača pomažu u kretanju naprijed ili natrag od određenog čvora.

Evo osnovne strukture dvostruko povezane liste.

Struktura dvostruko povezane liste

Svaka povezana lista ima početni i krajnji čvor. Početni čvor nema pret (prethodni pokazivač) čvor, a repni čvor nema sljedeći čvor.

Evo nekoliko važnih pojmova za dvostruko povezane liste:

• 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 čvoru. Podaci mogu sadržavati i druge Strukture podataka unutar njega. Na primjer, string, rječnik, skup, hashmap i druge strukture mogu se pohraniti u podatkovno polje.

Evo osnovne strukture jednog čvora u dvostruko povezanoj listi:

Struktura čvora u dvostruko povezanoj listi

Operacije dvostruko povezanog popisa

Operacije dvostruko povezane liste uključuju dodavanje, brisanje, umetanje i uklanjanje čvorova, kao i kretanje po listi od vrha prema dnu ili od dna prema vrhu.

Evo popisa operacija koje se mogu implementirati na dvostruko povezanoj listi:

• Umetanje ispred
• Umetanje na repu ili posljednjem čvoru
• 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

Implementacija i pseudokod za svaku od ovih operacija slijede u nastavku.

Umetanje ispred dvostruko povezane liste

Umetanje ispred znači stvaranje čvora u povezanoj listi i njegovo postavljanje na početak liste.

Na primjer, postoji zadani čvor 15Potrebno ga je dodati kao glavni čvor.

Prilikom izvođenja ove operacije primjenjuju se dva važna uvjeta:

1. Novi čvor postaje glavni čvor ako je dvostruko povezana lista prazna.
2. Ako već postoji glavni čvor, prethodni glavni čvor zamjenjuje se 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 u prednji čvor

Umetanje na kraj dvostruko povezane liste

Umetanje na kraj znači stvaranje čvora u povezanoj listi i njegovo postavljanje na rep.

Ovu operaciju izvode dvije metode:

• Metoda 1: Počnite pregledavati od početka dvostruko povezane liste sve do sljedeći postaje null. Zatim povežite novi čvor s sljedeći pokazivač.
• Metoda 2: Uzmite posljednji čvor dvostruko povezane liste. Zatim, sljedeći Pokazivač zadnjeg čvora pokazuje na novi čvor. Novi čvor postaje repni čvor.

Evo pseudokoda za umetanje na repnom čvoru:

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

Umetanje na kraj povezanog popisa

Umetanje nakon čvora

Razmotrite postojeću dvostruko povezanu listu kao što je sljedeća:

Cilj je umetnuti zadani čvor koji će biti povezan nakon čvora s vrijednošću 12.

Korak 1) Prijeđite od početka do zadnjeg čvora. Provjerite koji čvor ima vrijednost 12.

Korak 2) Stvorite 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 povezanoj listi:

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

Umetanje nakon čvora

Umetanje prije čvora

Ova operacija je slična umetanju nakon čvora. Pretražuje se određena vrijednost čvora, zatim se stvara novi čvor i umeće prije traženog čvora.

Za umetanje određenog čvora 15 prije čvora 12, prati ove korake:

Korak 1) Pređite povezanim popisom od glavnog čvora do repnog čvora.

Korak 2) Provjeri ima li sljedeći pokazivač trenutnog čvora vrijednost 12.

Korak 3) Umetnite novi čvor kao sljedeći čvor trenutnog čvora.

Evo pseudokoda za umetanje čvora prije čvora u dvostruko povezanoj listi:

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

Umetanje čvora ispred čvora

Izbriši zaglavlje dvostruko povezane liste

Glavni čvor u dvostruko povezanoj listi nema prethodnih čvorova. Dakle, sljedeći Pokazivač postaje novi glavni čvor kada se trenutni glavni čvor ukloni. Također je potrebno osloboditi memoriju koju zauzima izbrisani č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 pret pokazivač NULL. Ovo odvaja drugi čvor od prvog čvora.

Korak 3) Oslobodite memoriju koju je zauzimao prethodni glavni čvor.

Evo pseudokoda za brisanje glave iz dvostruko povezane liste:

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

Brisanje glavnog čvora

Nakon bilo kakvog brisanja potrebno je osloboditi dodijeljenu memoriju. U suprotnom, memorija za izbrisani blok ostaje zauzeta tijekom cijelog izvođenja programa i nijedna druga aplikacija ne može koristiti taj segment memorije.

Izbriši rep dvostruko povezane liste

Ova operacija je slična brisanju glave. Umjesto glave, uklanja se rep. Da bi se čvor identificirao kao rep, provjerite je li sljedeći pokazivač null. Nakon brisanja repa, memorija se mora osloboditi.

Ova operacija je također poznata kao brisanje s leđa.

Evo koraka kako to učiniti:

Korak 1) Pomičite se do repnog čvora dvostruko povezane liste.

Korak 2) Dodijelite varijablu ili pokazivač repnom čvoru.

Korak 3) Postavi sljedeći pokazivač na NULL i oslobodi 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
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

Pretraživanje i brisanje čvora s dvostruko povezane liste

Ova operacija traži određenu vrijednost čvora i briše taj čvor. Linearno pretraživanje je potrebno jer je povezani popis linearna struktura podataka. Nakon brisanja, memorija se mora osloboditi.

Evo koraka za pretraživanje i brisanje čvora u dvostruko povezanoj listi:

Korak 1) Prolazite kroz povezanu listu od početka dok vrijednost čvora ne bude jednaka traženoj stavci.

Korak 2) Dodijeli varijablu brisanje čvora do odgovarajućeg čvora.

Korak 3) Poveži prethodni čvor od brisanje čvora na sljedeći čvor i postavi sljedeći čvor pret pokazivač na prethodni čvor.

Korak 4) Oslobodite sjećanje na brisanje čvora.

Evo pseudokoda za pretraživanje i brisanje čvora s povezane liste:

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

Operacija pretraživanja i brisanja

Prolazak kroz dvostruko povezanu listu od naprijed

Prijelaz od glavnog čvora iterira preko sljedećeg čvora dok se ne pronađe NULL. Tijekom prelaska kroz svaki čvor, vrijednost se može ispisati. Evo koraka za prelazak u smjeru naprijed:

Korak 1) Dodijelite pokazivač ili varijablu trenutnom glavnom čvoru.

Korak 2) Iteriraj do sljedećeg čvora glave dok ne dobiješ NULL.

Korak 3) Ispišite podatke o čvorovima u svakoj iteraciji.

Korak 4) Vratite glavni čvor.

Evo pseudokoda za obilazak dvostruko povezane liste s početka:

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

Povratak nije obavezan. Međutim, vraćanje glavnog čvora nakon operacija je dobra praksa.

Prolazak kroz dvostruko povezanu listu od unatrag

Ova operacija je inverzna od kretanja sprijeda. Pristup je isti s jednom malom razlikom: prvo dođite do krajnjeg čvora, a zatim hodajte unatrag do vrha koristeći pret pokazivač.

Evo koraka za obilazak dvostruko povezane liste s leđa:

Korak 1) Krećite se dok se ne dođe do repnog čvora.

Korak 2) Od repnog čvora, pređite pomoću pret dok prethodni čvor ne postane NULL. pret Pokazivač je null za glavni čvor.

Korak 3) U svakoj iteraciji, ispišite podatke o čvoru.

Evo pseudokoda za prelazak s leđa:

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

Razlika između jednostruko i dvostruko povezane liste

Glavna razlika između jednostruko povezane liste i dvostruko povezane liste je broj veza koje svaki čvor sadrži.

Evo razlike između čvorova jednostruko povezane liste i dvostruko povezane liste:

Dvostruko povezani popis u C++

Ispod je potpuni C++ Implementacija dvostruko povezane liste s operacijama umetanja, brisanja, pretraživanja i pomicanja.

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

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

Dvostruko povezani popis u Python

Ispod je potpuni Python implementacija dvostruko povezane liste korištenjem klasa za čvorove i same liste.

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

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

Vremenska složenost se općenito dijeli na tri vrste: najbolji slučaj, prosječni slučaj i najgori slučaj.

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

1. Umetanje na početku ili kraju liste košta O(1) jer nije potreban prolaz unutar povezane liste. Pokazivači na početku i kraju liste daju izravan pristup početnim i krajnjim čvorovima.
2. Brisanje na početku ili kraju skupa košta O(1).
3. Pretraživanje čvora košta O(1) kada je ciljni čvor glavni čvor.

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

1. Umetanje na početku ili kraju košta O(1).
2. Brisanje na početku ili kraju skupa košta O(1).
3. Pretraživanje čvora košta O(n), jer se cilj može nalaziti bilo gdje na popisu. Ovdje, n je ukupan broj čvorova.

Vremenska složenost dvostruko povezane liste u najgorem slučaju ista je kao i u prosječnom slučaju.

Memorijska složenost dvostruko povezanog popisa

Složenost memorije je O(n), gdje je n je ukupan broj čvorova. Tijekom implementacije povezane liste, memorija se mora osloboditi. Inače, veće povezane liste uzrokuju curenje memorije.

Primjene dvostruko povezane liste

Dvostruko povezane liste pokreću nekoliko stvarnih struktura podataka jer dvosmjerni prolaz pojednostavljuje mnoge uobičajene operacije.

• LRU predmemorija: Najmanje korištene predmemorije koriste dvostruko povezanu listu s hash mapom za O(1) premještanje na početak i deložiranje.
• Povijest preglednika: Navigacija naprijed i natrag omogućuje kretanje po povezanom popisu u oba smjera.
• Poništi i ponovi nizove: Urednici i IDE-ovi track verzija dokumenata s pokazivačima na prethodno i sljedeće.
• Deque: DoubleRedovi s krajevima se guraju i otvaraju s oba kraja u vremenu O(1).
• Glazbene liste za reprodukciju: Prethodno i sljedeće tracGumbi k oslanjaju se na pokazivače naprijed i natrag.

Pitanja i odgovori