Liste

Einführung

In der Informatik ist die verkettete Liste (englisch Linked List) oder kurz Liste eine fundamentale dynamische Datenstruktur. Sie dient der sequenziellen Speicherung von logisch zusammengehörigen, aber physisch im Speicher verstreuten Datenobjekten[cite: 3].

Im Gegensatz zu statischen Datenstrukturen (wie dem Array) müssen die einzelnen Elemente einer Liste im Arbeitsspeicher nicht direkt hintereinanderliegen. Die logische Reihenfolge wird stattdessen durch Zeiger (Referenzen) realisiert, die von einem Listenelement zum nächsten weisen. Ein einzelnes Element der Liste wird als Knoten (englisch Node) bezeichnet. Jeder Knoten kapselt die eigentlichen Nutzdaten (den Inhalt) und besitzt mindestens einen Zeiger auf seinen direkten Nachfolger. Man unterscheidet hierbei zwischen unidirektionalen (einfach verketteten) und bidirektionalen (doppelt verketteten) Listen.

Objekte der abstrakten Datenstruktur List verwalten beliebig viele, linear angeordnete Objekte. Das wesentliche Konzept der im nordrhein-westfälischen Abitur verwendeten Listenstruktur ist das aktuelle Objekt (Current): Auf höchstens ein Listenobjekt kann zu einem gegebenen Zeitpunkt direkt lesend oder schreibend zugegriffen werden. Wenn eine Liste leer ist, der Durchlauf das Ende überschritten hat oder das aktuelle Objekt gelöscht wurde, ist die Referenz auf das aktuelle Objekt ungültig (null). Das Setzen des aktuellen Objekts erfolgt über definierte Navigationsmethoden.

Vorteile und Nachteile gegenüber einem Array

Vorteil: Das Einfügen und Löschen von Elementen an der aktuellen Position ist in konstanter Zeit ([math]\displaystyle{ \mathcal{O}(1) }[/math]) möglich, da lediglich Zeiger umgebogen werden müssen. Es ist nicht notwendig, nachfolgende Elemente im Speicher zu verschieben. Zudem wächst die Liste dynamisch mit ihren Anforderungen (keine feste Größenbegrenzung).
Nachteil: Die Liste verbraucht mehr Speicherplatz (Overhead durch die Speicherung der Referenzzeiger). Zudem ist kein direkter Indexzugriff möglich; um das [math]\displaystyle{ n }[/math]-te Element zu finden, muss die Liste von vorne durchlaufen werden.

Visualisierung

Die nachfolgende Abbildung veranschaulicht eine einfach verkettete (unidirektionale) Liste. Das eigentliche Listen-Objekt (hier als Dreieck dargestellt) verwaltet den Zustand der Liste über zwei interne Zeiger: einen Referenzzeiger auf das allererste Element (Startknoten) und einen Referenzzeiger auf das aktuell fokussierte Element (Aktueller Knoten).

Aufbau und Spezifikation (API)

Im Kontext der objektorientierten Anwendungsentwicklung und in den landesweiten Vorgaben für das Zentralabitur wird die Liste über eine klar definierte Schnittstelle abstrahiert. Eine normgerechte Klasse List muss über die folgenden Methoden und Konstruktoren verfügen:

Konstruktor

List()
- Eine leere Liste wird erzeugt.

Navigations- und Prüfmethoden

boolean isEmpty()
- Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.
boolean hasAccess()
- Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie false.
void next()
- Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt folgende Objekt zum neuen aktuellen Objekt. Andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt mehr (hasAccess() liefert den Wert false).
void toFirst()
- Falls die Liste nicht leer ist, wird das erste Objekt der Liste zum aktuellen Objekt. Ist die Liste leer, geschieht nichts.
void toLast()
- Falls die Liste nicht leer ist, wird das letzte Objekt der Liste zum aktuellen Objekt. Ist die Liste leer, geschieht nichts.

Methoden zur Datenmanipulation

Object getObject()
- Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird dieses zurückgegeben. Andernfalls gibt die Anfrage den Wert null zurück.
void setObject(Object pObject)
- Falls es ein aktuelles Objekt gibt und pObject ungleich null ist, wird das aktuelle Objekt durch pObject ersetzt. Sonst bleibt die Liste unverändert.
void append(Object pObject)
- Ein neues Objekt pObject wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls pObject gleich null ist, bleibt die Liste unverändert.
void insert(Object pObject)
- Falls es ein aktuelles Objekt gibt, wird ein neues Objekt vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist, wird pObject in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt und die Liste nicht leer ist, oder pObject gleich null ist, bleibt die Liste unverändert.
void concat(List pList)
- Die Liste pList wird an die aufrufende Liste angehängt. Anschließend wird pList zu einer leeren Liste. Das aktuelle Objekt bleibt unverändert. Falls pList null oder bereits leer ist, bleibt die Liste unverändert.
void remove()
- Falls es ein aktuelles Objekt gibt, wird dieses gelöscht und das Objekt hinter dem gelöschten Objekt wird zum neuen aktuellen Objekt. Wird das letzte Objekt der Liste gelöscht, gibt es danach kein aktuelles Objekt mehr. Wenn die Liste leer ist oder es kein aktuelles Objekt gibt, bleibt die Liste unverändert.

Laufzeitanalyse (Komplexität)

Im Zuge der Softwareentwicklung ist die Auswahl der richtigen Datenstruktur hinsichtlich ihrer Effizienz kritisch[cite: 4]. Bei einer idealen, objektorientierten Implementierung einer Liste (mit Referenzen auf den ersten Knoten, den letzten Knoten und den aktuellen Knoten) ergeben sich gemäß der Landau-Notation folgende Laufzeitkomplexitäten:

Operation	1. Best-Case	2. Average-Case	3. Worst-Case
`append(Object pObject)`	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]
`insert(Object pObject)`	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(n) }[/math]	[math]\displaystyle{ \mathcal{O}(n) }[/math]
`remove()`	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(n) }[/math]	[math]\displaystyle{ \mathcal{O}(n) }[/math]
Iteration (von vorne bis `n`)	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(n) }[/math]	[math]\displaystyle{ \mathcal{O}(n) }[/math]

Erläuterung: Da in einer einfach verketteten Liste nur vorwärts navigiert werden kann, erfordern insert() und remove() das Anpassen der Zeiger des Vorgängerknotens. Um den Vorgänger des aktuellen Knotens zu finden, muss die Liste im Average- und Worst-Case von vorne durchlaufen werden.

Implementierungsbeispiel (Java)

Nachfolgend ist das prinzipielle Grundgerüst einer Listen-Implementierung auf Basis einer Knotenklasse (ListNode) dargestellt, wie es im Leistungskurs oder der Fachinformatik-Ausbildung entwickelt wird, um dynamische Datenstrukturen und das Kapselungsprinzip informationstechnisch zu fundieren[cite: 3].

public class List {
    
    // Innere Knoten-Klasse
    private class ListNode {
        Object content;
        ListNode nextNode;

        public ListNode(Object pContent) {
            content = pContent;
            nextNode = null;
        }
    }

    // Zeiger auf wesentliche Elemente der Liste
    private ListNode first;
    private ListNode last;
    private ListNode current;

    /**
     * Konstruktor
     */
    public List() {
        first = null;
        last = null;
        current = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public boolean hasAccess() {
        return current != null;
    }

    public void next() {
        if (this.hasAccess()) {
            current = current.nextNode;
        }
    }

    public void append(Object pObject) {
        if (pObject != null) {
            ListNode newNode = new ListNode(pObject);
            if (this.isEmpty()) {
                first = newNode;
                last = newNode;
            } else {
                last.nextNode = newNode;
                last = newNode;
            }
        }
    }
    
    public Object getObject() {
        if (this.hasAccess()) {
            return current.content;
        }
        return null;
    }
    
    // ... weitere Methoden (insert, remove, toFirst, etc.)
}