Verkettete Liste

Für viele Probleme benötigt man Datenstrukturen, die mehrere Elemente gleichen Typs speichern können. So wollen wir in unserer Zoohandlung beispielsweise eine Liste mit allen Tieren erstellen und diese etwa ausgeben oder nach dem Alphabet ordnen können.

Wir haben bereits ein Beispiel dafür gesehen, nämlich eine Variante, um alle Füße im Zoo zu zählen:

externesPackage/ExterneMainKlasse.java:

package externesPackage;

import zoohandlung.*;

public class ExterneMainKlasse {

    public static void main(String[] args) {
        Laufen[] tiere = new Laufen[2]; // neues Array für zwei Objekte vom Typ Laufen erstellen

        Papagei p = new Papagei("Ara", 1.3, "Hallo", 40);
        p.setAnzahlBeine(2);

        Loewe leo = new Loewe("Leo", 115);
        leo.setAnzahlBeine(4);

        tiere[0] = p; // p und leo im Array speichern
        tiere[1] = leo;

        int summe = 0; // in Summe steht am Ende die Gesamtzahl der Beine

        for (int i = 0; i < tiere.length; i++) {
            summe += tiere[i].getAnzahlBeine(); // Jetzt geht alles!
        }
        System.out.println(summe);
    }
}Java

Das hat schon ganz gut funktioniert, allerdings ist ein normales Array im Java nicht immer die beste Datenstruktur, allein schon deshalb, da es schwierig ist, einem bestehenden Array ein Element hinzuzufügen: Da bereits schon beim Erstellen eines Arrays festgelegt wird, wie viele Elemente es hat, müsste man schon im Voraus wissen, wie viele Elemente es enthalten wird. Unsere Zoohandlung weiß aber nicht im Voraus, wie viele Tiere in ihr gehalten werden müssen.

Da muss es etwas Besseres geben. Als einfaches Beispiel für eine solche Datenstruktur wollen wir eine einfach verkettete Liste (englisch: singly linked list) erstellen, die es uns erlauben soll, jederzeit ein neues Tier hinzuzufügen und diese Liste auszugeben.

Die Idee ist ganz einfach: Die verkettete Liste soll aus einzelnen Knoten bestehen. Jeder dieser Knoten kann ein Tier (Tier inhalt) aufnehmen und verweist auf den Nachfolgerknoten (Knoten nachfolger).

Unsere verkettete Liste hat einen Verweis auf den ersten Knoten (damit wir nachher alle Knoten ausgeben können) und auf den letzten Knoten (damit wir wissen, an welchen Knoten wir einen neuen Knoten anhängen).

So könnte man einen neuen Knoten anhängen:

Und das wäre das zugehörige UML-Diagramm:

Unsere LinkedList soll zwei Methoden haben: void add(Tier), um ein neues Tier hinzuzufügen und void printAll(), um alle Tiere in der Liste auszugeben.

Ein erster Versuch

Eine einfach Umsetzung von Knoten könnte so aussehen:

MySinglyLinkedList1/Knoten.java:

package MySinglyLinkedList1;

import zoohandlung.Tier; // damit der Wert des Inhalts festgelegt werden kann

public class Knoten {

    Tier inhalt;
    Knoten nachfolger;
}Java

Und unsere MyLinkedList hätte den folgenden Code:

MySinglyLinkedList1/MyLinkedList.java:

package MySinglyLinkedList1;

import zoohandlung.*; // damit der Typ Tier bekannt ist

public class MyLinkedList {

    Knoten ersterKnoten = null;
    Knoten letzterKnoten = null;

    public void add(Tier t) {
        Knoten k = new Knoten();
        k.inhalt = t;
        if (ersterKnoten == null) { //erstes Element
            ersterKnoten = k;
            letzterKnoten = k;
        } else {
            letzterKnoten.nachfolger = k;
            letzterKnoten = k;
        }
    }

    public void printAll() {
        Knoten aktuellerKnoten = ersterKnoten;
        while (aktuellerKnoten != null) {
            System.out.println(aktuellerKnoten.inhalt);
            aktuellerKnoten = aktuellerKnoten.nachfolger;
        }
    }
}Java

In den ersten beiden Zeilen werden die Knoten ersterKnoten und letzterKnoten als Felder deklariert. Der Wert dieser Felder wird jeweils aus null gesetzt, was bedeutet, dass in ihnen noch kein Objekt vom Typ Knoten gespeichert ist:

Knoten ersterKnoten = null;
Knoten letzterKnoten = null;

Die Methode add(Tier) erwartet als Übergabeparameter ein Objekt vom Typ Tier und erstellt mit der übergebenen Tier einen neuen Knoten:

public void add(Tier t) {
    Knoten k = new Knoten(); (1)
    k.inhalt = t; (2)
    if (ersterKnoten == null) { //erstes Element (3)
        ersterKnoten = k;
        letzterKnoten = k;
    } else {
        letzterKnoten.nachfolger = k; (4)
        letzterKnoten = k; (5)
    }
}

1	Ein neuer, leerer Knoten wird erstellt
2	Der Inhalt dieses Knotens verweist auf das übergebene Objekt vom Typ Tier
3	Sollte der erste Knoten noch `null` sein, unser Eintrag also der erste Eintrag in der Liste sein, so verweisen der erste und der letzte Knoten auf das übergebene Objekt
4	Der Nachfolger des bisherigen letzten Knotens ist der neue Knoten und …
5	… wir haben jetzt einen neuen letzten Knoten, nämlich den, den wir gerade angehängt haben.

Nun müssen noch alle Werte unserer Liste ausgegeben werden:

public void printAll() {
    Knoten aktuellerKnoten = ersterKnoten; (1)
    while (aktuellerKnoten != null) { (2)
        System.out.println(aktuellerKnoten.inhalt); (3)
        aktuellerKnoten = aktuellerKnoten.nachfolger; (4)
    }
}

1	`aktuellerKnoten` enthält immer den aktuell auszugebenden Knoten. Zu Beginn setzen wir diesen auf den ersten Knoten.
2	Solange der aktuelle Knoten auf ein bestehendes Objekt verweist (also ungleich `null` ist):
3	gib den Inhalt des aktuellen Knotens aus
4	der neue Wert in `aktuellerKnoten` ist der Nachfolger des aktuellen Knotens

Probieren wir unsere aktuelle Umsetzung der Klassen MyLinkedList und Knoten mal aus. Dazu können wir aus einem anderen Package den folgenden Code aufrufen:

externalPackage/Main1.java:

package externalPackage;

import MySinglyLinkedList1.MyLinkedList;
import zoohandlung.*;

public class Main1 {

    public static void main(String[] args) {
        MyLinkedList mll = new MyLinkedList(); (1)
        for (int i = 0; i < 10; i++) {
            Loewe l = new Loewe("Leo" + i, Math.random()); (2)
            mll.add(l); (3)
        }
        mll.printAll(); (4)
    }
}

1	Erstelle eine neue Instanz von unserer Klasse `MyLinkedList` und speichere diese in der Variable mit dem Namen `mll`.
2	Erstelle einen neuen Löwen mit dem Namen Leo0 bis Leo9 und gib diesen Löwen jeweils ein zufälliges Gewicht
3	Füge die erstellten Löwen der Liste hinzu
4	Gib alle Löwen in der Liste aus

Startet man das Programm, so werden tatsächlich die Namen der 10 hinzugefügten Löwen ausgegeben. Super: Prinzipiell ist damit unser Ziel erreicht!

Aber es geht noch besser!

Abhängigkeit vom Package zoohandlung reduzieren

In der bisherigen Umsetzung des Codes findet man in Knoten.java und in LinkedList.java jeweils die Zeile

import zoohandlung.Tier;Java

damit zum Beispiel in Knoten.java der Typ Tier überhaupt bekannt ist:

MySinglyLinkedList1/Knoten.java:

import zoohandlung.Tier; // damit der Wert des Inhalts festgelegt werden kann

public class Knoten {

    Tier inhalt;
    Knoten nachfolger;
}Java

Das Problem besteht nun darin, dass unsere Klasse MyLinkedList dadurch nur zum Speichern von Objekten des Typs Tier funktioniert. Das war zwar unser ursprüngliches Ziel, aber schöner wäre es doch, wenn man in dieser LinkedList z. B. auch Strings speichern könnte, so dass man unsere LinkedList auch so verwenden könnte:

public static void main(String[] args) {
    MyLinkedList mll = new MyLinkedList();
    for (int i = 0; i < 10; i++) {
        mll.add("Text" +i);
    }
    mll.printAll();
}

Ein einfacher Trick sieht so aus:

Jede Klasse in Java ist automatisch eine Unterklasse der Klasse Object. Legt man also in unserem Knoten als Typ des Inhalts statt Tier einfach Object fest, so kann unsere Liste nun Objekte beliebiger Typen speichern.

Alles was wir dazu tun müssen, ist in Knoten.java und MyLinkedList.java jedes Mal, wenn der Typ Tier vorkommt, diesen durch den Typ Object ersetzen.

Dadurch wird aus

MySinglyLinkedList1/Knoten.java:

package MySinglyLinkedList1;

import zoohandlung.Tier; // damit der Wert des Inhalts festgelegt werden kann

public class Knoten {

    Tier inhalt;
    Knoten nachfolger;
}Java

MySinglyLinkedList2/Knoten.java:

package MySinglyLinkedList2;

public class Knoten {

    Object inhalt;
    Knoten nachfolger;
}Java

Beachte, dass der Import von zoohandlung.Tier jetzt nicht mehr notwendig ist!

Ebenso kann man sich in der Klasse MyLinkedList den Import sparen und aus der Methode

public void add(Tier t) {
    ...
}

wird die Methode

public void add(Object t) {
    ...
}

Probiert man diese neue Klasse nun aus, so kann man nach wie vor problemlos Objekte vom Typ Tier der LinkedList hinzufügen:

public static void main(String[] args) {
    MyLinkedList mll = new MyLinkedList();
    for (int i = 0; i < 10; i++) {
        Loewe l = new Loewe("Leo" + i, Math.random());
        mll.add(l); (1)
        mll.add(Math.random()); (2)
    }
    mll.printAll();
}

1	Hier wird ein Objekt vom Typ Loewe (ist auch ein Objekt vom Typ Object) der Liste hinzugefügt.
2	Hier wird `mll` ein Objekt vom Typ Integer hinzugefügt. Kein Problem, ist ja auch ein Objekt vom Typ Object.

Hmm, das ist jetzt nicht das, was wir wollten: Zwar ist MyLinkedList jetzt unabhängig von zoohandlung.Tier, aber der Preis dafür besteht darin, dass man nun Objekte jeden Typs in unserer verketteten Liste speichern kann, und zwar so, dass unsere verkettete Liste gleichzeitig Objekte vom Typ Loewe und vom Typ Integer enthält. Auch andere Objekte wie Strings oder MP3-Lieder könnten gleichzeitig mit unserem Löwen in der verketteten Liste gespeichert werden.

Wir wollen zwar, dass unsere verkettete Liste für die unterschiedlichsten Typen funktioniert, jede verkettete Liste soll jedoch nur Objekte des gleichen Typs aufnehmen können.

Zum Beispiel soll es eine verkettete Liste geben, die nur Objekte vom Typ Loewe speichert und eine andere, die nur Objekte vom Typ Integer speichert.

Generische Klassen und Methoden

Wir müssen es also irgendwie schaffen, dass unsere verkettete Liste zwar für jeden Typ funktioniert, aber so, dass alle Elemente unserer Liste von diesem gleichen Typ sind.

Zum Glück gibt es zu diesem Zweck eine einfache Lösung: generische Klassen und Methoden!

Sehen wir uns das am Beispiel von Knoten an: aus

MySinglyLinkedList2/Knoten.java:

package MySinglyLinkedList2;

public class Knoten {

    Object inhalt;
    Knoten nachfolger;
}Java

wird dabei

package MySinglyLinkedList3;

public class Knoten<T> { (1)

    T inhalt; (2)
    Knoten<T> nachfolger; (3)
}

1	`Knoten<T>` bedeutet, dass in der Klasse Knoten ein Typ `T` vorkommt, der überall dort, wo er in der Klasse vorkommt, derselbe ist.
2	Es gibt ein Feld namens `inhalt` das vom Typ `T` ist
3	Der Nachfolger ist wieder ein Knoten, der wieder den Typparameter `T` erhält, d. h. auch dieser Knoten kann nur wieder einen Inhalt vom Typ `T` speichern.

Am einfachsten kann man diesen Typparameter verstehen, wenn man das an einem Beispiel veranschaulicht:

Erstellt man einen neuen Knoten über

Knoten<String> k = new Knoten<>();

so ist der Typparameter hier String, d. h. jedes T in der Klasse Knoten<T> kann durch ein String ersetzt werden:

public class Knoten<String> {

    String inhalt; (1)
    Knoten<String> nachfolger; (2)
}

1	Der Typ von `inhalt` ist nun `String`
2	Der Nachfolger unseres Knotens ist hiermit auch vom Typ `Knoten<String>` und somit alle Elemente unserer verketteten Liste.

Analog dazu kann man auch unsere verkettete Liste mit einem Typparameter versehen:

public class MyLinkedList<T> {

    Knoten<T> ersterKnoten = null;
    Knoten<T> letzterKnoten = null;

    public void add(T t) {
        Knoten<T> k = new Knoten<>();
        ...
    }

    public void printAll() {
        Knoten<T> aktuellerKnoten = ersterKnoten;
        ...
    }
}Java

Der Typparameter von MyLinkedList muss bei der Verwendung unserer Klasse immer angegeben werden, so dass unsere verkettete Liste nun so aufgerufen werden muss:

public static void main(String[] args) {
    MyLinkedList<Tier> mll = new MyLinkedList<>();
    for (int i = 0; i < 10; i++) {
        Loewe l = new Loewe("Leo" + i, Math.random());
        mll.add(l);
    }
    mll.printAll();
}Java

Dadurch wird festgelegt, dass unsere verkettete Liste nur Elemente vom Typ Tier aufnehmen kann. Der Versuch, dieser Liste ein neues Element vom Typ Integer oder String hinzuzufügen, wird mit einer Fehlermeldung quittiert.

Möchte man nun eine verkettete Liste erstellen, die nur Strings aufnehmen kann, so muss diese über

MyLinkedList<String> mll = new MyLinkedList<>();

erzeugt werden.

Jetzt funktioniert unsere verkettete Liste tatsächlich so, wie es beabsichtigt war. Toll!

<> heißt wegen seiner Form auch diamond operator.

Zugabe: Implementieren der Interfaces Iterable und Iterator

Eigentlich erfüllt unsere verkettete Liste bereits alle Anforderungen, die wir zu Beginn vorgegeben haben. Aber es sollen an dieser Stelle noch zwei Interfaces implementiert werden, die die Benutzung unserer Klasse noch etwas angenehmer machen.

Für Arrays gibt es eine besonders schöne Variante der for-Schleife:

String[] text=new String[]{"bla","blubb","blobb"};

for (String t:text){
    System.out.println(t);
}Java

Hier wird ein Array erstellt, das die drei Strings "bla", "blubb" und "blobb" enthält.

Statt

for (int i = 0; i < text.length; i++){
    System.out.println(text[i]);
}Java

verwenden wir die elegantere Variante

for (String t:text){
    System.out.println(t);
}Java

Der Vorteil besteht darin, dass man sich keine Gedanken über die Länge des Arrays machen muss; es werden einfach alle Einträge der Feldvariable text ausgegeben.

Wäre es nicht schön, wenn unsere verkettete Liste auch so etwas könnte? Also zum Beispiel, dass der folgende Code funktionieren würde:

MyLinkedList<Tier> mll = new MyLinkedList<>();
for (int i = 0; i < 10; i++) {
    Loewe l = new Loewe("Leo" + i, Math.random());
    mll.add(l);
}

for (Tier t : mll) { // das wäre schön!
    System.out.println(t);
}Java

Dazu muss man wissen, dass for an der Stelle, wo hier das mll steht, ein Objekt erwartet, das das Interface Iterable implementiert.

Also ändern wir unsere Klasse MyLinkedList<T> so ab, dass Iterable<T> implementiert wird:

public class MyLinkedList<T> implements Iterable<T> {

    ...

    @Override
    public Iterator<T> iterator() {
        ...
    }
}Java

Dadurch muss man eine Methode public Iterator<T> iterator() implementieren, die ein Objekt zurückgibt, das das Interface Iterator<T> implementiert.

Also lassen wir unsere Klasse MyLinkedList<T> zusätzlich zu Iterable<T> auch das Interface Iterator<T> implementieren.

Dadurch kommen zwei weitere Methoden dazu:

public class MyLinkedList<T> implements Iterator<T>, Iterable<T> {

    ...

    public boolean hasNext() {
        ...
    }

    public T next() {
        ...
    }

    public Iterator<T> iterator() {
        return this;
    }
}Java

Da unsere Klasse nun auch Iterator<T> implementiert kann unsere Klasse selbst als Objekt vom Typ Iterator<T> zurückgegeben werden.

Nun müssen noch die Methoden 'public boolean hasNext()` und public T next() umgesetzt werden:

hasNext() gibt zurück, ob es noch ein weiteres Element in unserer verketteten Liste gibt. Eine mögliche Umsetzung könnte so aussehen:

public boolean hasNext() {
    boolean rueckgabe = aktuellerKnoten != null;
    if (rueckgabe == false) {
        aktuellerKnoten = ersterKnoten;
    }
    return rueckgabe;
}Java

In rueckgabe wird gespeichert, ob der aktuelle Knoten ungleich null ist (also true, falls er ungleich null ist, sonst false).

Damit die for-Schleife so funktioniert, wie erwartet, muss im Falle, dass wir schon am letzten Knoten sind, der aktuelle Knoten wieder auf den ersten Knoten gesetzt werden.

public T next() muss den nächsten Wert aus der Liste zurückgeben. Das könnte etwa so aussehen:

public T next() {
    T rueckgabe = aktuellerKnoten.inhalt;
    aktuellerKnoten = aktuellerKnoten.nachfolger;
    return rueckgabe;
}Java

Der neue aktuelle Knoten wird dabei auf den Nachfolger des aktuellen Knotens gesetzt. Dieser kann auch null sein.

Insgesamt sieht MyLinkedList nun so aus:

MySinglyLinkedList4/MyLinkedList.java:

package MySinglyLinkedList4;

import java.util.Iterator;

public class MyLinkedList<T> implements Iterator<T>, Iterable<T> {

    Knoten<T> ersterKnoten = null;
    Knoten<T> letzterKnoten = null;
    Knoten<T> aktuellerKnoten = null;

    public void add(T t) {
        Knoten<T> k = new Knoten<>();
        k.inhalt = t;
        k.inhalt = t;
        if (ersterKnoten == null) { //erstes Element
            ersterKnoten = k;
            letzterKnoten = k;
            aktuellerKnoten = k;
        } else {
            letzterKnoten.nachfolger = k;
            letzterKnoten = k;
        }
    }

    @Override
    public boolean hasNext() {
        boolean rueckgabe = aktuellerKnoten != null;
        if (rueckgabe == false) {
            aktuellerKnoten = ersterKnoten;
        }
        return rueckgabe;
    }

    @Override
    public T next() {
        T rueckgabe = aktuellerKnoten.inhalt;
        aktuellerKnoten = aktuellerKnoten.nachfolger;
        return rueckgabe;
    }

    @Override
    public Iterator<T> iterator() {
        return this;
    }
}Java

Nun kann tatsächlich zum Beispiel der folgende Code angewendet werden, der von allen Tieren, die das Interface Laufen implementieren, die Anzahl der Beine ausgibt:

MyLinkedList<Tier> mll = new MyLinkedList<>();
for (int i = 0; i < 10; i++) {
    Loewe l = new Loewe("Leo" + i, Math.random());
    mll.add(l);
}

for (Tier t : mll) {
    if (t instanceof Laufen) {
        System.out.println(((Laufen) t).getAnzahlBeine());
    }
}Java

Neben der Eleganz des nun möglichen Durchlaufens aller Werte ist die neue Lösung der Methode void printAll() auch insofern überlegen, als dass das Durchlaufen der Elemente aus der Klasse herausgeholt wurde. Dadurch kann man, wie im obigen Beispiel geschehen, während des Durchlaufens selbst entscheiden, wie die Ausgabe aussieht bzw. welche Werte überhaupt ausgegeben werden.

Bei der Verwendung von void printAll() musste man die Ausgabe so akzeptieren, wie sie vorgegeben war.

Code zu diesem Kapitel

Den gesamten Code dieses Kapitels findet man auf Github unter https://github.com/menzelths/MyLinkedList.

Zum Clonen des Projekts kann der folgende Link verwendet werden:

https://github.com/menzelths/MyLinkedList.git

Inhaltsverzeichnis

Verkettete Liste

Ein erster Versuch

Abhängigkeit vom Package zoohandlung reduzieren

Generische Klassen und Methoden

Zugabe: Implementieren der Interfaces Iterable und Iterator

Code zu diesem Kapitel