linked list data structure c with illustration
Eine detaillierte Studie der verknüpften Liste in C ++.
Eine verknüpfte Liste ist eine lineare dynamische Datenstruktur zum Speichern von Datenelementen. Wir haben bereits Arrays in unseren vorherigen Themen zu grundlegendem C ++ gesehen. Wir wissen auch, dass Arrays eine lineare Datenstruktur sind, die Datenelemente an zusammenhängenden Orten speichern.
Im Gegensatz zu Arrays speichert die verknüpfte Liste keine Datenelemente an zusammenhängenden Speicherorten.
Eine verknüpfte Liste besteht aus Elementen, die als 'Knoten' bezeichnet werden und zwei Teile enthalten. Der erste Teil speichert die tatsächlichen Daten und der zweite Teil hat einen Zeiger, der auf den nächsten Knoten zeigt. Diese Struktur wird normalerweise als 'einfach verknüpfte Liste' bezeichnet.
=> Lesen Sie hier die besten C ++ - Schulungsanleitungen.
Was du lernen wirst:
Verknüpfte Liste in C ++
Wir werden uns die einzeln verknüpfte Liste in diesem Tutorial genauer ansehen.
Das folgende Diagramm zeigt den Aufbau einer einfach verknüpften Liste.
Wie oben gezeigt, heißt der erste Knoten der verknüpften Liste 'Kopf', während der letzte Knoten 'Schwanz' heißt. Wie wir sehen, hat der letzte Knoten der verknüpften Liste den nächsten Zeiger als Null, da auf keine Speicheradresse verwiesen wird.
Da jeder Knoten einen Zeiger auf den nächsten Knoten hat, müssen Datenelemente in der verknüpften Liste nicht an zusammenhängenden Stellen gespeichert werden. Die Knoten können im Speicher verstreut sein. Wir können jederzeit auf die Knoten zugreifen, da jeder Knoten eine Adresse des nächsten Knotens hat.
Wir können der verknüpften Liste Datenelemente hinzufügen und Elemente einfach aus der Liste löschen. Somit ist es möglich, die verknüpfte Liste dynamisch zu vergrößern oder zu verkleinern. Es gibt keine Obergrenze für die Anzahl der Datenelemente in der verknüpften Liste. Solange Speicher verfügbar ist, können der verknüpften Liste so viele Datenelemente hinzugefügt werden.
Abgesehen vom einfachen Einfügen und Löschen verschwendet die verknüpfte Liste auch keinen Speicherplatz, da wir nicht vorher angeben müssen, wie viele Elemente wir in der verknüpften Liste benötigen. Der einzige Speicherplatz, den die verknüpfte Liste belegt, dient zum Speichern des Zeigers auf den nächsten Knoten, der einen geringen Overhead verursacht.
Als nächstes werden wir die verschiedenen Operationen diskutieren, die an einer verknüpften Liste ausgeführt werden können.
Operationen
Genau wie die anderen Datenstrukturen können wir auch für die verknüpfte Liste verschiedene Operationen ausführen. Im Gegensatz zu Arrays, in denen wir direkt mit dem Index direkt auf das Element zugreifen können, auch wenn es irgendwo dazwischen liegt, können wir mit einer verknüpften Liste nicht denselben Direktzugriff durchführen.
Um auf einen Knoten zugreifen zu können, müssen wir die verknüpfte Liste von Anfang an durchlaufen und erst dann können wir auf den gewünschten Knoten zugreifen. Der zufällige Zugriff auf die Daten aus der verknüpften Liste erweist sich daher als teuer.
Wir können verschiedene Operationen an einer verknüpften Liste ausführen, wie unten angegeben:
# 1) Einfügen
Durch das Einfügen einer verknüpften Liste wird der verknüpften Liste ein Element hinzugefügt. Obwohl es angesichts der Struktur der verknüpften Liste einfach klingt, wissen wir, dass wir jedes Mal, wenn ein Datenelement zur verknüpften Liste hinzugefügt wird, die nächsten Zeiger des vorherigen und nächsten Knotens des neuen Elements ändern müssen, das wir eingefügt haben.
Das zweite, was wir berücksichtigen müssen, ist der Ort, an dem das neue Datenelement hinzugefügt werden soll.
In der verknüpften Liste gibt es drei Positionen, an denen ein Datenelement hinzugefügt werden kann.
# 1) Am Anfang der verknüpften Liste
Eine verknüpfte Liste wird unter 2-> 4-> 6-> 8-> 10 angezeigt. Wenn wir einen neuen Knoten 1 als ersten Knoten der Liste hinzufügen möchten, zeigt der Kopf, der auf Knoten 2 zeigt, jetzt auf 1, und der nächste Zeiger von Knoten 1 hat eine Speicheradresse von Knoten 2, wie unten gezeigt Zahl.
Fragen und Antworten zum Shell-Scripting-Interview
Somit wird die neue verknüpfte Liste 1-> 2-> 4-> 6-> 8-> 10.
# 2) Nach dem angegebenen Knoten
Hier wird ein Knoten angegeben und wir müssen nach dem angegebenen Knoten einen neuen Knoten hinzufügen. Wenn wir in der unten verlinkten Liste a-> b-> c-> d -> e einen Knoten f nach Knoten c hinzufügen möchten, sieht die verknüpfte Liste wie folgt aus:
Daher prüfen wir im obigen Diagramm, ob der angegebene Knoten vorhanden ist. Wenn es vorhanden ist, erstellen wir einen neuen Knoten f. Dann zeigen wir mit dem nächsten Zeiger des Knotens c auf den neuen Knoten f. Der nächste Zeiger des Knotens f zeigt nun auf den Knoten d.
# 3) Am Ende der verknüpften Liste
Im dritten Fall fügen wir am Ende der verknüpften Liste einen neuen Knoten hinzu. Angenommen, wir haben dieselbe verknüpfte Liste a-> b-> c-> d-> e und müssen am Ende der Liste einen Knoten f hinzufügen. Die verknüpfte Liste sieht nach dem Hinzufügen des Knotens wie unten gezeigt aus.
Somit erstellen wir einen neuen Knoten f. Dann zeigt der auf null zeigende Endzeiger auf f und der nächste Zeiger des Knotens f auf null. Wir haben alle drei Arten von Einfügefunktionen im folgenden C ++ - Programm implementiert.
In C ++ können wir eine verknüpfte Liste als Struktur oder als Klasse deklarieren. Das Deklarieren einer verknüpften Liste als Struktur ist eine traditionelle C-Deklaration. Eine verknüpfte Liste als Klasse wird in modernem C ++ verwendet, hauptsächlich unter Verwendung der Standardvorlagenbibliothek.
Im folgenden Programm haben wir die Struktur verwendet, um eine verknüpfte Liste zu deklarieren und zu erstellen. Es hat Daten und einen Zeiger auf das nächste Element als Mitglieder.
#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 Ausgabe:
Letzte verknüpfte Liste:
30–> 20–> 50–> 10–> 40–> null
Als nächstes implementieren wir die Operation zum Einfügen verknüpfter Listen in Java. In der Java-Sprache wird die verknüpfte Liste als Klasse implementiert. Das folgende Programm ähnelt in seiner Logik dem C ++ - Programm. Der einzige Unterschied besteht darin, dass wir eine Klasse für die verknüpfte Liste verwenden.
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 (); } } Ausgabe:
Letzte verknüpfte Liste:
10–> 20–> 30–> 40–> 50–> null
Sowohl im obigen Programm, C ++ als auch in Java, haben wir separate Funktionen, um einen Knoten vor der Liste, am Ende der Liste und zwischen den in einem Knoten angegebenen Listen hinzuzufügen. Am Ende drucken wir den Inhalt der Liste, die mit allen drei Methoden erstellt wurde.
# 2) Löschen
Wie beim Einfügen umfasst das Löschen eines Knotens aus einer verknüpften Liste auch verschiedene Positionen, an denen der Knoten gelöscht werden kann. Wir können den ersten Knoten, den letzten Knoten oder einen zufälligen k-ten Knoten aus der verknüpften Liste löschen. Nach dem Löschen müssen wir den nächsten Zeiger und die anderen Zeiger in der verknüpften Liste entsprechend anpassen, damit die verknüpfte Liste intakt bleibt.
In der folgenden C ++ - Implementierung haben wir zwei Löschmethoden angegeben, d. H. Das Löschen des ersten Knotens in der Liste und das Löschen des letzten Knotens in der Liste. Wir erstellen zuerst eine Liste, indem wir dem Kopf Knoten hinzufügen. Dann zeigen wir den Inhalt der Liste nach dem Einfügen und jedem Löschen an.
#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 ' Ausgabe:
Verknüpfte Liste erstellt
10–> 8–> 6–> 4–> 2–
> NULL
Verknüpfte Liste nach dem Löschen des Kopfknotens
8–> 6–> 4–> 2–
> NULL
Verknüpfte Liste nach dem Löschen des letzten Knotens
8–> 6–> 4–> NULL
Als nächstes folgt die Java-Implementierung zum Löschen von Knoten aus der verknüpften Liste. Die Implementierungslogik ist dieselbe wie im C ++ - Programm. Der einzige Unterschied besteht darin, dass die verknüpfte Liste als Klasse deklariert ist.
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'); } } Ausgabe:
Verknüpfte Liste erstellt:
9–> 7–> 5–> 3–> 1–
> null
Verknüpfte Liste nach dem Löschen des Kopfknotens:
7–> 5–> 3–> 1–
> null
Verknüpfte Liste nach dem Löschen des letzten Knotens:
7–> 5–> 3–> null
Zählen Sie die Anzahl der Knoten
Die Operation zum Zählen der Anzahl von Knoten kann ausgeführt werden, während die verknüpfte Liste durchlaufen wird. Wir haben bereits in der obigen Implementierung gesehen, dass wir die verknüpfte Liste von Anfang an durchlaufen müssen, wenn wir einen Knoten einfügen / löschen oder Inhalte der verknüpften Liste anzeigen müssen.
Wenn Sie einen Zähler beibehalten und ihn beim Durchlaufen jedes Knotens erhöhen, erhalten Sie die Anzahl der in der verknüpften Liste vorhandenen Knoten. Wir werden dieses Programm den Lesern zur Umsetzung überlassen.
Arrays und verknüpfte Listen
Nachdem wir die Funktionsweise und Implementierung der verknüpften Liste gesehen haben, vergleichen wir, wie fair Arrays und verknüpfte Listen im Vergleich zueinander sind.
Arrays Verknüpfte Listen Arrays haben eine feste Größe Die Größe der verknüpften Liste ist dynamisch Das Einfügen eines neuen Elements ist teuer Das Einfügen / Löschen ist einfacher Direktzugriff ist erlaubt Direktzugriff nicht möglich Elemente befinden sich an einer zusammenhängenden Stelle Elemente haben eine nicht zusammenhängende Position Für den nächsten Zeiger ist kein zusätzlicher Platz erforderlich Zusätzlicher Speicherplatz für den nächsten Zeiger erforderlich
Anwendungen
Da Arrays und verknüpfte Listen sowohl zum Speichern von Elementen als auch als lineare Datenstrukturen verwendet werden, können beide Strukturen für die meisten Anwendungen auf ähnliche Weise verwendet werden.
Einige der Anwendungen für verknüpfte Listen lauten wie folgt:
- Eine verknüpfte Liste kann verwendet werden, um Stapel und Warteschlangen zu implementieren.
- Eine verknüpfte Liste kann auch verwendet werden, um Diagramme zu implementieren, wenn Diagramme als Adjazenzlisten dargestellt werden müssen.
- Ein mathematisches Polynom kann als verknüpfte Liste gespeichert werden.
- Bei der Hashing-Technik werden die beim Hashing verwendeten Buckets mithilfe der verknüpften Listen implementiert.
- Wenn ein Programm eine dynamische Speicherzuweisung erfordert, können wir eine verknüpfte Liste verwenden, da verknüpfte Listen in diesem Fall effizienter arbeiten.
Fazit
Verknüpfte Listen sind die Datenstrukturen, mit denen Datenelemente linear, aber nicht zusammenhängend gespeichert werden. Eine verknüpfte Liste ist eine Sammlung von Knoten, die einen Datenteil und einen nächsten Zeiger enthalten, der die Speicheradresse des nächsten Elements in der Liste enthält.
Für das letzte Element in der Liste wird der nächste Zeiger auf NULL gesetzt, wodurch das Ende der Liste angezeigt wird. Das erste Element der Liste heißt Head. Die verknüpfte Liste unterstützt verschiedene Vorgänge wie Einfügen, Löschen, Durchlaufen usw. Bei dynamischer Speicherzuweisung werden verknüpfte Listen Arrays vorgezogen.
Verknüpfte Listen sind in Bezug auf ihre Durchquerung teuer, da wir nicht wie Arrays zufällig auf Elemente zugreifen können. Einfüge-Lösch-Operationen sind jedoch im Vergleich zu Arrays weniger teuer.
In diesem Tutorial haben wir alles über linear verknüpfte Listen gelernt. Verknüpfte Listen können auch kreisförmig oder doppelt sein. Wir werden uns diese Listen in unseren kommenden Tutorials genauer ansehen.
=> Hier finden Sie eine vollständige C ++ - Schulungsserie.
Literatur-Empfehlungen
- Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung
- Doppelt verknüpfte Listendatenstruktur in C ++ mit Abbildung
- Warteschlangendatenstruktur in C ++ mit Illustration
- Stapeldatenstruktur in C ++ mit Illustration
- Datenstruktur der Prioritätswarteschlange in C ++ mit Abbildung
- Top 15 der besten kostenlosen Data Mining-Tools: Die umfassendste Liste
- 15 besten ETL-Tools im Jahr 2021 (Eine vollständige aktualisierte Liste)
- Einführung in Datenstrukturen in C ++