Meni

Dvostruko povezana struktura podataka popisa na C ++ s ilustracijom

  • Glavni
  • Ostalo
  • Dvostruko povezana struktura podataka popisa na C ++ s ilustracijom

doubly linked list data structure c with illustration

Isprobajte Naš Instrument Za Uklanjanje Problema

Dubinski vodič na dvostruko povezanom popisu.

Dvostruko povezani popis varijacija je pojedinačno povezanog popisa. Svjesni smo da je pojedinačno povezani popis zbirka čvorova, pri čemu svaki čvor ima podatkovni dio i pokazivač koji pokazuje na sljedeći čvor.

Dvostruko povezan popis također je zbirka čvorova. Svaki se čvor ovdje sastoji od dijela podataka i dva pokazivača. Jedan pokazivač pokazuje na prethodni čvor, dok drugi pokazuje na sljedeći čvor.

=> Ovdje pogledajte temeljne vodiče za obuku za C ++.

DUPLO POVEZANI POPIS

Što ćete naučiti:

Dvostruko povezan na C ++

Kao i na pojedinačno povezanom popisu, i dvostruko povezani popis ima glavu i rep. Prethodni pokazivač glave postavljen je na NULL jer je ovo prvi čvor. Sljedeći pokazivač repnog čvora postavljen je na NULL jer je ovo posljednji čvor.

Osnovni izgled dvostruko povezanog popisa prikazan je na donjem dijagramu.

Osnovni izgled dvostruko povezanog popisa

Na gornjoj slici vidimo da svaki čvor ima dva pokazivača, jedan koji upućuje na prethodni, a drugi na sljedeći čvor. Samo prvi čvor (glava) ima svoj prethodni čvor postavljen na nulu, a posljednji čvor (rep) ima sljedeći pokazivač na nulu.

Kako dvostruko povezani popis sadrži dva pokazivača, tj. Prethodni i sljedeći, možemo ga preusmjeriti u smjerove naprijed i natrag. To je glavna prednost dvostruko povezanog popisa nad pojedinačno povezanim popisom.

koji je najbolji softver za baze podataka

Izjava

U deklaraciji u stilu C čvor dvostruko povezanog popisa predstavljen je na sljedeći način:

struct node { struct node *prev; int data; struct node *next; };

Osim gornje deklaracije, čvor na dvostruko povezanom popisu možemo predstaviti i kao klasu na C ++. Dvostruko povezani popis predstavljen je kao klasa kada u C ++ koristimo STL. Dvostruko povezani popis možemo implementirati i pomoću klase na Javi.

Osnovne operacije

Slijede neke od operacija koje možemo izvesti na dvostruko povezanom popisu.

Umetanje

Operacija umetanja dvostruko povezanog popisa umeće novi čvor u povezani popis. Ovisno o položaju na koji treba umetnuti novi čvor, možemo imati sljedeće operacije umetanja.

  • Umetak sprijeda - Umeće novi čvor kao prvi čvor.
  • Umetanje na kraju - Umeće novi čvor na kraju kao zadnji čvor.
  • Umetanje prije čvora - S obzirom na čvor, umeće novi čvor prije ovog čvora.
  • Umetanje nakon čvora - S obzirom na čvor, umeće novi čvor nakon ovog čvora.

Brisanje

Operacija brisanja briše čvor s određenog položaja na dvostruko povezanom popisu.

  • Brisanje prvog čvora - Briše prvi čvor s popisa
  • Brisanje posljednjeg čvora - Briše posljednji čvor s popisa.
  • Brisanje čvora s obzirom na podatke - S obzirom na podatke, operacija podudara podatke s podacima čvora na povezanom popisu i briše taj čvor.

Preokret

Prelazak je tehnika posjećivanja svakog čvora na povezanom popisu. Na dvostruko povezanom popisu imamo dvije vrste prijelaza jer imamo dva pokazivača s različitim smjerovima na dvostruko povezanom popisu.

  • Naprijed zaokret - Prijelaz se vrši pomoću sljedećeg pokazivača koji je u smjeru naprijed.
  • Povratni hod - Prijelaz se vrši pomoću prethodnog pokazivača koji je unatrag.

Obrnuto

Ova operacija preokreće čvorove na dvostruko povezanom popisu tako da prvi čvor postaje zadnji čvor, dok zadnji čvor postaje prvi čvor.

traži

Operacija pretraživanja na dvostruko povezanom popisu koristi se za traženje određenog čvora na povezanom popisu. U tu svrhu moramo prelaziti popis dok se ne pronađu odgovarajući podaci.

Umetanje

Umetnite čvor sprijeda

Umetnite čvor sprijeda

Umetanje novog čvora na čelo popisa prikazano je gore. Kao što se vidi, prethodni novi čvor N postavljen je na nulu. Glava pokazuje na novi čvor. Sljedeći pokazivač N sada pokazuje na N1, a prethodni od N1 koji je ranije ukazivao na Null sada pokazuje na N.

Umetnite čvor na kraju

Umetnite čvor na kraju

Umetanje čvora na kraj dvostruko povezanog popisa postiže se usmjeravanjem sljedećeg pokazivača novog čvora N na nulu. Prethodni pokazivač N usmjeren je na N5. Pokazatelj ‘Sljedeći’ N5 usmjeren je na N.

Umetnite čvor prije / nakon zadanog čvora

Umetnite čvor prije-iza zadanog čvora

Kao što je prikazano na gornjem dijagramu, kada moramo dodati čvor prije ili poslije određenog čvora, mijenjamo prethodne i sljedeće pokazivače na čvorove prije i poslije kako bismo prikladno usmjerili na novi čvor. Također, novi pokazivači na čvorove prikladno su usmjereni na postojeće čvorove.

Sljedeći program C ++ prikazuje sve gore navedene metode za umetanje čvorova na dvostruko povezan popis.

#include using namespace std; // A doubly linked list node struct Node { int data; struct Node* next; struct Node* prev; }; //inserts node at the front of the list void insert_front(struct Node** head, int new_data) { //allocate memory for New node struct Node* newNode = new Node; //assign data to new node newNode->data = new_data; //new node is head and previous is null, since we are adding at the front newNode->next = (*head); newNode->prev = NULL; //previous of head is new node if ((*head) != NULL) (*head)->prev = newNode; //head points to new node (*head) = newNode; } /* Given a node as prev_node, insert a new node after the given node */ void insert_After(struct Node* prev_node, int new_data) { //check if prev node is null if (prev_node == NULL) { coutnext = prev_node->next; //set next of prev node to newnode prev_node->next = newNode; //now set prev of newnode to prev node newNode->prev = prev_node; //set prev of new node's next to newnode if (newNode->next != NULL) newNode->next->prev = newNode; } //insert a new node at the end of the list void insert_end(struct Node** head, int new_data) { //allocate memory for node struct Node* newNode = new Node; struct Node* last = *head; //set last node value to head //set data for new node newNode->data = new_data; //new node is the last node , so set next of new node to null newNode->next = NULL; //check if list is empty, if yes make new node the head of list if (*head == NULL) { newNode->prev = NULL; *head = newNode; return; } //otherwise traverse the list to go to last node while (last->next != NULL) last = last->next; //set next of last to new node last->next = newNode; //set last to prev of new node newNode->prev = last; return; } // This function prints contents of linked list starting from the given node void displayList(struct Node* node) { struct Node* last; while (node != NULL) { coutnext; } if(node == NULL) cout

Izlaz:

Dvostruko povezan popis je sljedeći:

1020304050NULL

Gornji program izrađuje dvostruko povezan popis umetanjem čvorova pomoću tri metode umetanja, tj. Umetanjem čvora sprijeda, umetanjem čvora na kraju i umetanjem čvora nakon datog čvora.

Dalje, demonstriramo istu operaciju kao implementacija Jave.

// Java Class for Doubly Linked List class Doubly_linkedList { Node head; // list head /* Doubly Linked list Node*/ class Node { int data; Node prev; Node next; //create a new node using constructor Node(int d) { data = d; } } // insert a node at the front of the list public void insert_front(int new_data) { /* 1. allocate node * 2. put in the data */ Node new_Node = new Node(new_data); /* 3. Make next of new node as head and previous as NULL */ new_Node.next = head; new_Node.prev = null; /* 4. change prev of head node to new node */ if (head != null) head.prev = new_Node; /* 5. move the head to point to the new node */ head = new_Node; } //insert a node after the given prev node public void Insert_After(Node prev_Node, int new_data) { //check that prev node is not null if (prev_Node == null) { System.out.println('The previous node is required,it cannot be NULL '); return; } //allocate new node and set it to data Node newNode = new Node(new_data); //set next of newNode as next of prev node newNode.next = prev_Node.next; //set new node to next of prev node prev_Node.next = newNode; //set prev of newNode as prev node newNode.prev = prev_Node; //set prev of new node's next to newnode if (newNode.next != null) newNode.next.prev = newNode; } // Add a node at the end of the list void insert_end(int new_data) { //allocate the node and set the data Node newNode = new Node(new_data); Node last = head; //set last as the head //set next of new node to null since its the last node newNode.next = null; //set new node as head if the list is null if (head == null) { newNode.prev = null; head = newNode; return; } //if list is not null then traverse it till the last node and set last next to last while (last.next != null) last = last.next; last.next = newNode; //set last next to new node newNode.prev = last; //set last as prev of new node } // display the contents of linked list starting from the given node public void displaylist(Node node) { Node last = null; while (node != null) { System.out.print(node.data + ''); last = node; node = node.next; } if(node == null) System.out.print('null'); System.out.println(); } } class Main{ public static void main(String() args) { /* Start with the empty list */ Doubly_linkedList dll = new Doubly_linkedList(); // Insert 40. dll.insert_end(40); // Insert 20 at the beginning. dll.insert_front(20); // Insert 10 at the beginning. dll.insert_front(10); // Insert 50 at the end. dll.insert_end(50); // Insert 30, after 20. dll.Insert_After(dll.head.next, 30); System.out.println('Doubly linked list created is as follows: '); dll.displaylist(dll.head); } }

Izlaz:

Stvoren je dvostruko povezan popis:

pitanja i odgovori na intervjuu za devops za iskusne

1020304050null

Brisanje

Čvor se može izbrisati s dvostruko povezanog popisa s bilo kojeg položaja poput prednjeg, završnog ili bilo kojeg drugog zadanog položaja ili danih podataka.

Kada brišemo čvor s dvostruko povezanog popisa, prvo premjestimo pokazivač koji pokazuje na taj određeni čvor tako da prethodni i sljedeći čvorovi nemaju nikakve veze s čvorom koji treba izbrisati. Tada čvor možemo lako izbrisati.

Razmotrimo sljedeći dvostruko povezani popis s tri čvora A, B, C. Uzmimo u obzir da čvor B. moramo izbrisati

dvostruko povezani popis s tri čvora A, B, C

Kao što je prikazano u gornjoj seriji dijagrama, pokazali smo brisanje čvora B s datog povezanog popisa. Slijed rada ostaje isti, čak i ako je čvor prvi ili zadnji. Jedina briga koju treba poduzeti jest da će, u slučaju da se prvi čvor izbriše, prethodni pokazivač drugog čvora biti postavljen na nulu.

Slično tome, kada se zadnji čvor izbriše, sljedeći pokazivač prethodnog čvora bit će postavljen na nulu. Ako se između čvorova izbrišu, tada će slijed biti kao gore.

Ostavljamo program za brisanje čvora s dvostruko povezanog popisa. Imajte na umu da će implementacija biti na liniji implementacije umetanja.

Obrni dvostruko povezan popis

Obrtanje dvostruko povezanog popisa važna je operacija. U tome jednostavno zamijenimo prethodne i sljedeće pokazivače svih čvorova, a također zamijenimo pokazivače glave i repa.

Slijedi dvostruko povezan popis:

Obrnuti dvostruko povezani popis

Sljedeća implementacija C ++-a prikazuje Obrnuti dvostruko povezan popis.

#include using namespace std; //node declaration for doubly linked list struct Node { int data; struct Node *prev, *next; }; Node* newNode(int val) { Node* temp = new Node; temp->data = val; temp->prev = temp->next = nullptr; return temp; } void displayList(Node* head) { while (head->next != nullptr) { cout next; } cout next = *head; (*head)->prev = temp; (*head) = temp; } // reverse the doubly linked list void reverseList(Node** head) { Node* left = *head, * right = *head; // traverse entire list and set right next to right while (right->next != nullptr) right = right->next; //swap left and right data by moving them towards each other till they meet or cross while (left != right && left->prev != right) { // Swap left and right pointer data swap(left->data, right->data); // Advance left pointer left = left->next; // Advance right pointer right = right->prev; } } int main() { Node* headNode = newNode(5); insert(&headNode, 4); insert(&headNode, 3); insert(&headNode, 2); insert(&headNode, 1); cout << 'Original doubly linked list: ' << endl; displayList(headNode); cout << 'Reverse doubly linked list: ' << endl; reverseList(&headNode); displayList(headNode); return 0; }

Izlaz:

Izvorni dvostruko povezani popis:

1 2 3 4 5

Obrnuti dvostruko povezani popis:

5 4 3 2 1

Ovdje zamijenimo lijevi i desni pokazivač i pomičemo ih jedni prema drugima dok se ne sretnu ili ne prekriže. Tada se zamjenjuju prvi i posljednji čvorovi.

Sljedeći je program implementacija Jave za obrtanje dvostruko povezanog popisa. U ovom programu također koristimo zamjenu lijevog i desnog čvora kao što smo to učinili u našem prethodnom programu.

// Java Program to Reverse a doubly linked List using Data Swapping class Main{ static class Node { int data; Node prev, next; }; static Node newNode(int new_data) { Node temp = new Node(); temp.data = new_data; temp.prev = temp.next = null; return temp; } static void displayList(Node head) { while (head.next != null) { System.out.print(head.data+ ' '); head = head.next; } System.out.println( head.data ); } // Insert a new node at the head of the list static Node insert(Node head, int new_data) { Node temp = newNode(new_data); temp.next = head; (head).prev = temp; (head) = temp; return head; } // Function to reverse the list static Node reverseList(Node head) { Node left = head, right = head; // traverse the list, set right pointer to end of list while (right.next != null) right = right.next; // move left and right pointers and swap their data till they meet or cross each other while (left != right && left.prev != right) { // Swap data of left and right pointer int t = left.data; left.data = right.data; right.data = t; left = left.next; // Advance left pointer right = right.prev; // Advance right pointer } return head; } public static void main(String args()) { Node headNode = newNode(5); headNode = insert(headNode, 4); headNode = insert(headNode, 3); headNode = insert(headNode, 2); headNode = insert(headNode, 1); System.out.println('Original doubly linked list:'); displayList(headNode); System.out.println('Reversed doubly linked list:'); headNode=reverseList(headNode); displayList(headNode); } }

Izlaz:

Izvorni dvostruko povezani popis:

1 2 3 4 5

Obrnuti dvostruko povezani popis:

5 4 3 2 1

Prednosti / nedostaci pred pojedinačno povezanim popisom

Razmotrimo neke od prednosti i nedostataka dvostruko povezanog popisa u odnosu na pojedinačno povezani popis.

Prednosti:

  • Dvostruko povezani popis može se prelaziti u smjeru naprijed, kao i unatrag, za razliku od pojedinačno povezanog popisa koji se može prelaziti samo u smjeru naprijed.
  • Operacija brisanja na dvostruko povezanom popisu učinkovitija je u usporedbi s pojedinačnim popisom kada je dan čvor. U pojedinačno povezanom popisu, budući da nam je potreban prethodni čvor za brisanje datog čvora, ponekad moramo preći popis da bismo pronašli prethodni čvor. Ovo pogađa izvedbu.
  • Operacija umetanja može se lako izvršiti na dvostruko povezanom popisu u usporedbi s pojedinačno povezanim popisom.

Mane:

  • Kako dvostruko povezani popis sadrži još jedan dodatni pokazivač, tj. Prethodni, memorijski prostor koji zauzima dvostruko povezan popis veći je u usporedbi s pojedinačno povezanim popisom.
  • Budući da su prisutna dva pokazivača, tj. Prethodni i sljedeći, sve radnje izvedene na dvostruko povezanom popisu moraju se pobrinuti za te pokazivače i održavati ih, što rezultira uskim grlom u izvedbi.

Primjene dvostruko povezanih popisa

Dvostruko povezani popis može se primijeniti u različitim scenarijima i aplikacijama iz stvarnog života, kao što je objašnjeno u nastavku.

  • Špil karata u igri klasičan je primjer dvostruko povezanog popisa. S obzirom na to da svaka karta u špilu ima prethodnu i sljedeću kartu poredane uzastopno, ovaj špil karata može se lako predstaviti pomoću dvostruko povezanog popisa.
  • Povijest / predmemorija preglednika - Predmemorija preglednika ima zbirku URL-ova i njome se možete kretati pomoću gumba za naprijed i natrag još je jedan dobar primjer koji se može predstaviti kao dvostruko povezani popis.
  • Nedavno korišteni (MRU) također se mogu predstaviti kao dvostruko povezani popis.
  • Druge strukture podataka poput stogova, hash tablice, binarnog stabla također se mogu konstruirati ili programirati pomoću dvostruko povezanog popisa.

Zaključak

Dvostruko povezani popis varijacija je pojedinačno povezanog popisa. Razlikuje se od pojedinačno povezanog popisa po tome što svaki čvor sadrži dodatni pokazivač na prethodni čvor zajedno sa sljedećim pokazivačem.

Ova prisutnost dodatnog pokazivača olakšava umetanje, brisanje operacija na dvostruko povezanom popisu, ali istodobno zahtijeva dodatnu memoriju za spremanje tih dodatnih pokazivača.

Kao što je već spomenuto, dvostruko povezani popis ima razne primjene u scenarijima u stvarnom vremenu poput predmemorije preglednika, MRU-a itd. Također možemo predstaviti druge strukture podataka poput drveća, hash tablica itd. Pomoću dvostruko povezanog popisa.

U sljedećem uputstvu saznat ćemo više o kružno povezanom popisu.

=> Ovdje pročitajte popularne serije obuke za C ++.

Preporučena literatura

^