Verkettete Listen (Linked Lists)

Verkettete Listen erlauben die Verwaltung von mehreren gelichartigen Elementen ohne Arrays, wenn Konzepte für komplexe Datentypen (mehrere unterschiedliche Attribute) wie Objekte, Struct (Sprache C) o.ä. verfügbar sind.

Die darin auftretenden Ansätze sind auch Ausgangsbasis für wichtige Datenstrukturen wie Binäre Bäume etc.

Das Konzept besteht im Prinzip darin, eine Klasse Node zu definieren, die einerseits eine "Nutzlast" (Payload) hat, die das zu verwaltende Element enthält (bzw. eine Referenz darauf) und weiters eine Referenz auf den "Nachfolger". Man kann sich das wie eine Menschenkette im Nebel vorstellen, die wo man eine "Verkettung" durch Halten der Schulter des Vordermannes herstellt.

Eine zweite Klasse (oft im Namen "LinkedList") repräsentiert die gesamte verkettete Liste. Sie enthält die Methoden für die Funktionalitäten und den Einstigspunkt in die Liste: eine Referenz zum ersten "Node". Falls die Liste leer ist, zeigt diese Referenz auf null.

Weiters sind darin die Funktionalitäten (Methoden) enthalten, die z.B. Elemente hinzufügen (Spezialfall 1. Element!), entfernen, den Index eines Elements feststellen, das Element an einem bestimmten Indx zurückliefern, Anzahl der enthaltenen Elemente (Listen-Länge) zurückliefern, etc., sodass die üblichen Nutzungen analog zu einem Array vorhanden sind.

Um ein bestimmtes Element zu erreichen, muss IMMER vom Node-0 (Attribut der LinkedList-Kalsse) ausgegangen werden und jeder Node nach seinem Nachfolger (next()) gefragt werden. Wenn hier null zurückgeliefert wird, ist man am Ende angelangt.

Hier eine rudimentäre Implementation einer LinkedList, wo die Payload ein String ist (völlig analog für andere Payloads wie Person, etc.):

public class StringNode
{
    private String payload;
    private StringNode next;

    public StringNode(String payload) {
        this.payload = payload;
    }
    public StringNode(String payload, StringNode next) {
        this.payload = payload;
        this.next = next;
    }
    public void setPayload(String payload) {
        this.payload = payload;
    }
    public void setNext(StringNode next) {
        this.next = next;
    }
    public String getPayload() {
        return payload;
    }
    public StringNode getNext() {
        return next;
    }
    public boolean isLast() {
        return next == null;
    }
}


public class StringLinkedList
{
    private StringNode node0;
    private String title;

    public StringLinkedList() {
        // empty for now
    }
    public int length() {
        StringNode current = this.node0;
        int len = 0;
        while (current != null) {
            current = current.getNext();
            len++;
        }
        return len;
    }
    public StringNode last() {
        StringNode current = this.node0;
        //int len = 0;
        StringNode prev = null;
        while (current != null) {
            prev = current;
            current = current.getNext();
            //len++;
        }
        return prev;
    }
    public boolean add(StringNode node) {
        if (node == null) {
            return false;
        }
        last().setNext(node);
        return true;
    }
    public boolean add(String payload) {
        StringNode newNode = new StringNode(payload);
        return add(newNode);
    }
    public StringNode get(int idx) {
        StringNode current = node0;
        for (int i = 0; i < idx; i++) {
            current = current.getNext();
        }
        return current;
    }
}