Menu

Dobbelt sammenkædet liste Datastruktur i C ++ med illustration

  • Vigtigste
  • Andet
  • Dobbelt sammenkædet liste Datastruktur i C ++ med illustration

doubly linked list data structure c with illustration

Prøv Vores Instrument Til At Fjerne Problemer

En dybtgående vejledning om dobbeltkoblet liste.

En dobbeltkoblet liste er en variation af den enkeltkædede liste. Vi er opmærksomme på, at den enkeltlinkede liste er en samling af noder, hvor hver node har en datadel og en markør, der peger på den næste node.

En dobbeltkoblet liste er også en samling noder. Hver knude her består af en datadel og to markører. Én markør peger på den forrige node, mens den anden markør peger på den næste node.

=> Tjek dybdegående C ++ træningsvejledninger her.

DOBBELT LINKET LISTE

Hvad du lærer:

Dobbelt forbundet i C ++

Som på den enkeltkædede liste har den dobbeltkædede liste også et hoved og en hale. Den forrige markør på hovedet er indstillet til NULL, da dette er den første node. Den næste markør på halenoden er indstillet til NULL, da dette er den sidste node.

Et grundlæggende layout på den dobbeltkoblede liste er vist i nedenstående diagram.

Et grundlæggende layout på den dobbeltkoblede liste

I ovenstående figur ser vi, at hver node har to markører, den ene peger på den forrige node og den anden peger på den næste node. Kun den første node (hoved) har sin tidligere node sat til null, og den sidste node (hale) har sin næste markør sat til null.

Da den dobbeltkoblede liste indeholder to markører, dvs. forrige og næste, kan vi krydse den i retningerne fremad og bagud. Dette er den største fordel ved dobbeltkoblet liste i forhold til den enkeltkædede liste.

hvilket af følgende er ikke en acceptabel måde at teste et responsivt design på?

Erklæring

I C-stilerklæring er en node på den dobbeltkoblede liste repræsenteret som følger:

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

Bortset fra ovenstående erklæring kan vi også repræsentere en node på den dobbeltkoblede liste som en klasse i C ++. En dobbeltkoblet liste er repræsenteret som en klasse, når vi bruger STL i C ++. Vi kan også implementere en dobbeltkoblet liste ved hjælp af en klasse i Java.

Grundlæggende funktioner

Følgende er nogle af de operationer, som vi kan udføre på en dobbeltkoblet liste.

Indskud

Indsættelse af den dobbeltkoblede liste indsætter en ny knude i den sammenkædede liste. Afhængigt af den position, hvor den nye node skal indsættes, kan vi have følgende indsætningsoperationer.

  • Indføring foran - Indsætter en ny node som den første node.
  • Indsættelse i slutningen - Indsætter en ny node i slutningen som den sidste node.
  • Indsættelse før en node - Givet en node, indsætter en ny node før denne node.
  • Indsættelse efter en node - Givet en node, indsætter en ny node efter denne node.

Sletning

Sletningshandling sletter en node fra en given position på den dobbeltkoblede liste.

  • Sletning af den første node - Sletter den første node på listen
  • Sletning af den sidste node - Sletter den sidste node på listen.
  • Sletning af en node givet dataene - Givet dataene matcher operationen dataene med nodedataene i den linkede liste og sletter den node.

Traversal

Traversal er en teknik til at besøge hver node på den linkede liste. På en dobbeltkoblet liste har vi to typer gennemkørsler, da vi har to markører med forskellige retninger på den dobbeltkædede liste.

  • Fremadkørsel - Traversal udføres ved hjælp af den næste markør, der er i fremadgående retning.
  • Bagudkørsel - Traversal udføres ved hjælp af den forrige markør, som er bagudretningen.

Baglæns

Denne handling vender noder i den dobbeltkoblede liste, så den første node bliver den sidste node, mens den sidste node bliver den første node.

Søg

Søgning på den dobbeltkoblede liste bruges til at søge efter en bestemt knude på den sammenkædede liste. Til dette formål er vi nødt til at krydse listen, indtil der findes matchende data.

Indskud

Indsæt en knude foran

Indsæt en knude foran

Indsættelse af en ny node foran på listen er vist ovenfor. Som set er den tidligere nye node N indstillet til null. Hoved peger på den nye knude. Den næste markør af N peger nu på N1 og forrige af N1, der tidligere pegede på Null, peger nu på N.

Indsæt node i slutningen

Indsæt node i slutningen

Indsættelse af knudepunkt i slutningen af ​​den dobbeltkoblede liste opnås ved at pege den næste markør for den nye knude N til nul. Den forrige markør af N er peget på N5. Den 'næste' markør på N5 peges på N.

Indsæt node før / efter given node

Indsæt node før efter given node

Som vist i ovenstående diagram, når vi skal tilføje en knude før eller efter en bestemt knude, ændrer vi de forrige og næste markører i de før og efter knudepunkter for på passende vis at pege på den nye knude. De nye knudepunkter er også passende peget på de eksisterende noder.

Følgende C ++ - program demonstrerer alle de ovennævnte metoder til at indsætte noder i den dobbeltkoblede liste.

#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

Produktion:

Dobbeltkoblet liste er som følger:

1020304050NUL

Ovenstående program konstruerer en dobbeltkoblet liste ved at indsætte noderne ved hjælp af tre indsættelsesmetoder, dvs. indsætte noden foran, indsætte noden i slutningen og indsætte noden efter den givne node.

Dernæst demonstrerer vi den samme operation 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); } }

Produktion:

Dobbeltkoblet liste oprettet er som følger:

hvad er den bedste vr app

1020304050ull

Sletning

En knude kan slettes fra en dobbeltkoblet liste fra enhver position som forfra, slutningen eller enhver anden given position eller givne data.

Når du sletter en node fra den dobbeltkoblede liste, placerer vi først markøren, der peger på den pågældende node, så den foregående og efter-noden ikke har nogen forbindelse til den node, der skal slettes. Vi kan derefter let slette noden.

Overvej følgende dobbeltkoblede liste med tre noder A, B, C. Lad os overveje, at vi skal slette noden B.

dobbeltkoblet liste med tre knudepunkter A, B, C

Som vist i ovenstående serie af diagrammet har vi demonstreret sletningen af ​​knude B fra den givne sammenkædede liste. Driftssekvensen forbliver den samme, selvom noden er første eller sidste. Den eneste forsigtighed, der skal tages, er, at hvis den første node slettes, vil den anden nodes forrige markør blive indstillet til null.

Tilsvarende, når den sidste node slettes, vil den næste markør i den forrige node blive indstillet til null. Hvis der mellem noder slettes, vil sekvensen være som ovenfor.

Vi forlader programmet for at slette en node fra en dobbeltkoblet liste. Bemærk, at implementeringen vil være på linje med implementeringen af ​​indsættelsen.

Omvendt dobbeltkoblet liste

At vende om en dobbeltkoblet liste er en vigtig handling. I dette bytter vi simpelthen de forrige og næste markører på alle knudepunkter og bytter også hoved- og halepegerne.

Nedenfor er en dobbeltkoblet liste:

Omvendt dobbeltkoblet liste

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

Produktion:

Oprindeligt dobbeltkoblet liste:

1 2 3 4 5

Omvendt dobbeltkoblet liste:

5 4 3 2 1

Her bytter vi venstre og højre markør og bevæger dem mod hinanden, indtil de mødes eller krydser hinanden. Derefter byttes den første og sidste knudepunkt.

Det næste program er Java-implementeringen til at vende en dobbeltkoblet liste. I dette program bruger vi også bytte af venstre og højre noder, som vi gjorde i vores tidligere 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); } }

Produktion:

Oprindeligt dobbeltkoblet liste:

1 2 3 4 5

Omvendt dobbeltkoblet liste:

5 4 3 2 1

Fordele / ulemper i forhold til enkeltkædet liste

Lad os diskutere nogle af fordele og ulemper ved dobbeltkoblet liste i forhold til den enkeltkædede liste.

Fordele:

  • Den dobbeltkoblede liste kan krydses både fremad og tilbage, i modsætning til en enkelt sammenkædet liste, som kun kan krydses i fremadgående retning.
  • Sletning på en dobbeltkoblet liste er mere effektiv sammenlignet med en enkelt liste, når en given node er givet. Da vi har brug for en tidligere node for at slette den givne node, er vi undertiden nødt til at krydse listen for at finde den tidligere node. Dette rammer forestillingen.
  • Indsættelse kan let udføres i en dobbeltkoblet liste sammenlignet med den enkeltkædede liste.

Ulemper:

  • Da den dobbeltkoblede liste indeholder en ekstra markør, dvs. tidligere, er hukommelsespladsen, der optages af den dobbeltkædede liste, større sammenlignet med den enkeltkædede liste.
  • Da to markører er til stede, dvs. forrige og næste, skal alle operationer, der udføres på den dobbeltkoblede liste, tage sig af disse markører og vedligeholde dem, hvilket resulterer i en præstationsflaskehals.

Anvendelser af dobbeltkoblet liste

En dobbeltkoblet liste kan anvendes i forskellige virkelige scenarier og applikationer som beskrevet nedenfor.

  • Et kortkort i et spil er et klassisk eksempel på en dobbeltkoblet liste. I betragtning af at hvert kort i et kort har det forrige kort og det næste kort arrangeret i rækkefølge, kan dette kortstik let repræsenteres ved hjælp af en dobbeltkoblet liste.
  • Browserhistorik / cache - Browsercachen har en samling af URL'er og kan navigeres ved hjælp af knapperne frem og tilbage er et andet godt eksempel, der kan repræsenteres som en dobbeltkoblet liste.
  • Senest anvendte (MRU) kan også repræsenteres som en dobbeltkoblet liste.
  • Andre datastrukturer som stakke, hash-tabel, det binære træ kan også konstrueres eller programmeres ved hjælp af en dobbeltkoblet liste.

Konklusion

En dobbeltkoblet liste er en variation af den enkeltkædede liste. Det adskiller sig fra listen, der er sammenkædet, ved at hvor hver node indeholder en ekstra markør til den tidligere node sammen med den næste markør.

Denne tilstedeværelse af en ekstra pointer letter indsættelse, sletning af handlinger på den dobbeltkoblede liste, men kræver samtidig ekstra hukommelse for at gemme disse ekstra pointer.

Som allerede diskuteret har den dobbeltkoblede liste forskellige anvendelser i realtidsscenarier som browser-cache, MRU'er osv. Vi kan også repræsentere andre datastrukturer som træer, hash-tabeller osv. Ved hjælp af en dobbeltkoblet liste.

I vores næste vejledning lærer vi mere om den cirkulære sammenkædede liste.

=> Læs gennem den populære C ++ træningsserie her.

Anbefalet læsning

^