Nicht nur Algorithmen, sondern auch Datenstrukturen können rekursiv sein: Ein klassisches Beispiel hierfür ist die verkettete Liste. In dieser Erklärung wirst Du die einfach und doppelt verkettete Liste kennenlernen.

Listen Informatik

In der Informatik ist eine verkettete Liste eine dynamische Datenstruktur, die die geordnete Speicherung von Datenelementen unterstützt. Die Anzahl der Objekte muss nicht im Voraus bekannt sein (z. B. zur Kompilierzeit) und bleibt für die Lebensdauer der Liste offen.

Listen Definition

Ein Array hat einen Nachteil. Du musst im Voraus wissen, wie viele Artikel Du benötigst. Dieses Problem wird mit der Datenstruktur einer Liste gelöst.

Die Liste besteht aus "Zellen" und jede Zelle besteht aus zwei Teilen:

• Der erste Teil ist das eigentliche Listenelement, also der Zellinhalt.
• Der zweite Teil dient der Verkettung der Listen und ist eine Referenz auf das nächste Listenelement (genauer gesagt die Zelle des nächsten Listenelements).

Da die letzte Zelle per Definition keine "nächste" Zelle hat, muss der nicht referenzierte Nullwert dort stehen.

Operationen mit Listen

Du kannst Listen flexibel auf- und abbauen. Dazu gibt es ganz einfache Standardoperationen:

• Create: Erstellen und Verketten von Listenelementen.
• Delete: Entketten und Löschen eines Listenelements.
• Search: Suchen nach einem bestimmten Listenelement.
• Destroy: Alle Elemente löschen.
• Insert: Element hinzufügen
• Size: Elementanzahl

Lineare Liste

Wie die meisten abstrakten Datentypen ist die lineare ADT-Liste ein zusammengesetzter Datentyp. Jedes seiner Objekte besteht aus einer endlichen Anzahl von Teilobjekten oder Elementen und ist linear angeordnet.

Für lineare Listen gilt Folgendes:

1. Es kann nur ein Listenelement geben, das keinen Vorgänger hat und als Anfang der Liste bezeichnet wird. Ein Listenanker zeigt auf dieses Element.
2. Es kann nur ein Listenelement geben, das keine Nachfolger hat und als Ende der Liste bezeichnet wird.
3. Die restlichen Listeneinträge haben genau einen Vorgänger und genau einen Nachfolger.

Verkettete Listen

Eine verkettete Liste ist ein Datencontainer, dessen Elemente (Knoten) nicht hintereinander im Hauptspeicher abgelegt werden müssen (wie bei Arrays), sondern beliebig über alle Speicher verteilt werden können. Aufeinanderfolgende Knoten sind durch Zeiger miteinander verbunden.

Arten von verketteten Listen

Es gibt verschiedene Arten von verkettete Listen:

Einfach verkettete Liste

Eine einfach verkettete Liste ist eine Folge beliebig vieler Listenelemente (Knoten), die durch Zeiger miteinander verbunden sind. Die Anzahl der Elemente kann während der Programmausführung beliebig verändert werden.

Jeder Listeneintrag besteht aus einem Datenbereich und einem Zeiger auf das nächste Listenelement. Datenbereich bedeutet eine oder mehrere Variablen, die tatsächliche Daten (Werte, Zeichenfolgen usw.) speichern.

Einfach verkettete Liste Java

Wenn man eine Datenstruktur mit einigen Standardoperationen hat, sollte man diese in einer einzigen Klasse zusammenfassen. Dies gilt offensichtlich für Listen, weshalb in JAVA (im Paket java.util) eine LinkedList-Klasse vordefiniert ist.

Hier erwartet Dich die Java-Implementierung einer einfach verketteten Liste:

// Ein verketteter Listenknoten
class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
        this.next = null;
    }
}


class Main{
    // Hilfsfunktion zum Ausgeben einer gegebenen einfach verketteten Liste
    public static void printList(Node head){
        Node ptr = head;
        while (ptr != null){
            System.out.print(ptr.data + " —> ");
            ptr = ptr.next;
        }

        System.out.println("null");

    }
    // Naive Funktion für die Darstellung von verketteten Listen mit vier Knoten
    public static Node constructList(){
        // Verkettete Listenknoten erstellen
        Node first = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        Node fourth = new Node(4);
        // Ordne die Pointer neu an, um eine Liste zu erzeugen
        Node head = first;
        first.next = second;
        second.next = third;
        third.next = fourth;
        // Pointer auf den ersten Knoten in der Liste zurückgeben
        return head;

    }

    public static void main(String[] args){
        // "head" zeigt auf das Startelement der verketteten Liste
        Node head = constructList();
        // Verkettete Liste ausgeben
        printList(head);

    }

}

Output: 1 ⇢ 2 ⇢ 3 ⇢ 4 ⇢ null

Um effektiv mit einer Liste arbeiten zu können, benötigst Du natürlich die in der folgenden Tabelle aufgeführten Listenoperationen:

Doppelt verkettete Liste

Basierend auf einer einfach verketteten Liste kann eine doppelt verkettete Liste als konzeptionelle Erweiterung beschrieben werden, bei der jeder Knoten nicht nur den nächsten Knoten, sondern auch den vorherigen Knoten referenziert. Die Liste kann also (von jedem Knoten aus) in beide Richtungen durchlaufen werden:

Abb. 2 - Doppelt verkettete Liste

Eine entsprechende JAVA-Klasse sieht (vereinfacht, ohne private Klassenattribute) etwa so aus:

public class Node {
int data;
Node previous;
Node next;
 // Konstruktor für Wert, etc. ...
}

Die doppelt verkettete Liste erleichtert einige Operationen – wie das Löschen eines Knotens mit einem bestimmten Wert, da der entfernte Knoten selbst auf zwei benachbarte Knoten verweist, deren Referenzen (auf den gelöschten Knoten) geändert werden müssen.

Zirkuläre Listen

In einigen Anwendungen benötigst Du Listen, die keinen Anfang und kein Ende haben, bei denen man aber wieder von vorn beginnen möchte. Dann setzt man den Zeiger nicht auf null, sondern lässt ihn auf das erste Element verweisen.

Beispielsweise kann ein Viereck als zirkuläre Liste betrachtet werden, das aus vier Punkten A, B, C, D besteht.

Array Listen

ArrayList und LinkedList implementieren die List-Schnittstelle und behalten die Einfügungsreihenfolge bei. Beides sind asynchrone Klassen.

Es gibt jedoch Unterschiede zwischen den beide Klassen.