Was ist eine verknüpfte Datenstruktur?
Eine verknüpfte Datenstruktur ist eine Sammlung von Daten, die in einem listenartigen Format angeordnet sind. Jedes Datum in der Liste wird als Knoten bezeichnet. Jeder Knoten ist mit dem nächsten in der Liste verbunden durch einen Verweis auf die Speicheradresse dieses nachfolgenden Knotens.Verlinkte Datenstrukturen werden anstelle eines Arrays verwendet, wenn die Anzahl der Knoten in einer Liste unbekannt ist oder im Verlauf der Liste wachsen oder schrumpfen kann Ausführung des Programms Die häufigste Art der verknüpften Datenstruktur wird als verknüpfte Liste bezeichnet.
Ein Knoten einer verknüpften Datenstruktur enthält im Allgemeinen zwei Informationen - eine Referenz auf die tatsächlich gespeicherten Daten und eine Referenz auf den nächsten Knoten in der Liste. Eine verknüpfte Liste wird schrittweise durchlaufen oder durchsucht Es gibt keine Möglichkeit, Informationen in einer verknüpften Liste zu finden, ohne die Knoten nacheinander von Anfang bis Ende zu durchlaufen.
Die meisten verknüpften Datenstrukturen belegen während der Programmausführung so wenig Speicher wie möglich. Wenn eine verknüpfte Liste mit nur einem Knoten erstellt und keine weiteren Knoten hinzugefügt werden, nimmt diese Liste den Speicherplatz ein Speicher, der nur für einen Knoten benötigt wird Dies steht in starkem Gegensatz zu einer Array-Datenstruktur, bei der die Größe des gesamten Arrays zu Beginn des Programms deklariert und zugewiesen werden muss und nicht geändert werden kann .
Verknüpfte Listen zahlen sich für die effiziente Nutzung der Speicherressourcen aus, da sie mehr Rechenleistung benötigen.Wenn ein bestimmtes Datenelement in einer verknüpften Liste gefunden werden soll, muss jedes Mal die gesamte Liste durchlaufen werden Das Entfernen oder Neuanordnen von Daten in einer verknüpften Liste kann auch rechenintensiver sein als das Verwalten eines Arrays, in dem Elemente einfach ausgetauscht werden können.
Eine verknüpfte Datenstruktur muss nicht nur eine Referenz zum nächsten Knoten haben. Einige verknüpfte Listen haben zwei Knotenreferenzen, eine zum nächsten Knoten in der Liste und eine zum vorherigen Knoten, die als doppelt verknüpfte Listen bezeichnet werden Liste in beide Richtungen viel schneller, jedoch auf Kosten der erhöhten Speichernutzung für die Datenstruktur.
Verknüpfte Listen können drei oder mehr Verweise auf andere Knoten in der Liste enthalten, wodurch eine baumähnliche Struktur erstellt wird, bei der ganze Zweige von Knoten aus einem einzigen Knoten hervorgehen Strukturen werden als mehrfach verknüpfte Listen bezeichnet, wobei mehrfach verknüpfte Listen insbesondere für komplexe Sortieralgorithmen zur Strukturierung von Daten nützlich sind und Suchbäume vor allem aufgrund der Verwendung verknüpfter Datenstrukturen möglich sind um mehrere Zweige mit variabler Länge zu erstellen.