Programmierung · Konzepte · Datenstrukturen

Was ist eine verkettete Liste?

Eine verkettete Liste (Linked List) ist eine Datenstruktur, die eine Folge von Werten als Kette von Knoten speichert. Jeder Knoten enthält zwei Dinge: einen Wert und einen Zeiger (eine Referenz) auf den nächsten Knoten der Kette. Die Knoten liegen nicht Seite an Seite in einem einzigen Speicherblock wie die Elemente eines Arrays; stattdessen zeigt jeder einfach dorthin, wo der nächste liegt. Folge den Zeigern vom ersten Knoten, dem Kopf (Head), und du kannst die ganze Sequenz Glied für Glied durchlaufen.

Wie die Kette aufgebaut ist

Stell es dir wie eine Schatzsuche vor, bei der jeder Hinweis dir sagt, wo der nächste Hinweis zu finden ist. Die Liste hält eine Referenz auf den Kopfknoten. Der Zeiger dieses Knotens führt zum zweiten Knoten, dessen Zeiger zum dritten führt, und so weiter, bis der Zeiger eines Knotens leer ist (oft null oder None genannt), was das Ende der Liste markiert.

[ Wert | nächster ] -> [ Wert | nächster ] -> [ Wert | null ]

Da die Verbindungen nur Zeiger sind, können die Knoten irgendwo im Speicher liegen. Um die Liste zu vergrößern, reservierst du einen neuen Knoten und setzt einen Zeiger auf ihn; nichts anderes muss verschoben werden.

Einfach vs doppelt verkettet

Es gibt zwei gängige Formen, und der Unterschied liegt darin, wie viele Zeiger jeder Knoten trägt:

• Einfach verkettete Liste: jeder Knoten zeigt nur auf den nächsten Knoten. Du kannst in der Liste vorwärts gehen, aber nicht rückwärts, und du zahlst nur einen Zeiger pro Knoten.
• Doppelt verkettete Liste: jeder Knoten zeigt sowohl auf den nächsten als auch auf den vorherigen Knoten. Das erlaubt das Durchlaufen in beide Richtungen und erleichtert manche Löschungen, auf Kosten eines zusätzlichen Zeigers pro Knoten.

Verkettete Liste vs Array

Am klarsten versteht man eine verkettete Liste im Vergleich zu einem Array, denn sie treffen gegensätzliche Kompromisse. Ein Array speichert seine Elemente in einem zusammenhängenden Block mit einem Index, sodass es sofort zu jeder Position springen kann. Eine verkettete Liste gibt das auf, im Austausch für günstige Änderungen an den Enden.

• Wahlfreier Zugriff. Ein Array liest jedes Element per Index in O(1). Eine verkettete Liste hat keinen Index: um den zehnten Knoten zu erreichen, musst du beim Kopf beginnen und neun Zeigern folgen, also ist der Zugriff O(n).
• Einfügen und Löschen. Wenn du bereits eine Referenz auf den richtigen Knoten hältst, kann eine verkettete Liste dort einfügen oder löschen, indem sie ein paar Zeiger umverdrahtet, eine O(1)-Operation - ohne andere Elemente zu verschieben. In einem Array bedeutet Einfügen oder Löschen in der Mitte, die nachfolgenden Elemente zu verschieben, was O(n) ist.
• Speicher und Cache. Ein Array packt seine Werte zusammen, was dem CPU-Cache entgegenkommt. Eine verkettete Liste verstreut ihre Knoten und speichert einen zusätzlichen Zeiger pro Knoten, also verbraucht sie mehr Speicher pro Element und hat tendenziell eine schlechtere Cache-Lokalität.

Keine ist "besser"; sie passen zu unterschiedlichen Aufgaben. Wenn du schnelle Zugriffe per Position brauchst, gewinnt meist ein Array (oder ein dynamisches Array wie eine list oder ein vector). Wenn deine Daten stark in der Größe schwanken und du vor allem an den Enden hinzufügst oder entfernst, kann eine verkettete Liste gut passen. Für eine Auffrischung, wie diese Kosten beschrieben werden, siehe unseren Leitfaden zur Big-O-Notation.

Die Komplexitäten, ehrlich

Hier sind die Standardkosten für eine verkettete Liste, mit dem Vorbehalt, der immer wichtig ist:

• Zugriff und Suche: O(n). Es gibt keinen Index, also bedeutet einen Wert zu finden, die Kette vom Kopf aus zu durchlaufen.
• Einfügen und Löschen: O(1) wenn du bereits eine Referenz auf den Knoten hast (zum Beispiel direkt am Kopf). Wenn du die Stelle erst finden musst, ist diese Suche O(n), und die Gesamtsumme spiegelt beide Teile wider.

Diese Bedingung "wenn du den Knoten hast" ist der Teil, den Leute oft weglassen. Am Kopf einer einfach verketteten Liste einzufügen, ist wirklich konstante Zeit; nach einem Wert einzufügen, den du erst lokalisieren musst, ist es nicht.

Wo verkettete Listen verwendet werden

Verkettete Listen sind eher ein Baustein als ein alltäglicher Container. Sie sind eine natürliche Art, einen Stack oder eine Queue zu implementieren, da diese nur an den Enden hinzufügen und entfernen. Sie passen zu Situationen, in denen sich die Größe der Sammlung stark ändert und du keinen schnellen Zugriff per Position brauchst. Manche Strukturen verwenden intern verkettete Knoten; zum Beispiel ist eine gängige Art, Kollisionen in einer Hash Table zu behandeln, die kollidierenden Einträge in einer kleinen verketteten Liste pro Bucket zusammenzuketten.

Die Kompromisse

• Kein wahlfreier Zugriff. Eine beliebige Position zu erreichen kostet O(n), weil du den Zeigern vom Kopf aus folgst; es gibt keinen Index, mit dem man springen könnte.
• Zusätzlicher Speicher pro Element. Jeder Knoten speichert mindestens einen Zeiger (zwei bei einer doppelt verketteten Liste) zusätzlich zu seinem Wert.
• Schwächere Cache-Lokalität. Verstreute Knoten sind weniger cache-freundlich als ein zusammenhängendes Array, was das Durchlaufen in der Praxis langsamer machen kann, selbst wenn das Big O gleich ist.
• Günstige Änderungen an einem bekannten Knoten. Der Vorteil: an einem Knoten, den du bereits hältst, einzufügen oder zu entfernen, ist O(1), ohne den Rest der Daten zu verschieben.

FAQ

Was ist der Unterschied zwischen einer verketteten Liste und einem Array? Ein Array speichert Elemente in einem zusammenhängenden Block mit einem Index, liest also jede Position in O(1), aber Elemente zu verschieben, um in der Mitte einzufügen oder zu löschen, kostet O(n). Eine verkettete Liste speichert separate Knoten, die durch Zeiger verbunden sind, hat also keinen wahlfreien Zugriff (O(n), um eine Position zu erreichen), kann aber an einem bekannten Knoten in O(1) einfügen oder löschen.

Warum ist der Zugriff auf ein Element O(n)? Weil eine verkettete Liste keinen Index hat. Um den n-ten Knoten zu erreichen, beginnst du beim Kopf und folgst der Zeigerkette n-mal, also wächst der Aufwand mit der gewünschten Position.

Was ist der Unterschied zwischen einfach und doppelt verkettet? In einer einfach verketteten Liste zeigt jeder Knoten nur auf den nächsten Knoten, du kannst dich also nur vorwärts bewegen. In einer doppelt verketteten Liste zeigt jeder Knoten auch auf den vorherigen Knoten, du kannst dich also in beide Richtungen bewegen, auf Kosten eines zusätzlichen Zeigers pro Knoten.

Wann sollte ich eine verkettete Liste verwenden? Wenn sich die Größe der Sammlung stark ändert und du vor allem an den Enden hinzufügst oder entfernst, oder als Rückgrat eines Stacks oder einer Queue. Wenn du schnellen Zugriff per Position brauchst, ist ein Array meist die bessere Wahl.

Verwandte Guides: Hash Tables, Big-O-Notation, Rekursion.