List

Einführung

Nachdem wir uns bei Verwendung der Klassen Queue und Stack strikt an das First-in-First-Out- bzw. Last-in-First-Out-Prinzip halten mussten, wollen wir nun eine Datenstruktur einführen, die flexibler ist. Sie ähnelt sehr der Klasse Queue, bietet aber die Möglichkeit, auf beliebige Elemente zuzugreifen und auch an beliebiger Stelle neue hinzuzufügen oder zu entfernen. Eine übliche Bezeichnung für eine solche Datenstruktur ist (einfach) verkettete Liste. Daher nennen wir die entsprechende Klasse einfach List.

Diese Klasse müssen werden wir nicht selbst implementieren. Stattdessen greifen wir hier sofort auf die Abiturklasse zurück.

Betrachten wir eine schematische Darstellung, erkennen wir, wo der entscheidende Unterschied zur Klasse Queue liegt:

Hier gibt es – ähnlich wie bei unserer allerersten Umsetzung einer Warteschlange – einen Laufzeiger, der auf einen beliebigen Knoten in der Liste zeigen kann. Dieser ermöglicht uns den Zugriff auf beliebige Elemente.

Zur Übersicht hier die Methoden, die bei dieser Klasse zur Verfügung stehen. Dabei ist zu beachten, dass diese Klasse wie die Abiturklassen Queue und Stack auch generisch ist. D. h., auch hier wird beim Erstellen festgelegt, von welcher Klasse zu speichernden Objekte sein müssen.

List()	Eine leere Liste wird erzeugt.
void toFirst()	Dies setzt den Laufzeiger auf den den ersten Knoten. Ist die Liste leer, so passiert nichts.
void next()	Sofern der Laufzeiger sich noch innerhalb der Liste befindet, wird er eine Position nach rechts verschoben. Befindet er sich bei Aufruf der Methode auf dem letzten Knoten, so befindet er sich danach jenseits der Liste.
void insert(pNeues:ContentType)	Sofern der Laufzeiger sich noch innerhalb der Liste befindet, wird vor dem von ihm referenzierten Knoten ein neuer Knoten mit Inhalt pNeues eingefügt. Befindet er sich jenseits der Liste, geschieht nichts.
void append(pNeues:ContentType)	Hängt an das Ende der Liste einen neuen Knoten mit Inhalt pNeues.
void remove()	Befindet sich der Laufzeiger innerhalb der Liste, wird der von ihm referenzierte Knoten gelöscht. Anschließend zeigt der Laufzeiger auf den Knoten, der rechts vom gelöschten lag. Wurde der letzte Knoten gelöscht, befindet sich der Laufzeiger damit jenseits der Liste.
void setContent()	Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst geschieht nichts.
void concat(List<ContentType> pList)	Falls pList null oder eine leere Liste ist, geschieht nichts. Ansonsten wird die Liste pList an die aktuelle Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert.
boolean isEmpty()	Dies liefert, wie gewohnt, den Wert true, wenn die Liste keine Objekte enthält und sonst den Wert false.
boolean hasAcceess()	Dies liefert den Wert true, wenn der Laufzeiger sich innerhalb der Liste befindet. Andernfalls wird der Wert false zurückgegeben.
ContentType getContent()	Sofern sich der Laufzeiger innerhalb der Liste befindet, wird das Inhaltsobjekt des von ihm referenzierten Knotens geliefert. Andernfalls wird null zurückgegeben.

Anwendungsbeispiel

Sehen wir uns ein kleines Beispiel an:

Ein Objekt der Klasse Kartenverwalter verwaltet Spielkarten in einer List. Mit haengeDran können weitere Karten (unsortiert) hinzugefügt werden. Mit istVorhanden kann abgefragt werden, ob eine bestimmt Zahl vorhanden ist. Mit schreibeInfo werden alle Karten in der Konsole ausgegeben.
Wir verwenden in diesem Beispiel Uno-Karten.

Die Klasse Spielkarte ist natürlich recht simpel:

public class Spielkarte {

    private String farbe;
    private int wert;

    public Spielkarte(String pFarbe, int pWert) {
        farbe = pFarbe;
        wert = pWert;
    }

    public String getFarbe() {
        return farbe;
    }

    public int getWert() {
        return wert;
    }

    public void schreibeInfo() {
        System.out.println(farbe + " " + wert);
    }

}

Nun die interessantere Klasse:

public class Kartenverwalter {

    private List<Spielkarte> meineKarten;

    public Kartenverwalter() {
        meineKarten = new List<Spielkarte>();
    }

    public void haengeDran(Spielkarte pKarte) {
        meineKarten.append(pKarte);
    }

    public boolean istVorhanden(int pWert) {
        meineKarten.toFirst();
        while (meineKarten.hasAccess()) {
            if (meineKarten.getContent().getWert() == pWert) {
                return true;
            }
            meineKarten.next();
        }
        return false;
    }

    public void schreibeInfo() {
        meineKarten.toFirst();
        while (meineKarten.hasAccess()) {
            meineKarten.getContent().schreibeInfo();
            meineKarten.next();
        }
    }

}

Es fällt auf, dass schon in diesem kurzen Beispiel zwei while-Schleifen vorkommen. Diese eignen sich sehr gut, um eine Liste zu durchlaufen.
Als Faustregel kann man sich merken, dass while-Schleifen zu Listen gehören wie for-Schleifen zu Arrays.

Hier ist noch eine passende ausführende Klasse:

public class KartenverwalterTest {

    public static void main(String[] args) {

        Kartenverwalter meinVerwalter = new Kartenverwalter();

        meinVerwalter.haengeDran(new Spielkarte("rot", 5));
        meinVerwalter.haengeDran(new Spielkarte("gelb", 1));
        meinVerwalter.haengeDran(new Spielkarte("rot", 2));
        meinVerwalter.haengeDran(new Spielkarte("grün", 8));
        meinVerwalter.haengeDran(new Spielkarte("blau", 2));

        System.out.println(meinVerwalter.istVorhanden(4));

        meinVerwalter.schreibeInfo();
    }

}

Das Beispiel der Spielkarten ist natürlich kein Zufall. In der Tat eignen sich Listen prima, um ein Kartenspiel wie Uno zu modellieren!