Datenstruktur und Algorithmen - Verknüpfte Liste

Eine verknüpfte Liste ist eine Folge von Datenstrukturen, die über Verknüpfungen miteinander verbunden sind.

Verknüpfte Liste ist eine Folge von Links, die Elemente enthalten. Jeder Link enthält eine Verbindung zu einem anderen Link. Die verknüpfte Liste ist nach dem Array die am zweithäufigsten verwendete Datenstruktur. Im Folgenden finden Sie wichtige Begriffe zum Verständnis des Konzepts der verknüpften Liste.

Link - Jeder Link einer verknüpften Liste kann Daten speichern, die als Element bezeichnet werden.
Next - Jeder Link einer verknüpften Liste enthält einen Link zum nächsten Link namens Weiter.
LinkedList - Eine verknüpfte Liste enthält den Verbindungslink zum ersten Link namens First.

Darstellung der verknüpften Liste

Die verknüpfte Liste kann als eine Kette von Knoten dargestellt werden, wobei jeder Knoten auf den nächsten Knoten zeigt.

Gemäß der obigen Abbildung sind die folgenden wichtigen Punkte zu berücksichtigen.

Verknüpfte Liste enthält ein Verknüpfungselement, das zuerst aufgerufen wird.
Jede Verbindung enthält ein Datenfeld und ein Verbindungsfeld, das als nächstes aufgerufen wird.
Jeder Link wird über seinen nächsten Link mit seinem nächsten Link verknüpft.
Der letzte Link enthält einen Link als null, um das Ende der Liste zu markieren.

Arten von verknüpften Listen

Im Folgenden sind die verschiedenen Arten von verknüpften Listen aufgeführt.

Simple Linked List - Die Objektnavigation ist nur vorwärts.
Doubly Linked List - Elemente können vorwärts und rückwärts navigiert werden.
Circular Linked List - Das letzte Element enthält einen Link des ersten Elements als nächstes und das erste Element enthält einen Link zum letzten Element wie zuvor.

Grundoperationen

Im Folgenden sind die grundlegenden Vorgänge aufgeführt, die von einer Liste unterstützt werden.

Insertion - Fügt am Anfang der Liste ein Element hinzu.
Deletion - Löscht ein Element am Anfang der Liste.
Display - Zeigt die vollständige Liste an.
Search - Sucht ein Element mit dem angegebenen Schlüssel.
Delete - Löscht ein Element mit dem angegebenen Schlüssel.

Einfügevorgang

Das Hinzufügen eines neuen Knotens zur verknüpften Liste ist eine mehr als einstufige Aktivität. Wir werden dies hier anhand von Diagrammen lernen. Erstellen Sie zunächst einen Knoten mit derselben Struktur und suchen Sie den Ort, an dem er eingefügt werden muss.

Stellen Sie sich vor, wir fügen einen Knoten ein B (NewNode), zwischen A (LeftNode) und C(RightNode). Dann zeigen Sie B. neben C -

NewNode.next −> RightNode;

Es sollte so aussehen -

Jetzt sollte der nächste Knoten links auf den neuen Knoten zeigen.

LeftNode.next −> NewNode;

Dadurch wird der neue Knoten in die Mitte der beiden gesetzt. Die neue Liste sollte so aussehen -

Ähnliche Schritte sollten unternommen werden, wenn der Knoten am Anfang der Liste eingefügt wird. Beim Einfügen am Ende sollte der vorletzte Knoten der Liste auf den neuen Knoten und der neue Knoten auf NULL zeigen.

Löschvorgang

Das Löschen ist auch ein mehr als einstufiger Prozess. Wir werden mit bildlicher Darstellung lernen. Suchen Sie zunächst den zu entfernenden Zielknoten mithilfe von Suchalgorithmen.

Der linke (vorherige) Knoten des Zielknotens sollte jetzt auf den nächsten Knoten des Zielknotens zeigen -

LeftNode.next −> TargetNode.next;

Dadurch wird der Link entfernt, der auf den Zielknoten zeigte. Mit dem folgenden Code entfernen wir nun, auf was der Zielknoten zeigt.

TargetNode.next −> NULL;

Wir müssen den gelöschten Knoten verwenden. Wir können das im Speicher behalten, andernfalls können wir einfach den Speicher freigeben und den Zielknoten vollständig löschen.

Rückwärtsbetrieb

Diese Operation ist gründlich. Wir müssen den letzten Knoten machen, auf den der Kopfknoten zeigt, und die gesamte verknüpfte Liste umkehren.

Zuerst gehen wir zum Ende der Liste. Es sollte auf NULL zeigen. Jetzt werden wir es auf seinen vorherigen Knoten verweisen lassen -

Wir müssen sicherstellen, dass der letzte Knoten nicht der letzte Knoten ist. Wir haben also einen temporären Knoten, der aussieht wie der Kopfknoten, der auf den letzten Knoten zeigt. Jetzt lassen wir alle Knoten auf der linken Seite nacheinander auf ihre vorherigen Knoten zeigen.

Mit Ausnahme des Knotens (erster Knoten), auf den der Hauptknoten zeigt, sollten alle Knoten auf ihren Vorgänger zeigen und sie zu ihrem neuen Nachfolger machen. Der erste Knoten zeigt auf NULL.

Wir werden den Kopfknoten mithilfe des temporären Knotens auf den neuen ersten Knoten zeigen lassen.

Die verknüpfte Liste ist jetzt umgekehrt. Klicken Sie hier , um die Implementierung der verknüpften Liste in der Programmiersprache C anzuzeigen .