Sortierte Liste für String-Objekte

Die Sortierte Liste ist ein häufig verwendete Variante der einfachen Liste, in der Elemente nach einem festgelegtem Ordnungkriterium an die "richtige" Stelle eingefügt werden. Beispielsweise ließe sich so eine aufsteigend alphabetisch geordnete Liste mit Nachnamen anlegen. Als Speicherstruktur soll eine einfache Liste zum Einsatz kommen, in die der Benutzer aber nur über eine neu zu definierende Methode sl_insert() einfügen kann. Diese Methode muss dafür sorgen, dass an der richtigen Stelle eingefügt wird. Wir realisieren den ADT Sortierte Liste der Einfachheit halber zunächst nur für String-Objekte, können also nur Zeichenketten einspeichern.

public class SortierteListe {

  // DATENFELD
  private Liste l;

  // KONSTRUKTOR
  public SortierteListe(){
    l = new ZeigerListe();
  }

  // METHODEN
  public void sl_insert(String s){
    l.reset();
    while(!l.endpos() && s.compareToIgnoreCase((String)l.elem())>0){
      l.advance();
    }
    l.insert(s);
  }

  public void sl_print(){
    l.reset();
    while (!l.endpos()) {
      System.out.println(l.elem());
      l.advance();
    }
  }

}

An dieser Klasse ist einiges bemerkenswert: Das Datenfeld l ist vom Typ Liste, wobei Liste ja ein Interface ist. Diese Form der Deklaration legt lediglich fest, dass l von einem Datentyp sein muss, der das Interface Liste implementiert hat. Es bleibt offen, welche Implementation genutzt wird. Im Konstruktor legen wir uns dann auf die ZeigerListe fest, könnten uns aber auch für die ArrayListe entscheiden, wenn wir sie denn programmiert hätten.

Innerhalb der Methode sl_insert müssen wir nach der passenden Einfüge-Stelle suchen. Für den lexikographischen Vergleich von zwei Strings wird hier die Methode compareToIgnoreCase genutzt. Diese Methode gehört zur Klasse String und gibt einen ganzzahligen Wert größer Null zurück, wenn dass die Methode aufrufende String-Objekt (hier s) lexikographisch hinter bzw. nach dem als Argument übergebenen String-Objekt einzuordnen ist. Im umgekehrten Fall wird ein Wert kleiner Null, bei Gleichheit Null zurückgegeben. Innerhalb der while-Schleife wird solange vorgerückt, bis man entweder das Ende der Liste erreicht hat oder aber an der richtigen Einfüge-Stelle angekommen ist.

Ein kleines Hauptprogramm testet die Sortierte Liste.

public static void main(String[] args) {

  SortierteListe liste = new SortierteListe();

  liste.sl_insert("Kiewidt");
  liste.sl_insert("Blanke");
  liste.sl_insert("Meyer");
  liste.sl_insert("Rolfes");
  liste.sl_insert("Fulge");

  liste.sl_print();

}

Sortierte Liste für ObjekteMitOrdnung

Unsere Sortierte Liste arbeitet nun einwandfrei mit String-Objekten. Lieber wäre es uns, wenn sie wie unsere bisherigen ADTs mit beliebigen Objekten arbeiten würde. Wir müssen allerdings verlangen, dass für die verwendeten Objekte eine Ordnungsrelation existiert, da man sie sonst nicht in einer Reihenfolge anordnen kann. Für diese Bedingung formulieren wir ein neues Interface, dass Klassen, deren Objekte in die Sortierte Liste wollen, implementieren müssen. Die Methode compareTo soll einen Größenvergleich zweier in die Liste einzuspeichernder Elemente ermöglichen. (Mit Hilfe der Methode print sollen Objektinformationen auf der Konsole ausgegeben werden.)

public interface ObjektMitOrdnung {

  public int compareTo(Object o);

  public void print();

}

Und jetzt kommt der Clou: Innerhalb der oben geschriebenen Methode sl_insert ersetzen wir String einfach durch ObjektMitOrdnung! Aus compareToIgnoreCase wird die in unserem Interface definierte Methode compareTo. Der Parameter x ist vom Typ ObjektMitOrdnung, also von irgendeinem Datentyp, der das ObjektMitOrdnung Interface implementiert hat. So haben wir sichergestellt, dass das Objekt x auch die Methode compareTo kennt, ohne das wir uns auf einen bestimmten Datentyp festlegen müssen.

  public void sl_insert(ObjektMitOrdnung x){
    l.reset();
    while(!l.endpos() && x.compareTo(l.elem())>0){
      l.advance();
    }
    l.insert(x);
  }

» drucken: pdf | html