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

Warum werden die Methoden in EineListe und nicht in ListenKnoten implementiert? Am Anfang gibt es keine Liste mit Knoten In EineListe muß der Kopf und das Ende gepflegt werden. Hier können Änderungen bei fast allen Operationen notwendig werden. Die Liste kann über Zeiger an die Knoten kommen. Die Knoten wissen aber nicht zu welcher Liste sie gehören.

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();
   }
}

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