Verlinkte Liste ist eine lineare Datenstruktur, in der Elemente nicht an einer zusammenhängenden Stelle gespeichert, sondern mithilfe von Zeigern verknüpft sind. Die verknüpfte Liste bildet eine Reihe verbundener Knoten, wobei jeder Knoten die Daten und die Adresse des nächsten Knotens speichert.

Knotenstruktur: Ein Knoten in einer verknüpften Liste besteht normalerweise aus zwei Komponenten:
Daten: Es enthält den tatsächlichen Wert oder die tatsächlichen Daten, die dem Knoten zugeordnet sind.
Nächster Hinweis: Es speichert die Speicheradresse (Referenz) des nächsten Knotens in der Sequenz.
Kopf und Schwanz: Der Zugriff auf die verknüpfte Liste erfolgt über den Kopfknoten, der auf den ersten Knoten in der Liste verweist. Der letzte Knoten in der Liste zeigt auf NULL oder nullptr und gibt damit das Ende der Liste an. Dieser Knoten wird als Endknoten bezeichnet.

Warum wird eine Datenstruktur für verknüpfte Listen benötigt?

Hier sind einige Vorteile einer verlinkten Liste, die unten aufgeführt sind. Sie werden Ihnen helfen zu verstehen, warum es notwendig ist, sie zu kennen.

• Dynamische Datenstruktur: Die Größe des Speichers kann zur Laufzeit basierend auf dem Einfügen oder Löschen des Vorgangs zugewiesen oder freigegeben werden.
• Einfaches Einfügen/Löschen: Das Einfügen und Löschen von Elementen ist einfacher als bei Arrays, da nach dem Einfügen und Löschen keine Elemente verschoben werden müssen, sondern lediglich die Adresse aktualisiert werden muss.
• Effiziente Speichernutzung: Wie wir wissen, handelt es sich bei der verknüpften Liste um eine dynamische Datenstruktur, deren Größe je nach Anforderung zunimmt oder abnimmt, sodass eine Speicherverschwendung vermieden wird.
• Implementierung: Mithilfe einer verknüpften Liste können verschiedene erweiterte Datenstrukturen implementiert werden, z. B. ein Stapel, eine Warteschlange, ein Diagramm, Hash-Maps usw.

Beispiel:

Wenn wir in einem System eine sortierte Liste von IDs in einem Array verwalten, ist id[] = [1000, 1010, 1050, 2000, 2040].

Wenn wir eine neue ID 1005 einfügen möchten, müssen wir zur Beibehaltung der sortierten Reihenfolge alle Elemente nach 1000 verschieben (außer 1000).

Auch bei Arrays ist das Löschen teuer, es sei denn, es werden spezielle Techniken eingesetzt. Um beispielsweise 1010 in id[] zu löschen, muss alles nach 1010 verschoben werden, da so viel Arbeit geleistet wird, was sich auf die Effizienz des Codes auswirkt.

Arten von verknüpften Listen :

Es gibt hauptsächlich drei Arten von verknüpften Listen:

1. Einfach verknüpfte Liste
2. Doppelt verknüpfte Liste
3. Zirkuläre verknüpfte Liste

1. Einfach verknüpfte Liste :

In einer einfach verknüpften Liste enthält jeder Knoten einen Verweis auf den nächsten Knoten in der Sequenz. Das Durchlaufen einer einfach verknüpften Liste erfolgt in Vorwärtsrichtung.

Einfach verknüpfte Liste

2. Doppelt verknüpfte Liste :

In einer doppelt verknüpften Liste enthält jeder Knoten Verweise sowohl auf den nächsten als auch auf den vorherigen Knoten. Dies ermöglicht die Durchquerung sowohl in Vorwärts- als auch in Rückwärtsrichtung, erfordert jedoch zusätzlichen Speicher für die Rückwärtsreferenz.

Doppelt verknüpfte Liste

3. Zirkuläre verknüpfte Liste :

In einer kreisförmigen verknüpften Liste zeigt der letzte Knoten zurück auf den Kopfknoten, wodurch eine kreisförmige Struktur entsteht. Es kann entweder einfach oder doppelt verknüpft sein.

vergleichbares Java

Zirkuläre verknüpfte Liste

Operationen an verknüpften Listen

1. Einfügen : Das Hinzufügen eines neuen Knotens zu einer verknüpften Liste erfordert das Anpassen der Zeiger der vorhandenen Knoten, um die richtige Reihenfolge beizubehalten. Das Einfügen kann am Anfang, am Ende oder an einer beliebigen Position innerhalb der Liste erfolgen
2. Streichung : Das Entfernen eines Knotens aus einer verknüpften Liste erfordert das Anpassen der Zeiger der benachbarten Knoten, um die Lücke zu schließen, die der gelöschte Knoten hinterlassen hat. Das Löschen kann am Anfang, am Ende oder an einer beliebigen Position innerhalb der Liste erfolgen.
3. Suchen : Die Suche nach einem bestimmten Wert in einer verknüpften Liste umfasst das Durchlaufen der Liste vom Kopfknoten aus, bis der Wert gefunden oder das Ende der Liste erreicht wird.

Komplexitätsanalyse einer verknüpften Liste :

• Zeitkomplexität: O(n)
• Hilfsraum: O(n)

Vorteile verknüpfter Listen

• Dynamische Größe: Verknüpfte Listen können dynamisch wachsen oder schrumpfen, da die Speicherzuweisung zur Laufzeit erfolgt.
• Einfügen und Löschen: Das Hinzufügen oder Entfernen von Elementen zu einer verknüpften Liste ist effizient, insbesondere bei großen Listen.
• Flexibilität: Verknüpfte Listen können einfach neu organisiert und geändert werden, ohne dass ein zusammenhängender Speicherblock erforderlich ist.

Nachteile verknüpfter Listen

• Direktzugriff: Im Gegensatz zu Arrays erlauben verknüpfte Listen keinen direkten Zugriff auf Elemente über den Index. Um einen bestimmten Knoten zu erreichen, ist eine Durchquerung erforderlich.
• Zusätzlicher Speicher: Verknüpfte Listen erfordern im Vergleich zu Arrays zusätzlichen Speicher zum Speichern der Zeiger.

Abschluss:

Verknüpfte Listen sind vielseitige Datenstrukturen, die eine dynamische Speicherzuweisung und effiziente Einfüge- und Löschvorgänge ermöglichen. Das Verständnis der Grundlagen verknüpfter Listen ist für jeden Programmierer oder Informatikbegeisterten von entscheidender Bedeutung. Mit diesem Wissen können Sie verknüpfte Listen implementieren, um verschiedene Probleme zu lösen und Ihr Verständnis von Datenstrukturen und Algorithmen zu erweitern.