linked list data structure c with illustration
En detaljert studie av koblet liste i C ++.
En koblet liste er en lineær dynamisk datastruktur for å lagre dataelementer. Vi har allerede sett matriser i våre tidligere emner om grunnleggende C ++. Vi vet også at matriser er en lineær datastruktur som lagrer dataelementer sammenhengende.
I motsetning til matriser lagrer ikke den koblede listen dataelementer i sammenhengende minneplasseringer.
En koblet liste består av elementer kalt “Noder” som inneholder to deler. Den første delen lagrer de faktiske dataene, og den andre delen har en peker som peker til neste node. Denne strukturen kalles vanligvis 'Singly linked list'.
=> Sjekk ut de beste C ++ opplæringsveiledningene her.
Hva du vil lære:
Koblet liste i C ++
Vi tar en titt på den enkeltstående lenken i detalj i denne opplæringen.
Diagrammet nedenfor viser strukturen til en enkelt koblet liste.
hva dbms kjører på en pc
Som vist ovenfor, kalles den første noden på den koblede listen 'head' mens den siste noden kalles 'Tail'. Som vi ser, vil den siste noden i den koblede listen ha sin neste peker som null, siden den ikke vil ha noen minneadresse pekt på.
Siden hver node har en peker til neste node, trenger ikke dataelementer i den koblede listen å bli lagret på sammenhengende steder. Nodene kan spres i minnet. Vi har tilgang til nodene når som helst, da hver node vil ha en adresse til neste node.
Vi kan legge til dataelementer i den koblede listen, samt slette elementer fra listen enkelt. Dermed er det mulig å vokse eller krympe den koblede listen dynamisk. Det er ingen øvre grense for hvor mange dataelementer som kan være der i den koblede listen. Så lenge minne er tilgjengelig, kan vi ha så mange dataelementer lagt til i den koblede listen.
Bortsett fra enkel innsetting og sletting, sløser ikke den koblede listen heller ikke minneplass, ettersom vi ikke trenger å spesifisere på forhånd hvor mange elementer vi trenger i den koblede listen. Den eneste plassen som er tatt av koblet liste er for å lagre pekeren til neste node som legger til litt overhead.
Deretter vil vi diskutere de forskjellige operasjonene som kan utføres på en koblet liste.
Operasjoner
Akkurat som de andre datastrukturene, kan vi også utføre forskjellige operasjoner for den koblede listen. Men i motsetning til arrays, der vi kan få tilgang til elementet ved hjelp av abonnement direkte, selv om det er et sted i mellom, kan vi ikke gjøre den samme tilfeldige tilgangen med en koblet liste.
For å få tilgang til en hvilken som helst node, må vi krysse den koblede listen fra starten, og først da kan vi få tilgang til ønsket node. Derfor viser det seg å være dyrt å få tilgang til dataene tilfeldig fra den koblede listen.
Vi kan utføre forskjellige operasjoner på en koblet liste som gitt nedenfor:
# 1) Innsetting
Innsettingsoperasjon av koblet liste legger til et element i den koblede listen. Selv om det kan høres enkelt ut, med tanke på strukturen til den koblede listen, vet vi at når et dataelement legges til i den koblede listen, må vi endre de neste pekerne i forrige og neste noder for det nye elementet vi har satt inn.
Den andre tingen vi må vurdere er stedet der den nye dataenheten skal legges til.
Det er tre posisjoner i den koblede listen der et dataelement kan legges til.
# 1) I begynnelsen av den koblede listen
En koblet liste vises nedenfor 2-> 4-> 6-> 8-> 10. Hvis vi vil legge til en ny node 1, som den første noden på listen, vil hodet som peker på node 2 nå peke på 1, og neste peker til node 1 vil ha en minneadresse til node 2 som vist nedenfor figur.
Dermed blir den nye koblede listen 1-> 2-> 4-> 6-> 8-> 10.
# 2) Etter den gitte Node
Her er en node gitt, og vi må legge til en ny node etter den gitte noden. I listen nedenfor - a -> b-> c-> d -> e, hvis vi vil legge til en node f etter node c, vil den koblede listen se slik ut:
Dermed sjekker vi i diagrammet ovenfor om den gitte noden er til stede. Hvis den er tilstede, oppretter vi en ny node f. Deretter peker vi neste peker på node c for å peke på den nye noden f. Den neste pekeren til noden f peker nå til noden d.
# 3) På slutten av den koblede listen
I det tredje tilfellet legger vi til en ny node på slutten av den koblede listen. Tenk på at vi har den samme koblede listen a-> b-> c-> d-> e, og vi må legge til en node f på slutten av listen. Den koblede listen vil se ut som vist nedenfor etter at du har lagt til noden.
hvordan lage en kopi av en array-java
Dermed oppretter vi en ny node f. Deretter peker halepekeren som peker mot null mot f, og den neste pekeren til node f peker mot null. Vi har implementert alle tre typene innsettingsfunksjoner i C ++ -programmet nedenfor.
I C ++ kan vi erklære en koblet liste som en struktur eller som en klasse. Erklæring om koblet liste som en struktur er en tradisjonell C-stil erklæring. En koblet liste som klasse brukes i moderne C ++, hovedsakelig mens du bruker standard malbibliotek.
I det følgende programmet har vi brukt struktur for å erklære og opprette en koblet liste. Den vil ha data og peke til neste element som sine 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 Produksjon:
Endelig koblet liste:
30–> 20–> 50–> 10–> 40–> null
Deretter implementerer vi den koblede listeinnsatsoperasjonen i Java. På Java-språk er den koblede listen implementert som en klasse. Programmet nedenfor er i logikk likt C ++ - programmet, den eneste forskjellen er at vi bruker en klasse for den koblede listen.
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 (); } } Produksjon:
Endelig koblet liste:
10–> 20–> 30–> 40–> 50–> null
Både i programmet ovenfor, C ++ så vel som Java, har vi separate funksjoner for å legge til en node foran listen, slutten av listen og mellom listene gitt i en node. Til slutt skriver vi ut innholdet i listen som er opprettet ved hjelp av alle de tre metodene.
# 2) Sletting
I likhet med innsetting innebærer det å slette en node fra en koblet liste også forskjellige posisjoner der noden kan slettes. Vi kan slette den første noden, den siste noden eller en tilfeldig kth-node fra den koblede listen. Etter sletting må vi justere neste peker og de andre pekerne i den koblede listen på riktig måte for å holde den koblede listen intakt.
I den følgende C ++ implementeringen har vi gitt to metoder for sletting, dvs. å slette den første noden i listen og slette den siste noden i listen. Vi oppretter først en liste ved å legge til noder i hodet. Deretter viser vi innholdet i listen etter innsetting og hver sletting.
#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 ' Produksjon:
Koblet liste opprettet
10–> 8–> 6–> 4–> 2–
> NULL
Koblet liste etter sletting av hodeknute
8–> 6–> 4–> 2–
> NULL
Koblet liste etter sletting av siste node
8–> 6–> 4–> NULL
hvordan være programmerer for nybegynnere
Deretter er Java-implementeringen for å slette noder fra den koblede listen. Implementeringslogikken er den samme som brukt i C ++ - programmet. Den eneste forskjellen er at den koblede listen blir erklært 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'); } } Produksjon:
Koblet liste opprettet:
9–> 7–> 5–> 3–> 1–
> null
Koblet liste etter sletting av hodeknute:
7–> 5–> 3–> 1–
> null
Koblet liste etter sletting av siste node:
7–> 5–> 3–> null
Telle antall noder
Operasjonen for å telle antall noder kan utføres mens du krysser den koblede listen. Vi har allerede sett i implementeringen ovenfor at når vi trenger å sette inn / slette en node eller vise innholdet i den koblede listen, må vi krysse den koblede listen fra start.
Hvis du holder en teller og øker den når vi krysser hver node, vil vi telle antall noder som er tilstede i den koblede listen. Vi legger igjen dette programmet for leserne å implementere.
Arrays And Linked Lists
Etter å ha sett operasjonene og implementeringen av den koblede listen, la oss sammenligne hvordan arrays og koblet liste rettferdig i forhold til hverandre.
Arrays Koblede lister Arrays har fast størrelse Koblet listestørrelse er dynamisk Innsetting av nytt element er dyrt Innsetting / sletting er lettere Tilfeldig tilgang er tillatt Tilfeldig tilgang ikke mulig Elementene ligger sammenhengende Elementer har ikke sammenhengende beliggenhet Ingen ekstra plass er nødvendig for neste peker Ekstra minne kreves for neste peker
applikasjoner
Ettersom matriser og koblede lister begge brukes til å lagre varer og er lineære datastrukturer, kan begge disse strukturene brukes på lignende måter for de fleste applikasjoner.
Noen av søknadene om koblede lister er som følger:
- En koblet liste kan brukes til å implementere stabler og køer.
- En koblet liste kan også brukes til å implementere grafer når vi må representere grafer som nærhetslister.
- Et matematisk polynom kan lagres som en koblet liste.
- I tilfelle hashingsteknikk blir skuffene som brukes i hashing implementert ved hjelp av de lenkede listene.
- Når et program krever dynamisk tildeling av minne, kan vi bruke en koblet liste ettersom koblede lister fungerer mer effektivt i dette tilfellet.
Konklusjon
Koblede lister er datastrukturene som brukes til å lagre dataelementer på en lineær måte, men ikke sammenhengende steder. En koblet liste er en samling noder som inneholder en datadel og en neste peker som inneholder minneadressen til det neste elementet i listen.
Det siste elementet i listen har sin neste peker satt til NULL, og indikerer dermed slutten på listen. Det første elementet i listen kalles hodet. Den koblede listen støtter forskjellige operasjoner som innsetting, sletting, traversering, etc. I tilfelle dynamisk minnetildeling foretrekkes koblede lister fremfor matriser.
Tilknyttede lister er dyre når det gjelder traversering siden vi ikke tilfeldig kan få tilgang til elementene som matriser. Imidlertid er innsettings- og slettingsoperasjoner billigere når man sammenligner matriser.
Vi har lært alt om lineære koblede lister i denne opplæringen. Koblede lister kan også være sirkulære eller dobbelt. Vi vil se nærmere på disse listene i våre kommende opplæringsprogrammer.
=> Sjekk her for komplett C ++ opplæringsserie.
Anbefalt lesing
- Sirkulær koblet liste Datastruktur i C ++ med illustrasjon
- Dobbeltkoblet liste Datastruktur i C ++ med illustrasjon
- Kødatastruktur i C ++ med illustrasjon
- Stakk datastruktur i C ++ med illustrasjon
- Prioritert kødatastruktur i C ++ med illustrasjon
- Topp 15 beste gratis dataverktøy: Den mest omfattende listen
- 15 beste ETL-verktøy i 2021 (en komplett oppdatert liste)
- Introduksjon til datastrukturer i C ++