A gekoppelde lijst is een soort lineaire dynamische datastructuur die we gebruiken om data-elementen op te slaan. Arrays zijn ook een soort lineaire datastructuur waarbij de data-items worden opgeslagen in continue geheugenblokken.

In tegenstelling tot arrays hoeft de gekoppelde lijst geen gegevenselementen op te slaan in aaneengesloten geheugengebieden of blokken.

vergelijkbare lijst

A gekoppelde lijst is samengesteld uit elementen die bekend staan ​​als 'Nodes' en die in twee delen zijn verdeeld. De eerste component is het deel waar we de daadwerkelijke gegevens opslaan, en de tweede is een deel waar we de verwijzing naar het volgende knooppunt opslaan. Dit type structuur staat bekend als een ' enkelvoudig gekoppelde lijst .'

Gekoppelde lijst in C++

In deze tutorial wordt de afzonderlijk gekoppelde lijst diepgaand besproken.

De structuur van een enkelvoudig gekoppelde lijst wordt geïllustreerd in het onderstaande diagram

• Zoals we in het bovenstaande deel hebben gezien, staat het eerste knooppunt van de gekoppelde lijst bekend als de 'kop', terwijl het laatste knooppunt de 'staart' wordt genoemd. Omdat er geen geheugenadres is opgegeven in het laatste knooppunt, zal het laatste knooppunt van de gekoppelde lijst een nul-volgende aanwijzer hebben.
• Omdat elk knooppunt een verwijzing naar het volgende knooppunt bevat, hoeven gegevenselementen in de gekoppelde lijst niet op aangrenzende locaties te worden bewaard. De knooppunten kunnen door het geheugen verspreid zijn. Omdat elk knooppunt het adres heeft van het knooppunt erna, hebben we toegang tot de knooppunten wanneer we maar willen.
• We kunnen snel gegevensitems toevoegen aan en verwijderen uit de verbonden lijst. Als gevolg hiervan kan de gekoppelde lijst dynamisch groter of kleiner worden. De gekoppelde lijst heeft geen maximumaantal gegevensitems die deze kan bevatten. Als gevolg hiervan kunnen we zoveel gegevensitems toevoegen als we willen aan de gekoppelde lijst, zolang er RAM beschikbaar is.
• Omdat we niet vooraf hoeven te specificeren hoeveel items we nodig hebben in de gekoppelde lijst, bespaart de gekoppelde lijst geheugenruimte en is deze eenvoudig in te voegen en te verwijderen. De enige ruimte die door een gekoppelde lijst wordt gebruikt, is het opslaan van de verwijzing naar het volgende knooppunt, wat enige kosten met zich meebrengt.

Daarna zullen we de verschillende bewerkingen bespreken die kunnen worden uitgevoerd op een gekoppelde lijst.

1) Inbrengen

De gekoppelde lijst wordt uitgebreid door er iets aan toe te voegen. Hoewel het eenvoudig lijkt, weten we, gezien de structuur van de gekoppelde lijst, dat elke keer dat een gegevensitem wordt toegevoegd, we de volgende verwijzingen naar de vorige en volgende knooppunten van het nieuwe item dat we hebben toegevoegd moeten wijzigen.

Waar het nieuwe gegevensitem zal worden ingevoegd, is het tweede aspect waar u over moet nadenken.

Er zijn drie plaatsen waar een gegevensitem aan de gekoppelde lijst kan worden toegevoegd.

A. Te beginnen met de gekoppelde lijst

Hieronder vindt u een samenhangende lijst met de getallen 2->4->6->8->10. Het hoofd dat naar knooppunt 2 wijst, zal nu naar knooppunt 1 wijzen, en de volgende aanwijzer van knooppunt 1 zal het geheugenadres van knooppunt 2 hebben, zoals weergegeven in de onderstaande afbeelding, als we een nieuw knooppunt 1 toevoegen als het eerste knooppunt in de lijst .

Als gevolg hiervan is de nieuwe gekoppelde lijst 1->2->4->6->8->10.

B. Na het opgegeven Node

css afbeeldingsgrootte wijzigen

In dit geval krijgen we een knooppunt en moeten we daarachter een nieuw knooppunt toevoegen. De gekoppelde lijst ziet er als volgt uit als knooppunt f wordt toegevoegd aan de gekoppelde lijst a->b->c->d->e na knooppunt c:

We controleren daarom of het opgegeven knooppunt aanwezig is in het bovenstaande diagram. Als het aanwezig is, wordt een nieuw knooppunt f gemaakt. Daarna wijzen we de volgende aanwijzer van knooppunt c naar het gloednieuwe knooppunt f. De volgende aanwijzer van knooppunt f wijst nu naar knooppunt d.

C. Het laatste item van de gekoppelde lijst

In het derde geval wordt een nieuw knooppunt toegevoegd aan het einde van de gekoppelde lijst. Houd rekening met de onderstaande gekoppelde lijst: a->b->c->d->e, met de toevoeging van knooppunt f aan het einde. Na het toevoegen van het knooppunt zal de gekoppelde lijst er als volgt uitzien.

Als resultaat construeren we een nieuw knooppunt f. De staartwijzer die naar nul leidt, wijst vervolgens naar f, en de volgende wijzer van knooppunt f wordt naar nul gericht. In de onderstaande programmeertaal hebben we alle drie de typen invoegfuncties gegenereerd.

Een gekoppelde lijst kan worden gedeclareerd als een structuur of als een klasse in C++. Een gekoppelde lijst die als structuur is gedeclareerd, is een klassiek statement in C-stijl. Een gekoppelde lijst wordt in modern C++ als klasse gebruikt, voornamelijk bij gebruik van de standaardsjabloonbibliotheek.

In de volgende toepassing is structuur gebruikt om een ​​gekoppelde lijst te declareren en te genereren. De leden ervan zijn gegevens en een verwijzing naar het volgende element.

C++ Programma:

 #include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -&gt; data = nodeData; newNode1 -&gt; next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -&gt; next; prevNode -&gt; next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -&gt; data = nodeData; newNode1 -&gt; next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -&gt; next != NULL ) last = last -&gt; next; last -&gt; 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--&gt;25--&gt;55--&gt;15--&gt;45--&gt;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&apos;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&apos;s initial node and deleting the list&apos;s last node. We begin by adding nodes to the head of the list. The list&apos;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 -&gt; next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -&gt; next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -&gt; next -&gt; next != NULL ) secondLast = secondLast-&gt;next; delete ( secondLast -&gt; next ); secondLast -&gt; next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -&gt; data = newData; newNode1 -&gt; next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &amp;head, 25 ); push ( &amp;head, 45 ); push ( &amp;head, 65); push ( &amp;head, 85 ); push ( &amp;head, 95 ); Node* temp; cout &lt;&lt; &apos;Linked list created &apos; &lt; 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--&gt;85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting head node 85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting last node 85--&gt;65--&gt;45--&gt;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&apos;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) Verwijdering

Net als bij invoegen vereist het verwijderen van een knooppunt uit een gekoppelde lijst veel punten waaruit het knooppunt kan worden geëlimineerd. We kunnen het eerste, laatste of k-de knooppunt van de gekoppelde lijst willekeurig verwijderen. We moeten de volgende aanwijzer en alle andere gekoppelde lijstaanwijzers correct bijwerken om de gekoppelde lijst na verwijdering te behouden.

In de volgende C++-implementatie hebben we twee verwijderingsmethoden: het verwijderen van het initiële knooppunt van de lijst en het verwijderen van het laatste knooppunt van de lijst. We beginnen met het toevoegen van knooppunten aan de kop van de lijst. De inhoud van de lijst wordt vervolgens na elke toevoeging of verwijdering weergegeven.

Python-constructeur

C++ Programma:

 #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 -&gt; next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -&gt; next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -&gt; next -&gt; next != NULL ) secondLast = secondLast-&gt;next; delete ( secondLast -&gt; next ); secondLast -&gt; next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -&gt; data = newData; newNode1 -&gt; next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &amp;head, 25 ); push ( &amp;head, 45 ); push ( &amp;head, 65); push ( &amp;head, 85 ); push ( &amp;head, 95 ); Node* temp; cout &lt;&lt; &apos;Linked list created &apos; &lt; 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--&gt;85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting head node 85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting last node 85--&gt;65--&gt;45--&gt;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&apos;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>

Aantal knooppunten

Terwijl u door de gekoppelde lijst loopt, kan het proces van het tellen van het aantal knooppunten worden uitgevoerd. In de voorgaande benadering zagen we dat als we een knooppunt moesten invoegen/verwijderen of de inhoud van de gekoppelde lijst moesten weergeven, we de gekoppelde lijst vanaf het begin moesten doorlopen.

Door een teller in te stellen en te verhogen, terwijl we elk knooppunt doorlopen, krijgen we het aantal knooppunten in de gekoppelde lijst.

Verschillen tussen array en gekoppelde lijst:

Functionaliteit

Omdat gekoppelde lijsten en arrays beide lineaire datastructuren zijn die objecten bevatten, kunnen ze voor de meeste toepassingen op vergelijkbare manieren worden gebruikt.

Hieronder volgen enkele voorbeelden van gekoppelde lijsttoepassingen:

tekenreeks in c++

• Stapels en wachtrijen kunnen worden geïmplementeerd met behulp van gekoppelde lijsten.
• Wanneer we grafieken moeten uitdrukken als aangrenzende lijsten, kunnen we een gekoppelde lijst gebruiken om ze te implementeren.
• We kunnen ook een gekoppelde lijst gebruiken om een ​​wiskundige polynoom te bevatten.
• In het geval van hashen worden gekoppelde lijsten gebruikt om de buckets te implementeren.
• Wanneer een programma dynamische geheugentoewijzing vereist, kunnen we een gekoppelde lijst gebruiken, omdat gekoppelde lijsten in dit geval efficiënter zijn.

Conclusie

Gekoppelde lijsten zijn datastructuren die worden gebruikt om data-elementen in een lineaire maar niet-aaneengesloten vorm vast te houden. Een gekoppelde lijst bestaat uit knooppunten met elk twee componenten. De eerste component bestaat uit gegevens, terwijl de tweede helft een aanwijzer heeft die het geheugenadres van het volgende lid van de lijst opslaat.

Als teken dat de gekoppelde lijst is beëindigd, wordt de volgende pointer van het laatste item in de lijst ingesteld op NULL. Het hoofd is het eerste item op de lijst. De gekoppelde lijst maakt een verscheidenheid aan acties mogelijk, zoals invoegen, verwijderen, doorlopen, enzovoort. Gekoppelde lijsten krijgen de voorkeur boven arrays voor dynamische geheugentoewijzing.

Gekoppelde lijsten zijn moeilijk af te drukken of te doorkruisen omdat we de elementen niet willekeurig kunnen benaderen, zoals bij arrays. In vergelijking met arrays zijn invoeg-verwijderingsprocedures goedkoper.

In deze tutorial hebben we alles geleerd wat er te weten valt over lineair gekoppelde lijsten. Gekoppelde lijsten kunnen ook dubbel gekoppeld of circulair zijn. In onze komende tutorials zullen we deze lijsten in detail doornemen.