EN koblet liste er en slags lineær dynamisk datastruktur som vi bruker til å lagre dataelementer. Matriser er også en type lineær datastruktur der dataelementene er lagret i kontinuerlige minneblokker.
I motsetning til matriser, trenger ikke den koblede listen å lagre dataelementer i sammenhengende minneområder eller -blokker.
EN koblet liste er sammensatt av elementer kjent som 'Noder' som er delt inn i to deler. Den første komponenten er delen hvor vi lagrer de faktiske dataene, og den andre er en del hvor vi lagrer pekeren til neste node. Denne typen struktur er kjent som en ' enkeltlenket liste .'
Koblet liste i C++
Denne opplæringen vil gå i dybden gjennom den enkeltlenkede listen.
Strukturen til en enkelt lenket liste er illustrert i diagrammet nedenfor
- Som vi har sett i delen ovenfor, er den første noden i den koblede listen kjent som 'hodet', mens den siste noden kalles 'halen'. Det er fordi ingen minneadresse er spesifisert i den siste noden, den siste noden på den koblede listen vil ha en null neste peker.
- Fordi hver node inkluderer en peker til neste node, trenger ikke dataelementer i den koblede listen å beholdes på sammenhengende steder. Nodene kan være spredt i minnet. Fordi hver node har adressen til den etter seg, kan vi få tilgang til nodene når vi vil.
- Vi kan raskt legge til og fjerne dataelementer fra den tilkoblede listen. Som et resultat kan den koblede listen øke eller trekke seg sammen dynamisk. Den koblede listen har ingen maksimal mengde dataelementer den kan inneholde. Som et resultat kan vi legge til så mange dataelementer vi vil til den koblede listen så lenge det er RAM tilgjengelig.
- Fordi vi ikke trenger å spesifisere hvor mange elementer vi trenger i den koblede listen på forhånd, sparer den koblede listen minneplass i tillegg til at den er enkel å sette inn og slette. Den eneste plassen som brukes av en koblet liste er å lagre pekeren til neste node, noe som gir en viss kostnad.
Deretter vil vi gå over de ulike operasjonene som kan utføres på en koblet liste.
kartskrift
1) Innsetting
Den koblede listen utvides ved å legge til den. Selv om det virker enkelt, gitt strukturen til den koblede listen, vet vi at hver gang et dataelement legges til, må vi endre de neste pekerne til forrige og neste noder til det nye elementet som vi har lagt til.
Hvor det nye dataelementet skal settes inn er det andre aspektet å tenke på.
Det er tre steder hvor et dataelement kan legges til den koblede listen.
nginx-variabler
en. Begynner med den koblede listen
Nedenfor er en tilkoblet liste over tallene 2->4->6->8->10. Hodet som peker til node 2 vil nå peke til node 1, og neste peker på node 1 vil ha minneadressen til node 2, som vist i illustrasjonen nedenfor, hvis vi legger til en ny node 1 som den første noden i listen .
Som et resultat er den nye koblede listen 1->2->4->6->8->10.
b. Etter den gitte noden
I dette tilfellet får vi en node og må legge til en ny node bak den. Den koblede listen vil se ut som følger hvis node f legges til den koblede listen a->b->c->d->e etter node c:
Vi sjekker derfor om den angitte noden er til stede i diagrammet ovenfor. Hvis den er tilstede, opprettes en ny node f. Etter det peker vi node cs neste peker mot den splitter nye noden f. Node fs neste peker peker nå til node d.
c. Den lenkede listens siste element
I det tredje tilfellet legges en ny node til på slutten av den koblede listen. Ta hensyn til den lenkede listen nedenfor: a->b->c->d->e, med tillegg av node f på slutten. Etter å ha lagt til noden, vil den koblede listen vises slik.
maven repository
Som et resultat konstruerer vi en ny node f. Halepekeren som leder til null peker deretter på f, og node fs neste peker peker på null. I programmeringsspråket nedenfor har vi generert alle tre typer innsettingsfunksjoner.
En koblet liste kan deklareres som en struktur eller som en klasse i C++. En koblet liste erklært som en struktur er en klassisk C-stil setning. En koblet liste brukes som en klasse i moderne C++, hovedsakelig ved bruk av standard malbibliotek.
Struktur ble brukt i følgende applikasjon for å deklarere og generere en koblet liste. Medlemmene vil være data og en peker til følgende element.
C++-program:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) Sletting
I likhet med innsetting krever sletting av en node fra en koblet liste mange punkter som noden kan elimineres fra. Vi kan fjerne den koblede listens første, siste eller kth node tilfeldig. Vi må oppdatere neste peker og alle andre lenkelistepekere på riktig måte for å opprettholde den lenkede listen etter sletting.
I følgende C++-implementering har vi to slettingsmetoder: sletting av listens første node og sletting av listens siste node. Vi begynner med å legge til noder til toppen av listen. Listens innhold vises deretter etter hver tillegg og sletting.
C++-program:
full addererkrets
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> Nodetelling
Mens du går gjennom den koblede listen, kan prosessen med å telle antall noder utføres. I den foregående tilnærmingen så vi at hvis vi trengte å sette inn/slette en node eller vise innholdet i den koblede listen, måtte vi krysse den koblede listen fra begynnelsen.
Å sette en teller og øke i tillegg til at vi krysser hver node vil gi oss antall noder i den koblede listen.
Forskjeller mellom Array og Linked List:
| Array | Koblet liste |
|---|---|
| Matriser har en definert størrelse. | Størrelsen på den koblede listen er variabel. |
| Det er vanskelig å sette inn et nytt element. | Innsetting og sletting er enklere. |
| Tilgang er tillatt tilfeldig. | Ingen tilfeldig tilgang er mulig. |
| Elementer er relativt tett eller sammenhengende. | Elementene er ikke sammenhengende. |
| Ingen ekstra plass er nødvendig for følgende peker. | Følgende peker krever ekstra minne. |
Funksjonalitet
Siden koblede lister og matriser begge er lineære datastrukturer som inneholder objekter, kan de brukes på lignende måter for de fleste applikasjoner.
juster css-bilde
Følgende er noen eksempler på koblede listeapplikasjoner:
- Stabler og køer kan implementeres ved hjelp av koblede lister.
- Når vi trenger å uttrykke grafer som tilstøtende lister, kan vi bruke en koblet liste for å implementere dem.
- Vi kan også bruke en lenket liste for å inneholde et matematisk polynom.
- I tilfelle av hashing, brukes koblede lister for å implementere bøttene.
- Når et program krever dynamisk minneallokering, kan vi bruke en koblet liste fordi koblede lister er mer effektive i dette tilfellet.
Konklusjon
Koblede lister er datastrukturer som brukes til å holde dataelementer i en lineær, men ikke-sammenhengende form. En koblet liste består av noder med to komponenter hver. Den første komponenten består av data, mens den andre halvdelen har en peker som lagrer minneadressen til følgende medlem av listen.
Som et tegn på at den koblede listen er avsluttet, har det siste elementet i listen sin neste peker satt til NULL. Hodet er det første elementet på listen. Den koblede listen tillater en rekke handlinger som innsetting, sletting, kryssing og så videre. Koblede lister favoriseres fremfor matriser for dynamisk minneallokering.
Koblede lister er vanskelige å skrive ut eller gå gjennom fordi vi ikke får tilgang til elementene tilfeldig som matriser. Sammenlignet med matriser er prosedyrer for innsetting og sletting rimeligere.
I denne opplæringen lærte vi alt det er å vite om lineært koblede lister. Linkede lister kan også være dobbeltlenket eller sirkulært. I våre kommende opplæringsprogrammer vil vi gå gjennom disse listene i detalj.