Liste

Die Liste ist eine lineare Datenstruktur, die sequentiell (d.h. von vorn nach hinten) durchlaufen wird. Jedes Element der Liste hat lediglich Zugriff auf seinen Nachfolger, wodurch sich eine verkettete Struktur ergibt.

Die Liste ist dynamisch, da an jeder Position neue Elemente in die Kette eingefügt werden können. Eine Suche auf einer Liste hat lineare Laufzeit, da nur der vollständige Durchlauf von vorn nach hinten möglich ist.

Die Abiturklasse List ist generisch, d.h. bereits beim Erzeugen wird festgelegt, von welcher Klasse die Objekte sein müssen, die in der Liste verwaltet werden sollen. Dabei ist es natürlich möglich (wenn auch nur selten sinnvoll), auch Objekte von Unterklassen dieser Klasse zu verwalten.

Eine Liste aufbauen

Im folgenden Beispiel wird beim Erzeugen der Liste festgelegt, dass Objekte der Klasse String verwaltet werden sollen. Mit Hilfe der Methode append werden die Zeichenketten jeweils an das Ende der Liste gehängt, wodurch sich die Reihenfolge Babsi - Franzi - Susi ergibt.

String s1 = "Babsi";
String s2 = "Franzi";
String s3 = "Susi";

List<String> l = new List<String>();
l.append(s1);
l.append(s2);
l.append(s3);

Eine Liste durchlaufen

Beim Durchlaufen einer Liste (z.B. um eine Suche zu realisieren) ist ein Sprung an den Anfang der Liste mithilfe der Methode toFirst() erforderlich. Anschließend hilft die Anfrage hasAccess() dabei zu erfragen, ob noch ein Listenelement verfügbar ist oder durch das Weiterlaufen durch die Liste mit der Methode next() bereits das Ende der Liste erreicht ist.

Wird die Zeichenketten-Liste aus dem vorherigen Abschnitt zugrunde gelegt, so lautet die Ausgabe der Schleife: Babsi -> Franz -> Susi -> ENDE!

l.toFirst();

while (l.hasAccess()) {
    String s = l.getContent();
    System.out.print(s+" -> ");
    l.next();
}

System.out.println("ENDE!");

Eine Liste verändern

Für das nächste Beispiel stellen wir uns eine Musiksammlung vor, in der Objekte der Klasse Titel verwaltet werden. Für jedes Titelobjekt ist eine Bewertung zwischen 1 und 5 angegeben, die durch die Methode getBewertung() erfragt werden kann.

Damit durchläuft die Schleife die Liste aller Titelobjekte und löscht mit der Methode remove() diejenigen Titel, die eine Bewertung 1 erhalten haben. Zusätzlich wird die Anzahl der gelöschten Objekte in der Variablen counter mitgezählt.

l.toFirst();
int counter = 0;

while (l.hasAccess()) {

    Titel t = l.getContent();
    if (t.getBewertung()==1) { 
        l.remove(); 
        counter++;
    }
    else { 
        l.next(); 
    }

}

In eine sortierte Liste einfügen

Eine Sortierung einer Liste kann mitunter ebenfalls sinnvoll sein. In unserem Beispiel der Musiksammlung könnten die Titelobjekte sortiert nach der Bewertung abgelegt werden. Damit die Sortierung der Liste nicht verloren geht, muss dem Benutzer der Musiksammlung eine eigene Methode zum sortierten Einfügen eines neuen Titels zur Verfügung gestellt werden.

Die Schleife wird solange durchlaufen, bis ein Titel gefunden wurde, der eine höhere oder gleich hohe Bewertung als der neue Titel besitzt. An dieser Stelle wird das zugehörige Titelobjekt mit der Methode insert vor dem aktuellen Listenobjekt eingefügt.

public void fuegeTitelSortiertEin(Titel t, List l) {
    l.toFirst();
    while (l.hasAccess()) {
        Titel aktuell = l.getContent();
        if (t.getBewertung() <= aktuell.getBewertung()) {
            l.insert(t);
            return;
        }
        else {
            l.next();
        }
    }
    l.append(t);
}

results matching ""

    No results matching ""