Wie sind verkettete Listen aufgebaut?
Das Prinzip der Schnitzeljagd im Arbeitsspeicher
Stell dir eine Schnitzeljagd vor: Du bekommst nicht alle Hinweise auf einmal. An jedem Versteck findest du einen Zettel mit einer Information und dem genauen Ort des nächsten Verstecks. Genau so funktioniert das Konzept der verketteten Liste (Linked List). Anstatt Daten streng nebeneinander in einem festen Block im Arbeitsspeicher abzulegen, können sie wild verstreut sein. Der Zusammenhalt entsteht ausschließlich dadurch, dass jedes Element weiß, wo exakt das nächste Element liegt.
Die Struktur: Knoten und Zeiger
Ein einzelnes Element in dieser Datenstruktur nennen wir Knoten (Node). Jeder Knoten besteht zwingend aus zwei Teilen:
- Daten (Payload): Der eigentliche Wert, den du speichern möchtest (z. B. eine Zahl, ein Text oder ein komplexes Objekt).
- Zeiger (Pointer): Eine Speicheradresse, die auf den nächsten Knoten verweist.
Der letzte Knoten zeigt auf einen Nullwert (z. B. None in Python), was das Ende der Liste markiert. Diese Struktur ermöglicht eine dynamische Speicherallokation: Die Liste kann zur Laufzeit beliebig wachsen oder schrumpfen, da das Betriebssystem für jeden neuen Knoten einfach irgendwo einen freien Speicherplatz sucht und ihn per Zeiger anbindet.
Einfach vs. doppelt verkettete Listen
Je nach Anforderung gibt es zwei Hauptarten von verketteten Listen, die sich in ihrer Navigationsrichtung und ihrem Speicherbedarf unterscheiden:
- Einfach verkettete Liste (Singly Linked List): Jeder Knoten hat nur einen Zeiger auf seinen Nachfolger. Du kannst die Liste nur vorwärts durchlaufen. Der große Vorteil ist der geringere Speicherbedarf, da pro Knoten nur eine Adresse gespeichert werden muss.
- Doppelt verkettete Liste (Doubly Linked List): Jeder Knoten besitzt zusätzlich einen Zeiger auf seinen Vorgänger (
Previous). Du kannst also vorwärts und rückwärts navigieren. Der Preis für diese Flexibilität ist ein höherer Speicherbedarf, da pro Knoten zwei Speicheradressen (Vorgänger und Nachfolger) verwaltet werden müssen.
Wann wählst du eine verkettete Liste statt eines Arrays?
Speicherverwaltung: Dynamisch vs. Statisch
Ein Array benötigt einen zusammenhängenden Block im Arbeitsspeicher. Wenn du ein Array anlegst, muss der Computer am Stück Platz dafür reservieren (statische Speicherverwaltung). Ist der Block voll, muss oft ein komplett neuer, größerer Block gesucht und alles dorthin kopiert werden. Eine verkettete Liste nutzt hingegen dynamische Speicherverwaltung. Sie füllt einfach Lücken im Arbeitsspeicher auf. Jeder neue Knoten wird dort abgelegt, wo gerade Platz ist. Das nutzt den Speicher flexibler aus, selbst wenn dieser stark fragmentiert ist. Aus deinem Vorwissen zu Stacks und Queues weißt du bereits, dass diese Flexibilität ideal ist, um dynamisch wachsende Warteschlangen effizient zu implementieren.
Zugriffsgeschwindigkeit: Direkt vs. Sequentiell
Wenn du das 50. Element lesen willst, ist das Array unschlagbar. Da alle Elemente direkt hintereinanderliegen, kann der Computer die Speicheradresse sofort mathematisch berechnen. Das nennt man direkten Zugriff (Random Access). Bei einer verketteten Liste ist nur sequentieller Zugriff möglich. Um das 50. Element zu finden, musst du zwingend beim ersten Knoten starten und dich 49-mal von Zeiger zu Zeiger hangeln. Das kostet bei großen Listen deutlich mehr Zeit.
Einfügen und Löschen: Die Stärke der Verkettung
Willst du ein neues Element ganz an den Anfang eines Arrays setzen, müssen alle bestehenden Elemente im Speicher um eine Position nach hinten verschoben werden. Das ist extrem rechenaufwendig und ineffizient. Bei einer verketteten Liste ist das Einfügen oder Löschen hingegen hocheffizient. Du musst keine Daten verschieben, sondern lediglich die Zeiger aktualisieren.
# Beispiel: Hocheffizientes Einfügen am Anfang einer einfach verketteten Liste
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None # Startpunkt der Liste
def prepend(self, data):
neuer_knoten = Node(data)
# 1. Der neue Knoten zeigt auf den bisherigen Startknoten
neuer_knoten.next = self.head
# 2. Der neue Knoten wird zum neuen Startknoten der Liste
self.head = neuer_knoten
Teste dein Wissen
Du analysierst den Arbeitsspeicher einer Anwendung. Wie werden die Elemente einer verketteten Liste im Gegensatz zu einem Array im Speicher abgelegt?