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