Linked List

Eine Linked List (verkettete Liste) ist eine dynamische Datenstruktur, bei der Elemente nicht zusammenhängend im Speicher liegen, sondern über Zeiger (Pointer) miteinander verbunden sind. Jedes Element, auch Node (Knoten) genannt, besteht aus den eigentlichen Daten und mindestens einem Verweis auf das nächste Element. Anders als bei Arrays ermöglicht diese Struktur effizientes Einfügen und Löschen von Elementen an beliebigen Positionen.

Aufbau einer Linked List

Eine Linked List besteht aus einzelnen Knoten, die durch Zeiger miteinander verbunden sind. Der erste Knoten wird als Head bezeichnet und dient als Einstiegspunkt in die Liste. Der letzte Knoten zeigt auf null (oder None in Python), um das Ende der Liste zu markieren.

Jeder Knoten enthält zwei wesentliche Komponenten:

• Data: Der eigentliche Wert oder die Nutzdaten des Knotens
• Next: Ein Zeiger auf den nächsten Knoten in der Liste

Die folgende Implementierung zeigt den grundlegenden Aufbau eines Knotens und einer einfach verketteten Liste in Java:

// Definition eines Knotens
class Node {
    int data;       // Nutzdaten
    Node next;      // Zeiger auf nächsten Knoten
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Einfache Linked List
class LinkedList {
    Node head;      // Einstiegspunkt
    
    public LinkedList() {
        this.head = null;
    }
}

Arten von verketteten Listen

Je nach Anwendungsfall gibt es verschiedene Varianten von Linked Lists, die sich in ihrer Struktur und ihren Möglichkeiten unterscheiden.

Einfach verkettete Liste (Singly Linked List)

Bei der einfach verketteten Liste enthält jeder Knoten nur einen Zeiger auf den nächsten Knoten. Du kannst die Liste daher nur in eine Richtung durchlaufen - vom Head zum Ende. Diese Variante benötigt weniger Speicher, da pro Knoten nur ein Zeiger gespeichert wird.

Doppelt verkettete Liste (Doubly Linked List)

Die doppelt verkettete Liste erweitert jeden Knoten um einen zusätzlichen Zeiger auf den vorherigen Knoten. Dadurch ist eine Navigation in beide Richtungen möglich. Der Nachteil: Jeder Knoten benötigt mehr Speicher, und bei Einfüge- und Löschoperationen müssen zwei Zeiger aktualisiert werden.

// Knoten für doppelt verkettete Liste
class DoublyNode {
    int data;
    DoublyNode prev;    // Zeiger auf vorherigen Knoten
    DoublyNode next;    // Zeiger auf nächsten Knoten
    
    public DoublyNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

Zirkuläre verkettete Liste (Circular Linked List)

Bei der zirkulären Liste zeigt der letzte Knoten nicht auf null, sondern zurück auf den Head. Dadurch entsteht ein geschlossener Ring ohne definiertes Ende. Diese Struktur eignet sich beispielsweise für Round-Robin-Scheduling oder Playlist-Wiederholungen.

Grundoperationen

Die wichtigsten Operationen auf Linked Lists sind das Einfügen, Löschen und Suchen von Elementen. Anders als bei Arrays erfordern diese Operationen keine Verschiebung von Elementen im Speicher.

Einfügen am Anfang

Das Einfügen am Anfang der Liste ist besonders effizient. Du erstellst einen neuen Knoten, setzt dessen Next-Zeiger auf den aktuellen Head und machst den neuen Knoten zum neuen Head.

public void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    newNode.next = head;    // Neuer Knoten zeigt auf bisherigen Head
    head = newNode;         // Neuer Knoten wird zum Head
}

Einfügen am Ende

Beim Einfügen am Ende musst du zunächst die gesamte Liste durchlaufen, um den letzten Knoten zu finden. Dann setzt du dessen Next-Zeiger auf den neuen Knoten.

public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    
    if (head == null) {
        head = newNode;
        return;
    }
    
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
}

Löschen eines Elements

Beim Löschen suchst du den Knoten mit dem gewünschten Wert und passt die Zeiger so an, dass der zu löschende Knoten übersprungen wird. Der Garbage Collector (bei Sprachen wie Java) kümmert sich dann automatisch um die Speicherfreigabe.

public void delete(int data) {
    if (head == null) return;
    
    // Fall: Head soll gelöscht werden
    if (head.data == data) {
        head = head.next;
        return;
    }
    
    Node current = head;
    while (current.next != null && current.next.data != data) {
        current = current.next;
    }
    
    if (current.next != null) {
        current.next = current.next.next;  // Knoten überspringen
    }
}

Zeitkomplexität

Die Zeitkomplexität der verschiedenen Operationen unterscheidet sich je nach Position und Art der Operation. Ein Verständnis dieser Komplexitäten hilft dir bei der Auswahl der richtigen Datenstruktur für dein Problem.

Der Speicherverbrauch liegt bei O(n), wobei jeder Knoten zusätzlich zum Datenwert auch Speicher für die Zeiger benötigt. Bei einer doppelt verketteten Liste verdoppelt sich der Zeiger-Overhead entsprechend.

Vergleich: Linked List vs. Array

Beide Datenstrukturen haben ihre Berechtigung und eignen sich für unterschiedliche Anwendungsfälle. Die Wahl hängt von den häufigsten Operationen ab, die du auf den Daten ausführen musst.

Verwende eine Linked List, wenn du häufig Elemente einfügst oder löschst und die Größe der Datenstruktur stark variiert. Arrays sind besser geeignet, wenn du oft auf Elemente per Index zugreifst und die Größe weitgehend konstant bleibt.

Praktische Anwendungen

Linked Lists bilden die Grundlage für viele andere Datenstrukturen und finden in zahlreichen Bereichen der Softwareentwicklung Anwendung:

• Stacks und Queues: Beide Datenstrukturen lassen sich effizient mit Linked Lists implementieren
• Undo-Funktionalität: Editoren speichern Aktionen in einer Liste, um sie rückgängig machen zu können
• Browser-History: Vor- und Zurück-Navigation nutzt eine doppelt verkettete Liste
• Hash-Tabellen: Kollisionsbehandlung durch Verkettung (Chaining)
• Speicherverwaltung: Betriebssysteme verwalten freie Speicherblöcke in Listen
• Musik-Player: Playlists mit Vor-/Zurück-Navigation und Wiederholung

Linked Lists in Standardbibliotheken

Die meisten Programmiersprachen bieten fertige Implementierungen von Linked Lists in ihren Standardbibliotheken. Diese sind optimiert und getestet - du musst also nicht jedes Mal eine eigene Implementierung schreiben.

// Java: LinkedList aus java.util
import java.util.LinkedList;

LinkedList<String> liste = new LinkedList<>();
liste.addFirst("Erster");
liste.addLast("Letzter");
liste.add(1, "Mitte");

String erstes = liste.getFirst();
liste.removeFirst();

# Python: collections.deque (doppelt verkettet)
from collections import deque

liste = deque()
liste.appendleft("Erster")
liste.append("Letzter")

erstes = liste.popleft()
letztes = liste.pop()

Linked Lists in der Praxis

Als Fachinformatiker für Anwendungsentwicklung begegnest du Linked Lists vor allem in der theoretischen Informatik und bei der Implementierung anderer Datenstrukturen. Im Alltag verwendest du meist die Standardbibliotheken deiner Programmiersprache. Das Verständnis der Funktionsweise hilft dir jedoch dabei, die richtige Datenstruktur für dein Problem auszuwählen und Performance-Probleme zu erkennen.

Quellen und weiterführende Links

• Oracle Java LinkedList Documentation
• GeeksforGeeks: Linked List Data Structure
• Python collections.deque Documentation
• Visualgo: Linked List Visualization