Java: Reihenfolge in einer Liste umdrehen

Eine beliebte Java-Programmieraufgabe ist es, die Reihenfolge einer gegebenen Liste umzudrehen. Die folgende Klasse erweitert die Klasse VerweisListe (ist hier nicht angegeben) um die Methoden umdrehen() und Object elem(int n). elem(int n) überschreibt die Methode elem() der Superklasse, die das aktuelle Listenobjekt zurückgibt.

/******************************  SuperListe.java  ******************************/

/**
 * Erweitet die Klasse VerweisListe um zwei nuetzliche Operationen.
 */

public class SuperListe extends VerweisListe {

  /**
   * Invertiert die Reihenfolge der Elemente in der Liste.
   */
  public void umdrehen() {
    Object zwischen = new Object();     // Zwischenspeicher
    int n = listenElemente();           // Anzahl der Listenelemente ermitteln.
    while(--n >= 0) {     // Beginnend beim vorletzten Element, Elemente zwischenspeichern,
                                     // loeschen und ans Ende haengen.
        zwischen = elem(n);     // Element von Position n zwischenspeichern.
        delete();                         // Element an Position n loeschen.
        endeSetzen();                // An das Listenende springen.
        insert(zwischen);           // Zwischengespeichertes Element ans Ende haengen.
    }    
  }
 
  /**
   * Springt auf das letzte Element der Liste.
   */
  private void endeSetzen() {
    while(!endpos())
        advance();
    } 
   
    /**
     * Zahl der Listenelemente ermitteln. Zaehlung beginnt bei 0.
     */
  private int listenElemente() {
    if(empty())
        throw new RuntimeException("Liste ist leer");
    int n = 0;
    reset();
    while(!endpos()) {
        advance();
        n++;
    }
    return n;
  }    

  /**
   * Liefert das Element an Stelle n.
   *
   * @param n der Index des zu liefernden Elementes, beginnend bei 0
   *
   * @return das Element an Stelle n
   *
   * @throws RuntimeException falls Liste weniger als n Elemente hat oder n < 0 ist
   */
  public Object elem(int n){
    if(n < 0 || listenElemente() < n)
        throw new RuntimeException("Ungueltiger Index");
    reset();                              // Auf Listenanfang springen.
    for(int i = 0; i < n; i++)    // An Auslesestelle springen.
        advance();
    return super.elem();          // Element zurueckgeben.
  }
}

/*************************************************************************/

Methoden der Superklasse:

• advance() wählt das nächste Listenelement aus.
• reset() wählt das erste Listenelement aus.
• boolean empty() ist true, wenn die Liste leer ist.
• boolean endpos() ist true, wenn das Ende der Liste erreicht wurde.
• Object elem() liest das Objekt an der aktuellen Listenposition aus.

Private Methoden:

• endeSetzen() wählt das letzte Element der Liste aus.
• int listenElemente() ermittelt die Anzahl der Listenelemente und gibt sie zurück. Dabei beginnt die Zählung bei 0: Der Wert 0 bedeutet also, dass 1 Element in der Liste ist. Wenn die Liste leer ist, wird eine RuntimeException geworfen.

Object elem(int n):

Die Methode gibt das Element an der Stelle n zurück. Zunächst wird geprüft, ob ein gültiger Wert n übergeben wurde. Wenn n kleiner 0 oder größer als die Anzahl der Listenelemente ist, wird eine RuntimeException geworfen.

Mit reset() wird das erste Listenelement angesteuert. In der For-Schleife wird advance() solange aufgerufen, bis das n-te Element erreicht ist. Mit dem Aufruf von elem() aus der Superklasse wird das Element zurückgegeben.

umdrehen():

Zunächst wird ein Objekt zwischen erzeugt, das jeweils das Element der Liste aufnimmt, das umgespeichert werden soll. n enthält die Position des umzuspeichernden Listenelements.

Beginnend mit dem (n - 1)-ten Element werden in der While-Schleife zunächst jeweils zwischengespeichert. dann gelöscht und schließlich am Ende der Liste wieder eingefügt. Damit mit dem (n - 1)-ten Element begonne wird, muss man im Schleifenkopf --n schreiben (anstatt n--). Bei --n wird zuerst n dekrementiert und anschließen auf <= 0 geprüft. Gleichzeitig wird damit erreicht, dass die While-Schleife nicht durchlaufen wird, wenn die Liste nur ein Element enthält.