Menu

Sammenkædet liste datastruktur i C ++ med illustration

  • Vigtigste
  • Andet
  • Sammenkædet liste datastruktur i C ++ med illustration

linked list data structure c with illustration

Prøv Vores Instrument Til At Fjerne Problemer

En detaljeret undersøgelse af sammenkædet liste i C ++.

En linket liste er en lineær dynamisk datastruktur til lagring af dataelementer. Vi har allerede set arrays i vores tidligere emner om grundlæggende C ++. Vi ved også, at arrays er en lineær datastruktur, der lagrer dataelementer sammenhængende.

I modsætning til arrays gemmer den linkede liste ikke dataelementer sammenhængende hukommelsesplaceringer.

En sammenkædet liste består af emner kaldet “Noder”, som indeholder to dele. Den første del gemmer de faktiske data, og den anden del har en markør, der peger på den næste node. Denne struktur kaldes normalt “Enkelt forbundet liste”.

=> Tjek de bedste C ++ træningsvejledninger her.

LINKET LISTE

Hvad du lærer:

Sammenkædet liste i C ++

Vi tager et kig på den enkeltstående liste i detaljer i denne vejledning.

Følgende diagram viser strukturen på en enkelt linket liste.

struktur af en enkelt forbundet liste

Som vist ovenfor kaldes den første node på den linkede liste 'hoved', mens den sidste node kaldes 'Tail'. Som vi ser, vil den sidste node på den linkede liste have sin næste markør som nul, da den ikke vil have nogen hukommelsesadresse peget på.

Da hver knude har en markør til den næste knude, behøver dataelementer på den sammenkædede liste ikke at blive lagret sammenhængende. Knudepunkterne kan spredes i hukommelsen. Vi kan få adgang til noderne når som helst, da hver node vil have en adresse til den næste node.

Vi kan tilføje dataelementer til den sammenkædede liste samt slette emner fra listen let. Det er således muligt at vokse eller formindske den sammenkædede liste dynamisk. Der er ingen øvre grænse for, hvor mange dataelementer der kan være der på den linkede liste. Så længe hukommelse er tilgængelig, kan vi tilføje så mange dataelementer til den linkede liste.

Bortset fra let indsættelse og sletning spilder den sammenkædede liste heller ikke hukommelsesplads, da vi ikke på forhånd behøver at specificere, hvor mange emner vi har brug for på den sammenkædede liste. Den eneste plads, der er taget af den sammenkædede liste, er til lagring af markøren til den næste node, der tilføjer lidt overhead.

Dernæst vil vi diskutere de forskellige operationer, der kan udføres på en sammenkædet liste.

Operationer

Ligesom de andre datastrukturer kan vi også udføre forskellige operationer for den linkede liste. Men i modsætning til arrays, hvor vi kan få adgang til elementet ved hjælp af abonnement direkte, selvom det er et sted imellem, kan vi ikke gøre den samme tilfældige adgang med en linket liste.

For at få adgang til et hvilket som helst knudepunkt er vi nødt til at krydse den sammenkædede liste fra starten, og først derefter kan vi få adgang til den ønskede node. Derfor viser det sig dyrt at få adgang til dataene tilfældigt fra den linkede liste.

Vi kan udføre forskellige operationer på en sammenkædet liste som angivet nedenfor:

hvilket program åbner en json-fil

# 1) Indsættelse

Indsættelse af linket liste tilføjer et element til den linkede liste. Selvom det måske lyder simpelt i betragtning af strukturen på den sammenkædede liste, ved vi, at når et dataelement føjes til den sammenkædede liste, er vi nødt til at ændre de næste markører i de forrige og næste noder for det nye element, som vi har indsat.

Den anden ting, vi skal overveje, er det sted, hvor det nye dataelement skal tilføjes.

Der er tre positioner på den sammenkædede liste, hvor et dataelement kan tilføjes.

# 1) I begyndelsen af ​​den linkede liste

En sammenkædet liste vises nedenfor 2-> 4-> 6-> 8-> 10. Hvis vi vil tilføje en ny node 1, som den første node på listen, vil hovedet, der peger på node 2, nu pege på 1, og den næste markør på node 1 vil have en hukommelsesadresse til node 2 som vist i nedenstående figur.

Indsættelse i begyndelsen

Den nye sammenkædede liste bliver således 1-> 2-> 4-> 6-> 8-> 10.

# 2) Efter den givne node

Her gives en knude, og vi skal tilføje en ny knude efter den givne knude. I nedenstående link a-> b-> c-> d -> e, hvis vi vil tilføje en node f efter node c, vil den linkede liste se således ud:

Indsættelse efter en given node

Således i ovenstående diagram kontrollerer vi, om den givne node er til stede. Hvis den er til stede, opretter vi en ny node f. Derefter peger vi den næste markør på node c for at pege på den nye node f. Den næste markør af noden f peger nu på node d.

# 3) I slutningen af ​​den sammenkædede liste

I det tredje tilfælde tilføjer vi en ny node i slutningen af ​​den linkede liste. Overvej, at vi har den samme sammenkædede liste a-> b-> c-> d-> e, og vi skal tilføje en node f til slutningen af ​​listen. Den linkede liste ser ud som vist nedenfor efter tilføjelse af noden.

Indsættelse i slutningen af ​​den linkede liste

Således opretter vi en ny node f. Derefter peges halemarkøren, der peger på nul, til f, og den næste markør i knudepunkt f peger på nul. Vi har implementeret alle tre typer indsætningsfunktioner i nedenstående C ++ - program.

I C ++ kan vi erklære en sammenkædet liste som en struktur eller som en klasse. Erklæring om sammenkædet liste som en struktur er en traditionel C-stil erklæring. En sammenkædet liste som klasse bruges i moderne C ++, for det meste ved brug af standard skabelonbibliotek.

I det følgende program har vi brugt struktur til at erklære og oprette en linket liste. Det vil have data og pege på det næste element som dets medlemmer.

#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout

Produktion:

Endelig linket liste:

30–> 20–> 50–> 10–> 40–> null

Dernæst implementerer vi den sammenkædede listeindsats i Java. På Java-sprog implementeres den linkede liste som en klasse. Programmet nedenfor har samme logik som C ++ - programmet, den eneste forskel er, at vi bruger en klasse til den linkede liste.

class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println(' Final linked list: '); lList. displayList (); } }

Produktion:

Endelig linket liste:

bedste pop op-blokker til Google Chrome

10–> 20–> 30–> 40–> 50–> null

I både ovenstående program, C ++ såvel som Java, har vi separate funktioner til at tilføje en node foran listen, slutningen af ​​listen og mellem listerne i en node. I sidste ende udskriver vi indholdet af listen oprettet ved hjælp af alle de tre metoder.

# 2) Sletning

Ligesom indsættelse involverer sletning af en node fra en linket liste også forskellige positioner, hvorfra noden kan slettes. Vi kan slette den første node, sidste node eller en tilfældig kth-node fra den linkede liste. Efter sletning er vi nødt til at justere den næste markør og de andre markører på den sammenkædede liste korrekt for at holde den sammenkædede liste intakt.

I den følgende C ++ implementering har vi givet to metoder til sletning, dvs. sletning af den første node i listen og sletning af den sidste node i listen. Vi opretter først en liste ved at tilføje noder til hovedet. Derefter viser vi indholdet af listen efter indsættelse og hver sletning.

#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created '

Produktion:

dot net interview spørgsmål og svar til erfarne

Tilknyttet liste oprettet

10–> 8–> 6–> 4–> 2–
> NULL

Tilknyttet liste efter sletning af hovednode

8–> 6–> 4–> 2–
> NULL

Tilknyttet liste efter sletning af sidste node

8–> 6–> 4–> NULL

Dernæst er Java-implementeringen til sletning af noder fra den linkede liste. Implementeringslogikken er den samme som i C ++ - programmet. Den eneste forskel er, at den sammenkædede liste erklæres som en klasse.

class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } }

Produktion:

Tilknyttet liste oprettet:

9–> 7–> 5–> 3–> 1–
> null

Tilknyttet liste efter sletning af hovednode:

7–> 5–> 3–> 1–
> null

Tilknyttet liste efter sletning af sidste node:

7–> 5–> 3–> null

Tæl antallet af noder

Funktionen til at tælle antallet af noder kan udføres, mens du krydser den linkede liste. Vi har allerede set i implementeringen ovenfor, at når vi har brug for at indsætte / slette en node eller vise indholdet af den linkede liste, er vi nødt til at krydse den linkede liste fra start.

Hvis du holder en tæller og forøger den, når vi krydser hver node, får vi antallet af noder, der er til stede på den linkede liste. Vi overlader dette program til læserne at implementere.

Arrays og sammenkædede lister

Efter at have set operationerne og implementeringen af ​​den sammenkædede liste, lad os sammenligne, hvordan arrays og den sammenkædede liste er fair i sammenligning med hinanden.

ArraysTilknyttede lister
Arrays har fast størrelseTilknyttet listestørrelse er dynamisk
Indsættelse af nyt element er dyrtIndsættelse / sletning er lettere
Tilfældig adgang er tilladtTilfældig adgang ikke mulig
Elementer er sammenhængendeElementer har ikke sammenhængende placering
Der kræves ikke ekstra plads til den næste markørEkstra hukommelsesplads kræves til næste markør

Ansøgninger

Da arrays og sammenkædede lister begge bruges til at gemme varer og er lineære datastrukturer, kan begge disse strukturer bruges på lignende måder til de fleste applikationer.

Nogle af ansøgningerne om sammenkædede lister er som følger:

  • En linket liste kan bruges til at implementere stakke og køer.
  • En sammenkædet liste kan også bruges til at implementere grafer, når vi skal repræsentere grafer som nærhedslister.
  • Et matematisk polynom kan gemmes som en sammenkædet liste.
  • I tilfælde af hashing-teknik implementeres skovle, der bruges i hashing ved hjælp af de sammenkædede lister.
  • Når et program kræver dynamisk allokering af hukommelse, kan vi bruge en sammenkædet liste, da sammenkædede lister fungerer mere effektivt i dette tilfælde.

Konklusion

Tilknyttede lister er datastrukturer, der bruges til at gemme dataelementer på en lineær måde, men ikke sammenhængende placeringer. En sammenkædet liste er en samling af noder, der indeholder en datadel og en næste markør, der indeholder hukommelsesadressen på det næste element på listen.

Det sidste element på listen har sin næste markør indstillet til NULL, hvilket indikerer slutningen af ​​listen. Det første element på listen kaldes hovedet. Den sammenkædede liste understøtter forskellige operationer som indsættelse, sletning, gennemkørsel osv. I tilfælde af dynamisk hukommelsesallokering foretrækkes sammenkædede lister frem for arrays.

Tilknyttede lister er dyre for deres gennemkørsel, da vi ikke tilfældigt kan få adgang til elementerne som arrays. Imidlertid er indsættelses-sletningsoperationer billigere sammenlignet med arrays.

Vi har lært alt om lineære sammenkædede lister i denne vejledning. Tilknyttede lister kan også være cirkulære eller dobbelt. Vi vil se nærmere på disse lister i vores kommende tutorials.

=> Tjek her for komplet C ++ træningsserie.

Anbefalet læsning

^