Verkettete Listen

Das Prinzip der Schnitzeljagd

Stell dir eine Schnitzeljagd vor. Du hast nicht alle Hinweise auf einmal in der Hand. Stattdessen findest du an jedem Ort einen Zettel. Auf diesem Zettel steht eine Aufgabe (die Daten) und der genaue Ort, wo der nächste Zettel versteckt ist (der Verweis oder Pointer). Genau so funktioniert eine verkettete Liste (Linked List).

Im Gegensatz zu einem Array, wo alle Elemente wie in einem Eierkarton fest nebeneinander im Speicher liegen, können die Elemente einer verketteten Liste wild verstreut im Arbeitsspeicher liegen. Der Zusammenhalt entsteht nur dadurch, dass jedes Element weiß, wo das nächste zu finden ist. Ein einzelnes Element in dieser Liste nennen wir Knoten (Node). Jeder Knoten besteht aus zwei Teilen:

1. Daten (Payload): Der eigentliche Wert, den wir speichern wollen (z. B. eine Zahl, ein Text oder ein Objekt).
2. Next-Pointer: Eine Adresse, die auf den nächsten Knoten in der Liste zeigt.

Das letzte Element der Liste zeigt auf NULL (oder None), um zu signalisieren: "Hier ist die Liste zu Ende". Dies ermöglicht eine dynamische Speicherallokation: Die Liste kann wachsen und schrumpfen, solange noch irgendwo im Speicher Platz für einen weiteren einzelnen Knoten ist.

Einfach vs. doppelt verkettete Listen

Es gibt zwei Hauptarten von verketteten Listen, die sich in ihrer Flexibilität und ihrem Speicherbedarf unterscheiden:

• Einfach verkettete Liste (Singly Linked List):
  • Jeder Knoten kennt nur seinen Nachfolger.
  • Analogie: Eine Einbahnstraße. Du kommst von Haus A nach Haus B, aber nicht direkt zurück.
  • Vorteil: Geringerer Speicherbedarf, da nur ein Zeiger pro Knoten gespeichert werden muss.
  • Nachteil: Du kannst die Liste nur in eine Richtung durchlaufen. Wenn du am Ende bist, kommst du nicht einfach einen Schritt zurück.
• Doppelt verkettete Liste (Doubly Linked List):
  • Jeder Knoten kennt seinen Nachfolger und seinen Vorgänger. Er hat also einen Next-Pointer und einen Previous-Pointer.
  • Analogie: Eine normale Straße. Du kannst vorwärts und rückwärts gehen.
  • Vorteil: Du kannst in beide Richtungen navigieren, was z. B. das Löschen von Elementen vereinfacht, da du den Vorgänger kennst.
  • Nachteil: Höherer Speicherbedarf, da zwei Zeiger pro Knoten verwaltet werden müssen.

class Node:
    def __init__(self, data):
        self.data = data      # Die Nutzdaten
        self.next = None      # Zeiger auf den Nachfolger
        # self.prev = None    # <-- Nur bei doppelt verketteten Listen nötig

Zugriff und Speicher: Der Preis der Flexibilität

• Zugriffsgeschwindigkeit: Arrays bieten direkten Zugriff (Random Access). Da alle Elemente hintereinander liegen, kann der Computer die Adresse des 10. Elements sofort berechnen (O(1)). Bei einer verketteten Liste ist nur sequentieller Zugriff möglich. Um das 10. Element zu finden, musst du beim ersten anfangen und dich neunmal von Zeiger zu Zeiger hangeln (O(n)). Das ist wie bei einer Musikkassette: Um zum letzten Lied zu kommen, musst du das ganze Band vorspulen.
• Speicherverwaltung: Ein Array ist statisch (oder schwerfällig dynamisch). Es benötigt einen großen, zusammenhängenden Block. Ist der Block voll, muss oft das ganze Array in einen größeren Bereich kopiert werden. Die verkettete Liste ist dynamisch. Sie nutzt den Speicher effizienter aus, da sie Lücken im Arbeitsspeicher füllen kann, benötigt aber pro Element etwas mehr Platz für die Zeiger.

Einfügen und Löschen: Die Stärke der Liste

• Array: Wenn du ein Element in die Mitte eines Arrays einfügen willst, müssen alle nachfolgenden Elemente verschoben werden, um Platz zu machen. Das kostet viel Rechenzeit.
• Verkettete Liste: Um ein Element einzufügen, musst du nur die Zeiger "umbiegen". Das neue Element zeigt auf den Nachfolger, und der Vorgänger zeigt auf das neue Element. Die anderen Elemente bleiben unberührt an ihrem Platz im Speicher. Das geht extrem schnell (O(1)), vorausgesetzt, du hast die richtige Stelle bereits gefunden. Das Löschen funktioniert analog: Der Zeiger des Vorgängers wird einfach auf den Nachfolger des zu löschenden Elements gesetzt.

# --- Szenario A: Array (Liste in Python) ---
# Problem: Alle Elemente müssen verschoben werden!
# [2, 3, 4] -> [ , 2, 3, 4] -> [1, 2, 3, 4]
my_array = [2, 3, 4]
my_array.insert(0, 1) # Einfügen am Anfang
print(my_array)  # Ausgabe: [1, 2, 3, 4]

# --- Szenario B: Verkettete Liste ---
# Vorteil: Nur Zeiger ändern, kein Verschieben nötig!
class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, data):
        new_node = Node(data)
        
        # 1. Der neue Knoten zeigt auf den bisherigen ersten Knoten
        new_node.next = self.head
        
        # 2. Der Kopf der Liste ist jetzt der neue Knoten
        self.head = new_node