Trennung von Struktur und Daten

Im vorhergehenden Kapitel haben Sie eine Warteschlangen-Implementierung kennengelernt, bei der der Code zur Verwaltung der Listenstruktur mit dem Code zur Verwaltung der Daten vermischt war. Wir werden jetzt Struktur und Daten sauber trennen, so dass der Code zur Verwaltung der Listenstruktur besser wiederverwendbar wird.

Die Lösungsidee besteht darin, jedes Datenobjekt in ein Objekt einer neuen Klasse Knoten zu "verpacken", das neben dem (Verweis auf das) Datenobjekt auch einen Verweis auf denjenigen Knoten enthält, der den Verweis auf den Nachfolger des aktuellen Inhaltsobjekts beinhaltet. "Einfach verkettet" ist diese Liste übrigens insofern, als die Knoten keinen Verweis auf ihre Vorgänger-Knoten beinhalten (das wäre dann eine "doppelt verkettete Liste").

Beispielhaftes Objektdiagramm

Klassendiagramm

Umsetzung in Java

Die Klasse Inhalt

Die Klasse Kunde muss für die Speicherung in der Warteschlange überhaupt nicht mehr angepasst werden:

class Kunde {
   String name;
 
   Kunde(String name) {
      this.name = name;
   }
}

Sehen wir uns bei den Klassen Warteschlange und Knoten zunächst nur ihre Attribute an:

public class Warteschlange {
    private Knoten erster;
 
}
 
public class Knoten {
    private Knoten nachfolger;
    private Inhalt inhalt;
 
    public Knoten(Inhalt inhalt){
       this.inhalt = inhalt;
    }
}

Die Klasse Warteschlange übernimmt in dieser Konstellation die "Kommunikation" mit dem Nutzer der Warteschlange. Der Nutzer ruft weder Methoden der Klasse Knoten direkt auf noch "weiß" er von deren Existenz.

Die Warteschlange setzt damit das Prinzip der Trennung von Struktur und Inhalt um, d.h. bei der Verwendung der Struktur (hier: Warteschlange bzw. Liste) sind keinerlei Änderungen an der Klasse Kunde notwendig.

Damit die Warteschlange auf die Knoten geeignet zugreifen kann, benötigt die Klasse Knoten Methoden zum Holen und Setzen der Nachfolger-Referenz (sog. Getter- und Setter-Methoden):

   Knoten getNachfolger() {
      return nachfolger;
   }
 
   void setNachfolger(Knoten nachfolger) {
      this.nachfolger = nachfolger;
   }
 
   Kunde getDaten() {
      return daten;
   }

Die Methode erstenEntnehmen der Warteschlange kann damit folgendermaßen umgesetzt werden:

   Kunde erstenEntnehmen() {
      Knoten erster = anfang;
      anfang = erster.getNachfolger();
      return erster.getDaten();
   }

Kaum schwerer ist das Anfügen neuer Knoten am Ende der Warteschlange:

   void hintenAnstellen(Kunde kunde) {
      if(anfang == null) {
         anfang = new Knoten(kunde);
         ende = anfang;
         return;
      }
 
      Knoten neuerKnoten = new Knoten(kunde);
      ende.setNachfolger(neuerKnoten);
      ende = neuerKnoten;
 
   }

Die Ermittlung der Anzahl der enthaltenen Elemente kann sowohl iterativ als auch rekursiv gelöst werden:

Anzahl der enthaltenen Elemente: iterativ

Klasse Warteschlange:

public int getAnzahlIterativ() {
   if(anfang == null) {
      return 0;
   }
 
   int anzahl = 1;
   Knoten aktuellerKnoten = erster;
   while(aktuellerKnoten.getNachfolger() != null) {
      aktuellerKnoten = aktuellerKnoten.getNachfolger();
      anzahl++;
   }
 
   return anzahl;
}

Anzahl der enthaltenen Elemente: rekursiv

Hier kümmert sich die Methode getAnzahlRekursiv der Klasse Warteschlange selbst wieder nur um den trivialen Fall (erster == null, also Anzahl == 0) und "fragt" im nichttrivialen Fall beim ersten Knoten nach: Klasse Warteschlange:

   int getAnzahlRekursiv() {
      if(anfang == null) return 0;
      return anfang.getAnzahlRekursiv();
   }

Klasse Knoten:

   int getAnzahlRekursiv() {
      if(nachfolger == null) return 1;
      return nachfolger.getAnzahlRekursiv() + 1;
   }

Sequenzdiagramm am Beispiel einer Warteschlange mit drei Knoten:

Gesamtprogramm

Aufgabe 1:

Erweitere die Klasse Warteschlange um eine Methode gibDenNtenWertZurück(int n), die den Inhalt des n-ten Elements der Warteschlange zurückgibt.

Lösung

Aufgabe 2:

Erweitere die Klasse Warteschlange um eine Methode letztesElementLoeschen(), die das letzte Element der Warteschlange löscht.

Lösung