A verlinkte Liste ist eine Art lineare dynamische Datenstruktur, die wir zum Speichern von Datenelementen verwenden. Arrays sind ebenfalls eine Art lineare Datenstruktur, bei der die Datenelemente in fortlaufenden Speicherblöcken gespeichert werden.
Im Gegensatz zu Arrays muss die verknüpfte Liste keine Datenelemente in zusammenhängenden Speicherbereichen oder -blöcken speichern.
A verlinkte Liste besteht aus Elementen, die als „Knoten“ bekannt sind und in zwei Teile unterteilt sind. Die erste Komponente ist der Teil, in dem wir die eigentlichen Daten speichern, und die zweite ist ein Teil, in dem wir den Zeiger auf den nächsten Knoten speichern. Diese Art von Struktur wird als „ einfach verknüpfte Liste .'
Verknüpfte Liste in C++
In diesem Tutorial wird die einfach verknüpfte Liste ausführlich behandelt.
Die Struktur einer einfach verknüpften Liste ist im folgenden Diagramm dargestellt
- Wie wir im obigen Teil gesehen haben, wird der erste Knoten der verknüpften Liste als „Kopf“ bezeichnet, während der letzte Knoten als „Ende“ bezeichnet wird. Da im letzten Knoten keine Speicheradresse angegeben ist, hat der letzte Knoten der verknüpften Liste einen Null-Nächstenzeiger.
- Da jeder Knoten einen Zeiger auf den nächsten Knoten enthält, müssen Datenelemente in der verknüpften Liste nicht an zusammenhängenden Orten aufbewahrt werden. Die Knoten können über den gesamten Speicher verteilt sein. Da jeder Knoten die Adresse des darauf folgenden Knotens hat, können wir jederzeit auf die Knoten zugreifen.
- Wir können schnell Datenelemente zur verbundenen Liste hinzufügen und daraus entfernen. Dadurch kann die verknüpfte Liste dynamisch wachsen oder schrumpfen. Die verknüpfte Liste hat keine maximale Menge an Datenelementen, die sie enthalten kann. Dadurch können wir beliebig viele Datenelemente zur verknüpften Liste hinzufügen, solange RAM verfügbar ist.
- Da wir nicht im Voraus angeben müssen, wie viele Elemente wir in der verknüpften Liste benötigen, spart die verknüpfte Liste Speicherplatz und lässt sich einfach einfügen und löschen. Der einzige von einer verknüpften Liste benötigte Speicherplatz besteht darin, den Zeiger auf den nächsten Knoten zu speichern, was einige Kosten verursacht.
Anschließend gehen wir die verschiedenen Operationen durch, die für eine verknüpfte Liste ausgeführt werden können.
1) Einfügung
Die verknüpfte Liste wird durch die Aktion „Hinzufügen“ erweitert. Obwohl es angesichts der Struktur der verknüpften Liste einfach erscheint, wissen wir, dass wir jedes Mal, wenn ein Datenelement hinzugefügt wird, die nächsten Zeiger des vorherigen und nächsten Knotens des neuen Elements, das wir hinzugefügt haben, ändern müssen.
Der zweite Aspekt, über den man nachdenken muss, ist, wo das neue Datenelement eingefügt wird.
Es gibt drei Stellen, an denen ein Datenelement zur verknüpften Liste hinzugefügt werden kann.
A. Beginnend mit der verknüpften Liste
Unten finden Sie eine zusammenhängende Liste der Zahlen 2->4->6->8->10. Der auf Knoten 2 zeigende Kopf zeigt nun auf Knoten 1 und der nächste Zeiger von Knoten 1 hat die Speicheradresse von Knoten 2, wie in der Abbildung unten gezeigt, wenn wir einen neuen Knoten 1 als ersten Knoten in der Liste hinzufügen .
Infolgedessen lautet die neue verknüpfte Liste 1->2->4->6->8->10.
B. Nach dem angegebenen Knoten
In diesem Fall erhalten wir einen Knoten und müssen dahinter einen neuen Knoten hinzufügen. Die verknüpfte Liste sieht wie folgt aus, wenn Knoten f nach Knoten c zur verknüpften Liste a->b->c->d->e hinzugefügt wird:
Wir prüfen daher, ob der angegebene Knoten im obigen Diagramm vorhanden ist. Wenn es vorhanden ist, wird ein neuer Knoten f erstellt. Danach zeigen wir den nächsten Zeiger von Knoten c auf den brandneuen Knoten f. Der nächste Zeiger des Knotens f zeigt nun auf den Knoten d.
C. Das letzte Element der verknüpften Liste
Instanz von
Im dritten Fall wird am Ende der verknüpften Liste ein neuer Knoten hinzugefügt. Berücksichtigen Sie die folgende verknüpfte Liste: a->b->c->d->e, mit dem Zusatz Knoten f am Ende. Nach dem Hinzufügen des Knotens sieht die verknüpfte Liste folgendermaßen aus.
Als Ergebnis konstruieren wir einen neuen Knoten f. Der Endzeiger, der zu Null führt, zeigt dann auf f, und der nächste Zeiger des Knotens f zeigt auf Null. In der folgenden Programmiersprache haben wir alle drei Arten von Einfügefunktionen generiert.
Eine verknüpfte Liste kann in C++ als Struktur oder als Klasse deklariert werden. Eine als Struktur deklarierte verknüpfte Liste ist eine klassische Anweisung im C-Stil. Eine verknüpfte Liste wird in modernem C++ als Klasse verwendet, hauptsächlich bei Verwendung der Standardvorlagenbibliothek.
Die Struktur wurde in der folgenden Anwendung verwendet, um eine verknüpfte Liste zu deklarieren und zu generieren. Seine Mitglieder sind Daten und ein Zeiger auf das folgende Element.
C++-Programm:
#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) Löschung
Ähnlich wie beim Einfügen erfordert das Löschen eines Knotens aus einer verknüpften Liste viele Punkte, an denen der Knoten entfernt werden könnte. Wir können den ersten, letzten oder k-ten Knoten der verknüpften Liste nach dem Zufallsprinzip entfernen. Wir müssen den nächsten Zeiger und alle anderen Zeiger der verknüpften Liste korrekt aktualisieren, um die verknüpfte Liste nach dem Löschen beizubehalten.
In der folgenden C++-Implementierung haben wir zwei Löschmethoden: Löschen des Anfangsknotens der Liste und Löschen des letzten Knotens der Liste. Wir beginnen mit dem Hinzufügen von Knoten zum Kopf der Liste. Nach jedem Hinzufügen und Löschen wird dann der Inhalt der Liste angezeigt.
C++-Programm:
#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> Knotenanzahl
Beim Durchlaufen der verknüpften Liste kann die Anzahl der Knoten gezählt werden. Im vorherigen Ansatz haben wir gesehen, dass wir die verknüpfte Liste von Anfang an durchlaufen mussten, wenn wir einen Knoten einfügen/löschen oder den Inhalt der verknüpften Liste anzeigen mussten.
Wenn wir einen Zähler setzen und jeden Knoten inkrementieren und durchlaufen, erhalten wir die Anzahl der Knoten in der verknüpften Liste.
Unterschiede zwischen Array und verknüpfter Liste:
| Array | Verlinkte Liste |
|---|---|
| Arrays haben eine definierte Größe. | Die Größe der verknüpften Liste ist variabel. |
| Das Einfügen eines neuen Elements ist schwierig. | Das Einfügen und Löschen ist einfacher. |
| Der Zugriff ist wahllos gestattet. | Es ist kein wahlfreier Zugriff möglich. |
| Elemente liegen relativ nahe beieinander oder grenzen aneinander. | Die Elemente sind nicht zusammenhängend. |
| Für den folgenden Zeiger ist kein zusätzlicher Platz erforderlich. | Der folgende Zeiger erfordert zusätzlichen Speicher. |
Funktionalität
Da es sich bei verknüpften Listen und Arrays um lineare Datenstrukturen handelt, die Objekte enthalten, können sie für die meisten Anwendungen auf ähnliche Weise verwendet werden.
Im Folgenden finden Sie einige Beispiele für verknüpfte Listenanwendungen:
So rufen Sie versteckte Apps ab
- Stapel und Warteschlangen können mithilfe verknüpfter Listen implementiert werden.
- Wenn wir Diagramme als Adjazenzlisten ausdrücken müssen, können wir sie mit einer verknüpften Liste implementieren.
- Wir können auch eine verknüpfte Liste verwenden, um ein mathematisches Polynom zu enthalten.
- Beim Hashing werden verknüpfte Listen zur Implementierung der Buckets verwendet.
- Wenn ein Programm eine dynamische Speicherzuweisung erfordert, können wir eine verknüpfte Liste verwenden, da verknüpfte Listen in diesem Fall effizienter sind.
Abschluss
Verknüpfte Listen sind Datenstrukturen, mit denen Datenelemente in linearer, aber nicht zusammenhängender Form gespeichert werden. Eine verknüpfte Liste besteht aus Knoten mit jeweils zwei Komponenten. Die erste Komponente besteht aus Daten, während die zweite Hälfte einen Zeiger enthält, der die Speicheradresse des folgenden Mitglieds der Liste speichert.
Als Zeichen dafür, dass die verknüpfte Liste beendet ist, wird der nächste Zeiger des letzten Elements in der Liste auf NULL gesetzt. Der Kopf ist das erste Element auf der Liste. Die verknüpfte Liste ermöglicht eine Vielzahl von Aktionen wie Einfügen, Löschen, Durchlaufen usw. Für die dynamische Speicherzuweisung werden verknüpfte Listen gegenüber Arrays bevorzugt.
Verknüpfte Listen sind schwer zu drucken oder zu durchlaufen, da wir nicht wie Arrays zufällig auf die Elemente zugreifen können. Im Vergleich zu Arrays sind Einfüge- und Löschvorgänge kostengünstiger.
In diesem Tutorial haben wir alles gelernt, was man über linear verknüpfte Listen wissen muss. Verknüpfte Listen können auch doppelt verknüpft oder zirkulär sein. In unseren kommenden Tutorials werden wir diese Listen im Detail durchgehen.