Meny

Dobbeltkoblet listedatastruktur i C ++ med illustrasjon

  • Hoved
  • Annen
  • Dobbeltkoblet listedatastruktur i C ++ med illustrasjon

doubly linked list data structure c with illustration

Prøv Instrumentet Vårt For Å Eliminere Problemer

En grundig opplæring om dobbeltkoblet liste.

En dobbeltkoblet liste er en variant av den enkeltkoblede listen. Vi er klar over at den enkeltkoblede listen er en samling noder med hver node som har en datadel og en peker som peker mot neste node.

En dobbeltkoblet liste er også en samling noder. Hver node her består av en datadel og to pekere. En peker peker på forrige node mens den andre peker på neste node.

=> Sjekk In-Depth C ++ Training Tutorials Here.

DOBBELKOBLET LISTE

Hva du vil lære:

Dobbeltkoblet i C ++

Som i den enkeltkoblede listen, har den dobbeltkoblede listen også et hode og en hale. Den forrige pekeren på hodet er satt til NULL, da dette er den første noden. Den neste pekeren til halenoden er satt til NULL, da dette er den siste noden.

En grunnleggende utforming av den dobbeltkoblede listen er vist i diagrammet nedenfor.

En grunnleggende utforming av den dobbeltkoblede listen

I figuren ovenfor ser vi at hver node har to pekere, den ene peker mot den forrige noden og den andre peker mot den neste noden. Bare den første noden (hodet) har den forrige noden satt til null, og den siste noden (halen) har den neste pekeren satt til null.

Siden den dobbeltkoblede listen inneholder to pekere, dvs. forrige og neste, kan vi krysse den i retningene fremover og bakover. Dette er den viktigste fordelen med dobbeltkoblet liste over den enkeltkoblede listen.

det du ser er det du får webbygger

Erklæring

I C-stilerklæring er en node på den dobbeltkoblede listen representert som følger:

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

Bortsett fra ovennevnte erklæring, kan vi også representere en node i den dobbeltkoblede listen som en klasse i C ++. En dobbeltkoblet liste er representert som en klasse når vi bruker STL i C ++. Vi kan implementere en dobbeltkoblet liste ved hjelp av en klasse i Java også.

Grunnleggende operasjoner

Følgende er noen av operasjonene vi kan utføre på en dobbeltkoblet liste.

Innsetting

Innsettingsoperasjon av den dobbeltkoblede listen setter inn en ny node i den koblede listen. Avhengig av posisjonen der den nye noden skal settes inn, kan vi ha følgende innsettingsoperasjoner.

  • Innsetting foran - Setter inn en ny node som den første noden.
  • Innføring på slutten - Setter inn en ny node på slutten som den siste noden.
  • Innsetting før en node - Gitt en node, setter inn en ny node før denne noden.
  • Innsetting etter en node - Gitt en node, setter inn en ny node etter denne noden.

Sletting

Slettingsoperasjon sletter en node fra en gitt posisjon i den dobbeltkoblede listen.

  • Sletting av den første noden - Sletter den første noden i listen
  • Sletting av den siste noden - Sletter den siste noden i listen.
  • Sletting av en node gitt dataene - Gitt dataene, samsvarer operasjonen med dataene med nodedataene i den koblede listen og sletter den noden.

Gjennomgang

Traversal er en teknikk for å besøke hver node i den koblede listen. I en dobbeltkoblet liste har vi to typer gjennomkjøringer da vi har to pekere med forskjellige retninger i den dobbeltkoblede listen.

  • Fremoverkjøring - Gjennomgang gjøres ved hjelp av neste peker som er i retning fremover.
  • Bakoverkjøring - Gjennomgang gjøres ved hjelp av forrige peker som er bakoverretningen.

Omvendt

Denne operasjonen reverserer nodene i den dobbeltkoblede listen, slik at den første noden blir den siste noden mens den siste noden blir den første noden.

Søk

Søkeoperasjon i den dobbeltkoblede listen brukes til å søke etter en bestemt node i den koblede listen. For dette formålet må vi krysse listen til samsvarende data er funnet.

Innsetting

Sett inn en node foran

Sett inn en node foran

Innsetting av en ny node foran på listen er vist ovenfor. Som sett er den forrige nye noden N satt til null. Hode peker mot den nye noden. Neste peker på N peker nå mot N1 og forrige av N1 som tidligere pekte mot Null peker nå mot N.

Sett inn node på slutten

Sett inn node på slutten

Å sette inn node på slutten av den dobbeltkoblede listen oppnås ved å peke neste peker på ny node N til null. Den forrige pekeren til N er pekt mot N5. ‘Neste’ pekeren til N5 peker mot N.

Sett inn node før / etter gitt node

Sett inn node før etter gitt node

Som vist i diagrammet ovenfor, når vi må legge til en node før eller etter en bestemt node, endrer vi forrige og neste pekere til før- og etter-nodene slik at de på riktig måte peker på den nye noden. Også de nye nodepekerne er riktig pekt på eksisterende noder.

Følgende C ++ - program viser alle metodene ovenfor for å sette inn noder i den dobbeltkoblede listen.

#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

Produksjon:

Dobbeltkoblet liste er som følger:

1020304050NUL

Ovennevnte program konstruerer en dobbeltkoblet liste ved å sette inn nodene ved å bruke tre innsettingsmetoder, dvs. sette inn noden foran, sette inn noden på slutten og sette inn noden etter den gitte noden.

Deretter demonstrerer vi den samme operasjonen som en Java-implementering.

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

Produksjon:

Dobbeltkoblet liste opprettet er som følger:

eksempel for abstrakt grensesnitt i java

1020304050ull

Sletting

En node kan slettes fra en dobbeltkoblet liste fra hvilken som helst posisjon som fra fronten, enden eller en hvilken som helst annen gitt posisjon eller gitt data.

Når du sletter en node fra den dobbeltkoblede listen, plasserer vi først pekeren som peker mot den aktuelle noden, slik at forrige og etternode ikke har noen forbindelse til noden som skal slettes. Vi kan da enkelt slette noden.

Tenk på den følgende dobbeltkoblede listen med tre noder A, B, C. La oss vurdere at vi trenger å slette noden B.

dobbeltkoblet liste med tre noder A, B, C

Som vist i ovenstående serie av diagrammet, har vi demonstrert sletting av node B fra den gitte koblede listen. Driftssekvensen forblir den samme selv om noden er første eller siste. Den eneste forsiktigheten som bør tas er at hvis den første noden blir slettet, vil den andre nodenes forrige peker bli satt til null.

På samme måte, når den siste noden blir slettet, vil neste peker til den forrige noden settes til null. Hvis noder mellom slettes, vil sekvensen være som ovenfor.

Vi forlater programmet for å slette en node fra en dobbeltkoblet liste. Merk at implementeringen vil være i tråd med implementeringsimplementeringen.

Omvendt dobbeltkoblet liste

Å reversere en dobbeltkoblet liste er en viktig operasjon. I dette bytter vi bare de forrige og neste pekerne på alle nodene og bytter også hodet og halen.

Nedenfor er en dobbelt koblet liste:

Omvendt dobbeltkoblet liste

Etter C ++ implementering viser Reverse Doubly Linked List.

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

Produksjon:

Opprinnelig dobbeltkoblet liste:

1 2 3 4 5

Omvendt dobbeltkoblet liste:

5 4 3 2 1

Her bytter vi venstre og høyre pekere og beveger dem mot hverandre til de møter eller krysser hverandre. Deretter byttes den første og siste noden.

Det neste programmet er Java-implementeringen for å reversere en dobbeltkoblet liste. I dette programmet bruker vi også bytte av venstre og høyre noder som vi gjorde i vårt forrige program.

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

Produksjon:

Opprinnelig dobbeltkoblet liste:

1 2 3 4 5

Omvendt dobbeltkoblet liste:

5 4 3 2 1

Fordeler / ulemper i forhold til enkeltkoblet liste

La oss diskutere noen av fordelene og ulempene med dobbeltkoblet liste over den enkeltkoblede listen.

Fordeler:

  • Den dobbeltkoblede listen kan krysses både fremover og bakover, i motsetning til enkeltkoblet liste som bare kan krysses fremover.
  • Slettoperasjon i en dobbeltkoblet liste er mer effektiv sammenlignet med enkeltliste når en gitt node er gitt. I en enkelt koblet liste, da vi trenger en tidligere node for å slette den gitte noden, må vi noen ganger krysse listen for å finne den forrige noden. Dette treffer forestillingen.
  • Innsettingsoperasjonen kan gjøres enkelt i en dobbeltkoblet liste sammenlignet med den enkeltkoblede listen.

Ulemper:

  • Siden den dobbeltkoblede listen inneholder en ekstra peker, dvs. forrige, er minneplassen som er tatt opp av den dobbeltkoblede listen større sammenlignet med den enkeltkoblede listen.
  • Siden to pekere er tilstede, dvs. forrige og neste, må alle operasjonene som utføres på den dobbeltkoblede listen, ta seg av disse pekerne og vedlikeholde dem, noe som resulterer i en ytelsesflaskehals.

Anvendelser av dobbeltkoblet liste

En dobbeltkoblet liste kan brukes i ulike virkelige scenarier og applikasjoner som diskutert nedenfor.

  • Et kortstokk i et spill er et klassisk eksempel på en dobbeltkoblet liste. Gitt at hvert kort i en kortstokk har det forrige kortet og det neste kortet ordnet i rekkefølge, kan dette kortstokken enkelt vises med en dobbeltkoblet liste.
  • Nettleserhistorikk / hurtigbuffer - Nettleserbufferen har en samling URL-er og kan navigeres ved hjelp av fremover- og bakknappene, er et annet godt eksempel som kan vises som en dobbeltkoblet liste.
  • Senest brukte (MRU) kan også vises som en dobbeltkoblet liste.
  • Andre datastrukturer som Stacks, hash-tabell, det binære treet kan også konstrueres eller programmeres ved hjelp av en dobbeltkoblet liste.

Konklusjon

En dobbeltkoblet liste er en variant av den enkeltkoblede listen. Den skiller seg fra den enkeltkoblede listen ved at der hver node inneholder en ekstra peker til forrige node sammen med neste peker.

Denne tilstedeværelsen av en ekstra peker muliggjør innsetting, sletting av operasjoner på den dobbeltkoblede listen, men krever samtidig ekstra minne for å lagre disse ekstra pekerne.

Som allerede diskutert, har den dobbeltkoblede listen forskjellige bruksområder i sanntidsscenarier som nettleserbuffer, MRUer osv. Vi kan også representere andre datastrukturer som trær, hasjtabeller, etc. ved hjelp av en dobbeltkoblet liste.

I vår neste opplæring vil vi lære mer om Circular Linked List.

=> Les gjennom den populære C ++ treningsserien her.

Anbefalt lesing

^