EN linket liste er en slags lineær dynamisk datastruktur, som vi bruger til at gemme dataelementer. Arrays er også en type lineær datastruktur, hvor dataelementerne er lagret i kontinuerlige hukommelsesblokke.
I modsætning til arrays behøver den sammenkædede liste ikke at gemme dataelementer i sammenhængende hukommelsesområder eller -blokke.
EN linket liste er sammensat af elementer kendt som 'knuder', der er opdelt i to dele. Den første komponent er den del, hvor vi gemmer de faktiske data, og den anden er en del, hvor vi gemmer markøren til den næste node. Denne type struktur er kendt som en ' enkelt linket liste .'
Linket liste i C++
Denne tutorial vil gennemgå den enkeltforbundne liste i dybden.
En enkelt lænket listes struktur er illustreret i diagrammet nedenfor
- Som vi har set i ovenstående del, er den første knude på den sammenkædede liste kendt som 'hovedet', mens den sidste knude kaldes 'halen'. Det er fordi der ikke er angivet nogen hukommelsesadresse i den sidste knude, at den sidste knude på den sammenkædede liste vil have en null næste pointer.
- Fordi hver knude indeholder en pointer til den næste knude, behøver dataelementer i den sammenkædede liste ikke at blive bibeholdt på sammenhængende steder. Noderne kan være spredt i hukommelsen. Fordi hver node har adressen på den efter sig, kan vi få adgang til noderne, når vi vil.
- Vi kan hurtigt tilføje og fjerne dataelementer fra den tilsluttede liste. Som et resultat kan den linkede liste øges eller trække sig sammen dynamisk. Den sammenkædede liste har ingen maksimal mængde dataelementer, den kan indeholde. Som et resultat kan vi tilføje så mange dataelementer, som vi vil, til den linkede liste, så længe der er RAM tilgængelig.
- Fordi vi ikke behøver at angive, hvor mange elementer vi skal bruge i den linkede liste på forhånd, sparer den linkede liste hukommelsesplads ud over at være enkel at indsætte og slette. Den eneste plads, der bruges af en sammenkædet liste, er at gemme markøren til den næste node, hvilket tilføjer nogle omkostninger.
Herefter vil vi gennemgå de forskellige operationer, der kan udføres på en sammenkædet liste.
java matematik tilfældig
1) Indsættelse
Den sammenkædede liste udvides ved at tilføje til den. Selvom det virker simpelt, givet den linkede listes struktur, ved vi, at hver gang et dataelement tilføjes, skal vi ændre de næste pointere for de forrige og næste knudepunkter for det nye element, som vi har tilføjet.
Hvor det nye dataelement vil blive indsat, er det andet aspekt at tænke på.
Der er tre steder, hvor et dataelement kan tilføjes til den sammenkædede liste.
tegn til streng
en. Begyndende med den linkede liste
Nedenfor er en sammenhængende liste over tallene 2->4->6->8->10. Hovedet, der peger på node 2, vil nu pege på node 1, og den næste pointer på node 1 vil have hukommelsesadressen for node 2, som vist i illustrationen nedenfor, hvis vi tilføjer en ny node 1 som den første node på listen .
Som følge heraf er den nye linkede liste 1->2->4->6->8->10.
b. Efter den givne Node
I dette tilfælde får vi en node og skal tilføje en ny node bag den. Den linkede liste vil se ud som følger, hvis node f tilføjes til den linkede liste a->b->c->d->e efter node c:
Vi kontrollerer derfor, om den angivne node er til stede i diagrammet ovenfor. Hvis den er til stede, oprettes en ny node f. Derefter peger vi node c's næste pointer mod den helt nye node f. Node f's næste pointer peger nu på node d.
c. Den linkede listes sidste punkt
I det tredje tilfælde tilføjes en ny node til slutningen af den sammenkædede liste. Tag hensyn til den linkede liste nedenfor: a->b->c->d->e, med tilføjelse af node f i slutningen. Efter tilføjelse af noden vil den sammenkædede liste se sådan ud.
maven repository
Som et resultat konstruerer vi en ny node f. Halemarkøren, der fører til null, peges derefter på f, og node fs næste pointer peges på null. I programmeringssproget nedenfor har vi genereret alle tre typer indsætningsfunktioner.
En sammenkædet liste kan erklæres som en struktur eller som en klasse i C++. En sammenkædet liste erklæret som en struktur er en klassisk C-stil erklæring. En sammenkædet liste bruges som en klasse i moderne C++, hovedsageligt ved brug af standard skabelonbibliotek.
Struktur blev brugt i følgende applikation til at erklære og generere en linket liste. Dens medlemmer vil være data og en pegepind 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) Sletning
I lighed med indsættelse kræver sletning af en node fra en sammenkædet liste mange punkter, hvorfra noden kan fjernes. Vi kan fjerne den linkede listes første, sidste eller kth node tilfældigt. Vi skal opdatere den næste pointer og alle andre linkede listemarkører korrekt for at bevare den linkede liste efter sletning.
I den følgende C++-implementering har vi to sletningsmetoder: sletning af listens indledende node og sletning af listens sidste node. Vi begynder med at tilføje noder til listens hoved. Listens indhold vises derefter efter hver tilføjelse og sletning.
C++ program:
fuldt adderkredsløb
#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> Nodetælling
Mens du krydser den linkede liste, kan processen med at tælle antallet af noder udføres. I den foregående tilgang så vi, at hvis vi havde brug for at indsætte/slette en node eller vise indholdet af den linkede liste, var vi nødt til at krydse den linkede liste fra begyndelsen.
Indstilling af en tæller og inkrementering, mens vi krydser hver node, vil give os antallet af noder på den sammenkædede liste.
Forskelle mellem Array og Linked List:
| Array | Linket liste |
|---|---|
| Arrays har en defineret størrelse. | Størrelsen af den linkede liste er variabel. |
| Det er svært at indsætte et nyt element. | Indsættelse og sletning er nemmere. |
| Adgang er tilladt tilfældigt. | Ingen tilfældig adgang er mulig. |
| Elementer er relativt tæt eller sammenhængende. | Elementerne er ikke sammenhængende. |
| Der kræves ikke yderligere plads til følgende pointer. | Følgende markør kræver ekstra hukommelse. |
Funktionalitet
Da sammenkædede lister og arrays begge er lineære datastrukturer, der indeholder objekter, kan de bruges på lignende måder for de fleste applikationer.
terminal kali linux
Følgende er nogle eksempler på linkede listeapplikationer:
- Stabler og køer kan implementeres ved hjælp af linkede lister.
- Når vi skal udtrykke grafer som tilgrænsende lister, kan vi bruge en linket liste til at implementere dem.
- Vi kan også bruge en sammenkædet liste til at indeholde et matematisk polynomium.
- I tilfælde af hashing anvendes linkede lister til at implementere buckets.
- Når et program kræver dynamisk hukommelsesallokering, kan vi bruge en linket liste, fordi linkede lister er mere effektive i dette tilfælde.
Konklusion
Sammenkædede lister er datastrukturer, der bruges til at holde dataelementer i en lineær, men ikke-sammenhængende form. En sammenkædet liste består af noder med hver to komponenter. Den første komponent består af data, mens den anden halvdel har en markør, der gemmer hukommelsesadressen på det følgende medlem af listen.
Som et tegn på, at den linkede liste er afsluttet, har det sidste punkt på listen sin næste markør sat til NULL. Hovedet er det første punkt på listen. Den sammenkædede liste giver mulighed for en række handlinger såsom indsættelse, sletning, gennemkøring og så videre. Sammenkædede lister foretrækkes frem for arrays til dynamisk hukommelsesallokering.
Sammenkædede lister er svære at udskrive eller krydse, fordi vi ikke kan få adgang til elementerne tilfældigt ligesom arrays. Sammenlignet med arrays er procedurer for indsættelse og sletning billigere.
I denne tutorial lærte vi alt, hvad der er at vide om lineært linkede lister. Sammenkædede lister kan også være dobbeltlinkede eller cirkulære. I vores kommende selvstudier vil vi gennemgå disse lister i detaljer.