Listen

Listen sind verkettete Datenstrukturen, die im Gegensatz zu Feldern dynamisch wachsen können um beliebig viele Elemente (Knoten) zu verwalten. Sie werden anstatt Felder verwendet wenn

  • die maximale Größe nicht vorab bekannt ist
  • kein wahlfreier Zugriff auf beliebige Listenelemente (bzw. Knoten) benötigt wird.
  • die Reihenfolge der Knoten wichtig ist.

Typische Operationen die für Listen zur Verfügung stehen sind:

  • Einfügen von Knoten in die Liste
  • Entfernen von Knoten aus der Liste
  • Veränderung der Knotenreihenfolge
  • Bestimmung der Länge der Liste
  • Abfrage ob ein Knoten in der Liste enthalten ist

Mit Hilfe von Listen können auch spezialisiertere Datenstrukturen wie Warteschlangen (engl. queues) oder Stapel (engl. stack) implementiert werden.

Listen in Java

Eine verkettete Datenstruktur kann mit jeder Javaklasse aufgebaut werden die in der Lage ist auf Objekte der gleichen Klasse zu zeigen.

Eine solche Verkettung kann man zum Beispiel mit jeder Klasse implementieren, die die folgende Schnittstelle implementiert:

package s2.listen;
/**
*
* @author s@scalingbits.com
*/
public interface EinfacherListenknoten {
/**
* Einfuegen eines Nachfolgers
* @param n einzufuegender Listenknoten
*/
public void setNachFolger(EinfacherListenknoten n);
/**
* Auslesen des Nachfolgers
* @return der Nachfolger
*/
public EinfacherListenknoten getNachfolger();
}

Dies geschieht im folge für die Klasse Ganzzahl, die neben der Listeneigenschaft auch in der Lage ist eine Ganzzahl zu verwalten:

package s2.listen;

/**
*
* @author s@scalingbits.com
*/
public class Ganzzahl implements EinfacherListenknoten {

public int wert;
private EinfacherListenknoten naechsterKnoten;

public Ganzzahl(int i) {
wert = i;
naechsterKnoten = null;
}
/**
* Einfuegen eines Nachfolgers
* @param n einzufuegender Listenknoten
*/
@Override
public void setNachFolger(EinfacherListenknoten n) {
naechsterKnoten = n;
}
/**
* Auslesen des Nachfolgers
* @return der Nachfolger
*/
@Override
public EinfacherListenknoten getNachfolger() {
return naechsterKnoten;
}

/**
* Hauptprogramm zum Testen
* @param args
*/
public static void main(String[] args) {
Ganzzahl z1 = new Ganzzahl(11);
Ganzzahl z2 = new Ganzzahl(22);
Ganzzahl z3 = new Ganzzahl(33);
z1.setNachFolger(z2);
z2.setNachFolger(z3);
}
}

In UML:

 

Hiermit kann eine verkettete Struktur aufgebaut werden, die die Verwaltung von beliebig vielen Objekten erlaubt. In der main() Methode wird eine verkettete Liste von drei Objekten aufgebaut:

Zum Zugriff auf diese Liste reicht jetzt die Referenzvariable z1. Alle anderen Knoten können mit Hilfe der Methode getNachfolger() erreicht werden. Es existiert jedoch kein wahlfreier Zugriff auf die Knoten der Liste.

Werden die beiden Variablen z2 und z3 dereferenziert, können die einzelnen Knoten nach wie vor erreicht werden:

z2 = null;
z3 = null;

Wird die Variable z1 dereferenziert,

 z1 = null;

sind alle drei Objekte nicht mehr erreichbar und können vom Garbagekollektor gelöscht werden.

Unsortierte Listen

Im einfachsten Fall kann eine Liste als einfach verzeigerte Liste implementiert die nur auf den Kopfknoten zeigt.

  • Das Einfügen und Löschen am Kopfende hat einen konstanten Aufwand
  • Das Suchen bzw. Löschen von Knoten hat einen Aufwand von O(n)
  • Relativer Zugriff von einem bekannten Knoten ist nur in Richtung der Nachfolger möglich.

Bei Listen kann man auch das Ende der Liste im Listenobjekt mit pflegen. Einfüge- und Entnahmeoperationen werden hierdurch aufwendiger zu implementieren. Der Vorteil liegt jedoch darin, dass auf das Ende der Liste wahlfrei zugegriffen werden kann.

Vorteile einfach verzeigerter Listen mit Referenz auf das Ende der Liste

  • Zugriff auf das und erste und letzte Element der Liste mit konstantem Aufwand
  • Iterieren über die Menge aller Listenelemente ist möglich
  • Löschen des letzten Elements ist mit konstantem Aufwand möglich (Hierdurch kann eine Warteschlange implementiert werden)

Nachteile

  • Kein wahlfreier Zugriff auf alle Elemente
  • Man kann nur auf ein Nachbarelement (den Nachfolger) mit konstantem Aufwand zugreifen

Zweiseitig verzeigerte Listen haben den Vorteil, dass sie einen direkten Zugriff auf den Vorgängerknoten sowie auf den Nachfolgerknoten haben:

Vorteile (über die einfach verzeigerte Liste hinaus):

  • Iterieren ist in zwei Richtungen möglich
  • Der Vorgängerknoten eines Listenknoten kann auch mit konstantem Aufwand errreicht werden

 

 

Übungen (Listen)

Doppelt verzeigerte Liste mit Referenz auf das Ende der Liste

Implementieren Sie eine doppelt verzeigerte Liste zur Verwaltung ganzer Zahlen. Der Listenkopf referenziert auf das Kopfelement sowie auf das letzte Element der Liste

Eine Liste mit drei Knoten soll wie folgt implementiert sein:

Beachten Sie die die beiden Sonderfälle einer Liste mit einem Element und den Sonderfall einer leeren Liste.

Zur beschleunigten Implementierung sind alle Klassen schon gegeben

  • ListenKnoten: Eine einfache Klasse zur Verwaltung ganzer Zahlen mit Referenzen auf Vorgänger- und Nachfolgerknoten
  • MainTestListe: Ein Hauptprogramm mit diversen Testroutinen zum Testen der Liste
  • EineListe: Eine Rahmenklasse die vervollständigt werden soll. Implementieren Sie die folgenden Methoden:
    • einfuegeAnKopf(einfuegeKnoten): Einfügen eines Knotens am Kopf der Liste
    • laenge(): Berechnung der Länger der Liste
    • loesche(Knoten): Löschen eines Knotens einer Liste
    • enthaelt(Knoten): Prüfung ob ein Knoten in der Liste enthalten ist. Die Prüfung erfolgt auf Objektidentität, nicht auf Wertgleichheit
    • einfuegeNach(nachKnoten,einfuegeKnoten): Einfügen eines neuen Knotens einfuegeKnoten hinter dem Knoten nachKnoten

UML Diagramm der drei Klassen:

Klasse Listenknoten

package s2.listen;
/**
*
* @author s@scalingbits.com
*/
public class Listenknoten {
private Listenknoten vorgaenger;
private Listenknoten nachfolger;
private int wert;

public Listenknoten(int einWert) { wert=einWert;}
public Listenknoten getNachfolger() { return nachfolger;}
public void setNachfolger(Listenknoten nachfolger) {
this.nachfolger = nachfolger;
}
public Listenknoten getVorgaenger() {
return vorgaenger;
}
public void setVorgaenger(Listenknoten vorgaenger) {
this.vorgaenger = vorgaenger;
}
public int getWert() {
return wert;
}
public void setWert(int wert) {
this.wert = wert;
}
/**
* Erlaubt den Zahlenwert als Text auszudrucken
* @return
*/
@Override
public String toString() { return Integer.toString(wert);}
}

Klasse EineListe

Vervollständigen Sie die folgende Klasse

package s2.listen;

/**
*
* @author s@scalingbits.com
*/

public class EineListe {
    protected Listenknoten kopf;
    protected Listenknoten ende;
    /**
     * Konstrukor. Erzeuge eine leere Liste
     */
    public EineListe() {
        kopf = null;
        ende = null;
    }
    /**
    * Berechne die Länge der Liste
    * @return Länge der Liste
    */
    public int laenge() {
        int laenge = 0;
        System.out.println("1. Implementieren Sie EineListe.laenge()");
        return laenge;
    }
    /**
     * Liefert den Kopf der Liste oder einen Null Zeiger
     * @return
     */
    public Listenknoten getKopf() {
        return kopf;
    }
    /**
     * Liefert das Ende der Liste oder einen Null Zeiger
     * @return
     */
    public Listenknoten getEnde() {
        return ende;
    }
    /**
     * Drucke eine Liste alle Objekte auf der Konsole
     */
    public void drucken() {
        System.out.println("Länge Liste: " + laenge());
        Listenknoten k = kopf;
        while (k != null) {
            System.out.println("Knoten: " + k);
            k = k.getNachfolger();
        }
    }
    /**
     * Füge hinter dem Listenknoten "nach" den Knoten "k"ein.
     * Füge nichts ein wenn der Listenknoten "nach" nicht in der Liste
     * vorhanden ist
     * @param nach
     * @param k
     */
    public void einfuegeNach(Listenknoten nach, Listenknoten k) {
        System.out.println("5. Implementieren Sie EineListe.einfuegeNach()");
    }
    /**
     * Füge einen Listenknoten am Kopf der Liste ein
     * @param k neuer Listenknoten
     */
    public void einfuegeAnKopf(Listenknoten k) {
        System.out.println("2. Implementieren Sie EineListe.einfuegeAnKopf()");
    }
    /**
     * Lösche einen Knoten aus der Liste. Mache nichts falls es nichts zu
     * gibt
     * @param k zu löschender Listenknoten
     */
    public void loesche(Listenknoten k) {
        System.out.println("3. Implementieren Sie EineListe.loesche()");
    } // Ende Methode loesche()
    /**
     * Ist wahr wenn ein Knoten mit dem gleichen Wert existiert
     * @param k
     * @return
     */
    public boolean enthaelt(Listenknoten k) {
        boolean result = false;
        System.out.println("4. Implementieren Sie EineListe.enthaelt()");
        return result;
    } // Ende Methode enhaelt()
} // Ende der Klasse EineListe

Klasse MainTestListe

package s2.listen;

/**
*
* @author s@scalingbits.com
*/
public class MainTestListe {
/**
* Testroutinen für einfache Listen
* @param args
*/
public static void main(String[] args) {
EineListe testListe = new EineListe();
einfuegeTest(testListe, 4, 6);
System.out.println("Kontrolle: Drei Knoten von 4 bis 6");
einfuegeTest(testListe, 1, 3);
System.out.println("Kontrolle: Sechs Knoten von 1 bis 6");
einfuegeTest(testListe, 21, 27);
System.out.println("Kontrolle: 13 Knoten von 21 bis 27, 1 bis 6");
loeschenEndeTest(testListe, 3);
System.out.println("Kontrolle: 10 Knoten von 21 bis 27, 1 bis 3");
loeschenKopfTest(testListe, 8);
System.out.println("Kontrolle: 2 Knoten von 2 bis 3");
loeschenKopfTest(testListe, 3);
System.out.println("Kontrolle: 0 Knoten. Versuch löschen in leerer Liste");
enthaeltTest(testListe, 10);
System.out.println("Kontrolle: Einfügen in der Liste");
testListe = new EineListe();
einfuegeNachTest(testListe, 10);
}
/**
* Einfügen einer Reihe von Zahlen in eine gegebene Liste
* @param l Liste in die eingefügt wird
* @param min kleinster Startknoten der eingefügt wird
* @param max größter Knoten der eingefügt werden
*/
public static void einfuegeTest(EineListe l, int min, int max) {
System.out.println("Test: Einfügen am Kopf [" + min + " bis " + max + "]");
for (int i = max; i >= min; i--) {
l.einfuegeAnKopf(new Listenknoten(i));
System.out.println("Länge der Liste: " + l.laenge());
}
l.drucken();
}
/**
* Lösche eine bestimmte Anzahl von Knoten am Ende der Liste
* @param l Liste aus der Knoten gelöscht werden
* @param anzahl der zu loeschenden Knoten
*/
public static void loeschenEndeTest(EineListe l, int anzahl) {
System.out.println("Test: Löschen am Ende der Liste " + anzahl + "fach:");
for (int i = 0; i < anzahl; i++) {
l.loesche(l.ende);
System.out.println("Länge der Liste: " + l.laenge());
}
l.drucken();
}
public static void loeschenKopfTest(EineListe l, int anzahl) {
System.out.println("Test: Löschen am Kopf der Liste " + anzahl + "fach:");
for (int i = 0; i < anzahl; i++) {
l.loesche(l.getKopf());
System.out.println("Länge der Liste: " + l.laenge());
}
l.drucken();
}
public static void enthaeltTest(EineListe l, int groesse) {
System.out.println("Test: enhaelt() " + groesse + " Elemente");
Listenknoten[] feld = new Listenknoten[groesse];
for (int i = 0; i < groesse; i++) {
feld[i] = new Listenknoten(i * 10);
l.einfuegeAnKopf(feld[i]);
}
l.drucken();
for (int i = 0; i < groesse; i++) {
if (l.enthaelt(feld[0])) {
System.out.println("Element " + feld[i] + " gefunden");
}
}
System.out.println("Erfolg wenn alle Elemente gefunden wurden");
Listenknoten waise = new Listenknoten(4711);
if (l.enthaelt(waise)) {
System.out.println("Fehler: Element gefunden welches nicht zur Liste gehört!");
} else {
System.out.println("Erfolg: Element nicht gefunden welches nicht zur Liste gehört");
}
}
public static void einfuegeNachTest(EineListe l, int max) {
System.out.println("Test: einfügen nach " + max + "fach");
Listenknoten[] feld = new Listenknoten[max];
for (int i = 0; i < max; i++) {
feld[i] = new Listenknoten(i*10);
l.einfuegeAnKopf(feld[i]);
}
System.out.println("Länge der Liste: " + l.laenge());
for (int i = 0; i < max; i++) {
l.einfuegeNach(feld[i], new Listenknoten(feld[i].getWert()+1));
System.out.println("Länge der Liste: " + l.laenge());
}
l.einfuegeNach(l.ende, new Listenknoten(111));
l.drucken();
}
}

 

 

Lösungen

Doppelt verzeigerte Liste mit Referenz auf das Ende der Liste

Klasse EineListe

Hinweis: Ändern Sie den Namen von EineListeLoseung an den zwei Stellen zu EineListe.

package s2.listen;

/**
*
* @author s@scalingbits.com
*/
public class EineListeLoesung {
protected Listenknoten kopf;
protected Listenknoten ende;
public EineListeLoesung() {
kopf = null;
ende = null;
}
/**
* Berechnet die Anzahl der Listenelemente
* @return Anzahl der Listenelemente
*/
public int laenge() {
int laenge = 0;
Listenknoten zeiger = kopf;
while (zeiger != null) {
laenge++;
zeiger = zeiger.getNachfolger();
}
return laenge;
}
/**
* Liefert den Kopf der Liste oder einen Null Zeiger
* @return Zeiger auf Kopf der Liste
*/
public Listenknoten getKopf() {
return kopf;
}
/**
* Liefert das Ende der Liste oder einen Null Zeiger
* @return Zeiger auf das Ende der Lister
*/
public Listenknoten getEnde() {
return ende;
}
/**
* Drucke eine Liste alle Objekte auf der Konsole
*/
public void drucken() {
System.out.println("Länge Liste: " + laenge());
Listenknoten k = kopf;
while (k != null) {
System.out.println("Knoten: " + k);
k = k.getNachfolger();
}
}
/**
* Füge hinter dem Listenknoten "nach" den Knoten "k"ein.
* Füge nichts ein wenn der Listenknoten "nach" nicht in der Liste
* vorhanden ist
* @param nach
* @param k
*/
public void einfuegeNach(Listenknoten nach, Listenknoten k) {
Listenknoten t;
t = kopf; // Diese Variable wird über die Listenknoten laufen
while ((t != null) && (t != nach)) {
// Iteriere über die Liste solange Knoten existieren
// und kein passender gefunden hier
t = t.getNachfolger();
}
if (t == nach) { // Der Knoten wurde gefunden
// Merken des Nachfolger hinter der Einfuegestelle
Listenknoten derNaechste = nach.getNachfolger();
if (derNaechste != null) {
// Setzen des neuen Vorgängers falls es einen Nachfolger gab
derNaechste.setVorgaenger(k);
} else { // Wir haben am Ende eingefuegt. Ende-Zeiger korrigieren
ende = k;
}
// Der neu eingefügte Knoten soll auf den Nachfolger zeigen
k.setNachfolger(derNaechste);
// Der gesuchte Knoten ist der Vorgaenger. Der neue Knoten
// soll auf ihn zeigen
k.setVorgaenger(t);
// Der Vorgaenger soll auf den neu einfeügten Knoten zeigen
t.setNachfolger(k);
}
}
/**
* Füge einen Knoten am Anfang der Liste ein
* @param k
*/
public void einfuegeAnKopf(Listenknoten k) {
k.setVorgaenger(null);
if (kopf == null) { // Die Liste ist leer
ende = k; // Das Ende ist auch der Kopf
k.setNachfolger(null); // Sicherstellen das kein Nachfolger benutzt wird
} else { // Liste ist nicht leer
k.setNachfolger(kopf); // Neuer Nachfolger ist alter Kopf
kopf.setVorgaenger(k); // Alter Kopf bekommt Vorgaenger

}
kopf = k; // Es gibt einen neuen Kopf. Heureka
}

public void loesche(Listenknoten k) {
Listenknoten t = kopf; // Diese Variable wird über die Listenknoten laufen
if (kopf == null) {
System.out.println("Löschversuch auf leerer Liste");
} else {
//Pflege der Kopf- bzw Endezeiger
if (kopf == k) {
// Das Kopfelement wir geloescht
kopf = k.getNachfolger(); //Kann auch Null sein...
}
if (ende == k) {
// Das zu loeschende Objekt ist das Letzte
ende = k.getVorgaenger(); // Kann auch Null sein...
}
while ((t != null) && (t != k)) {
// Iteriere über Liste solange Nachfolger da sind
// und nichts passendes gefunden wird
t = t.getNachfolger();
}
if (t == k) { // Der Knoten wurde gefunden
Listenknoten nachf = k.getNachfolger();
Listenknoten vorg = k.getVorgaenger();
if (nachf != null) {
// Es gibt einen Nachfolger. Pflege dessen Vorgaenger
nachf.setVorgaenger(vorg);
}
if (vorg != null) {
// Es gibt einen Vorgaenger. Pflege dessen Nachfolger
vorg.setNachfolger(nachf);
}
// Entfernen aller Referenzen des geloeschten Objekts
t.setNachfolger(null);
t.setVorgaenger(null);
} // Ende der Knoten wurde gefunden
} // Ende Loeschen aus einer nicht leeren Liste
} // Ende Methode loesche

/**
* Ist wahr wenn ein Knoten mit dem gleichen Wert existiert
* @param k
* @return
*/
public boolean enthaelt(Listenknoten k) {
Listenknoten t = kopf;
boolean result = false;
while ((result == false) && (t != null)) {
result = (t == k);
if (!result) {
t = t.getNachfolger();
}
}
return result;
} // Ende Methode enhaelt()
} // Ende der Klasse EineListe