12 Zustände und Listen

In diesem Kapitel lernen wir zunächst das wichtige Konzept von Zustandsmaschinen kennen. Damit können wir besser und übersichtlicher verschiedene Game-Screens und Nichtspieler-Charaktere programmieren. In diesem Zusammenhang lernen wir auch die switch-Anweisung kennen, eine Art spezielles If für Fallunterscheidungen. Wir verwenden Konstanten, um unsere Zustände zu benennen.

Anschließend lernen wir Listen kennen, das sind die besseren Arrays. Man kann dort beliebig Elemente hinzufügen und entfernen. Die For-each-Schleife erlaubt ein elegantes Durchlaufen von Listen. Um Zahlen aufzulisten benötigen wir allerdings Wrapperklassen, aber eins nach dem anderen...

12.1 Zustandsmaschinen

In der theoretischen Informatik werden sogenannte Endliche Automaten (auch Zustandsmaschinen genannt) eingesetzt, um Beweise darüber zu führen, welche Probleme mit welchen Mechanismen in welcher Zeit lösbar sind.

In der Praxis werden Zustandsmaschinen eingesetzt, um einfaches Verhalten zu programmieren. Ein gewünschtes Verhalten wird zunächst als Zustandsmaschine entworfen, man sagt auch "modelliert", und anschließend in Code übersetzt. Der resultierende Code ist oft verständlicher und besser erweiterbar als Code, der ohne eine solche Vorplanung geschrieben wird.

Eine Zustandsmaschine besteht aus Punkten (Zustände) und Pfeilen (Übergänge). Die Pfeile stehen für Ereignisse (events) oder Aktionen. Die Maschine befindet sich in einem der Zustände und geht über einen Pfeil in einen anderen Zustand über, sofern das Ereignis oder die Aktion des Pfeils ausgelöst wird.

Ein Video-Player lässt sich als Zustandsmaschine modellieren: Zu Beginn ist der Player im Zustand "Video läuft nicht". Sobald die Play-Taste gedrückt wird, geht der Player in den Zustand "Video läuft" über. Wenn die Pause-Taste gedrückt wird, geht der Player wieder in den Zustand "Video läuft nicht" über.

Zustand mit boolescher Variable repräsentieren

Schauen wir uns ein Code-Beispiel an. Statt eines Videoplayers nehmen wir einen Ball, der von links nach rechts und zurück fliegt. Auch der Ball kann zwei Zustände haben: (1) fliegen und (2) stehen. Wenn Sie die Leertaste drücken, steht der Ball (Pause). Wenn Sie die Enter-Taste drücken, fliegt der Ball weiter (Play).

Das Basisprogramm lässt den Ball hin und her laufen:

int x = 0;
int speed = 1;

void draw() {
  background(100);
  noStroke();
  ellipse(x, height/2, 30, 30);
  x = x + speed;
  if (x < 0 || x > width) {
    speed = -speed;
  }
}

Da wir nur zwei Zustände haben, merken wir uns den Zustand in einer booleschen Variable "play". Wenn die Variable true ist, ist der Zustand "play". Wenn sie false ist, ist der Zustand "pause". Der Übergang in einen anderen Zustand wird durch den jeweiligen Tastendruck ausgelöst.

int x = 0;
int speed = 1;
boolean play = true;

void draw() {
  background(100);
  noStroke();
  ellipse(x, height/2, 30, 30);

  // Was im Zustand "play" gemacht werden soll:
  if (play) {
    x = x + speed;
    if (x < 0 || x > width) {
      speed = -speed;
    }
  }
}

void keyPressed() {

  // Was im Zustand "play" für ein Übergang erlaubt ist
  if (play) {
    if (key == ' ') {
      play = false; // Gehe über zu "pause"
    }
  }
  else {
    // Was im Zustand "pause" für ein Übergang erlaubt ist
    if (keyCode == ENTER) {
      play = true; // Gehe über zu "play"
    }
  }
}

(interaktives Feld, Sie müssen auf das Feld klicken, damit ihre Tastendrücke erkannt werden)

Beachten Sie, dass der Ball in jedem der Zustände andere Tasten annimmt. Der Ball nimmt sozusagen eine "andere Persönlichkeit" an, sobald er sich in einem anderen Zustand befindet. Im Code sind die Zustände klar ersichtlich.

Wir unterscheiden dabei, wie der Zustand (play vs. pause) verwirklich wird - dies steht in draw() - und wie der Übergang geregelt wird - dies steht in keyPressed() (bzw. allgemein: im interaktiven Teil des Programms).

Zustand als Zahl

Aber was, wenn wir mehr als zwei Zustände haben? Dann ist es mit einer booleschen Variable nicht getan, denn die kann nur zwei Werte annehmen. Stattdessen nehmen wir eine Integer-Variable, dann können wir eine große Menge Zustände speichern, jeder Zustand bekommt eine eigene Zahl. Wir schreiben unser Beispiel von oben so um, dass eine Zahl den Zustand speichert. Die 0 steht für Zustand "play", die 1 für Zustand "pause".

int x = 0;
int speed = 1;
int state = 0; // 0: play, 1: pause

void draw() {
  background(100);
  noStroke();
  ellipse(x, height/2, 30, 30);

  // Was im Zustand "play" gemacht werden soll:
  if (state == 0) {
    x = x + speed;
    if (x < 0 || x > width) {
      speed = -speed;
    }
  }
}

void keyPressed() {

// NEU: Die switch-Anweisung

switch (state) {

  case 0:
    if (key == ' ') {
      state = 1; // Gehe über zu "pause"
    }
    break;

  case 1:
    if (keyCode == ENTER) {
      state = 0; // Gehe über zu "play"
    }
    break;
  }
}

Fallunterscheidung mit Switch

Sie sehen hier ein neues Konstrukt von Processing/Java: die Switch-Anweisung. Eine Switch-Anweisung ist eine Fallunterscheidung, wie Sie sie normalerweise mit If erledigen würden. Sie geben dem Switch eine Variable (hier: state) und listen dann mit case (engl. für "Fall") auf, welche Code-Teile ausgeführt werden sollen, wenn die Variable den Wert 0 bzw. 1 enthält. Jeder Code-Teil muss mit break abgeschlossen werden, ansonsten würde der darunterliegende Code auch ausgeführt werden (wenn wir z.B. das erste break im Code oben weglassen, dann wird im Fall von 0 erst der Code unter "case 0" ausgeführt und anschließend der Code von "case 1"). Das zweite break könnte man auch weglassen, da darunter kein Code mehr folgt, man schreibt es aber dennoch, falls man das Switch später um einen weiteren Fall erweitert.

Neben den "case"-Optionen gibt es noch das default . Der Code hier wird ausgeführt, wenn keiner der anderen Fälle greift. Im Beispiel könnte man den Fall abfangen, dass state einen falschen Wert (also nicht 0 oder 1) enthält.

void keyPressed() {

  switch (state) {

  case 0:
    if (key == ' ') {
      state = 1; // Gehe über zu "pause"
    }
    break;

  case 1:
    if (keyCode == ENTER) {
      state = 0; // Gehe über zu "play"
    }
    break;

  default:
    println("Unbekannter Zustand: " + state);
  }
}

Die allgemeine Form der Switch-Anweisung ist

switch (<VARIABLE>) {

  case <WERT 1>:
    ...
    break;

  case <WERT 2>:
    ...
    break;

  ...

  case <WERT N>:
    ...
    break;

  default:
    ...
  }
}

Es können natürlich beliebig viele Fälle unterschieden werden. Das default am Ende kann weggelassen werden, ist also optional.

Zustandsmaschinen in Spielen

In Spielen werden Zustandsmaschinen z.B. eingesetzt, um Nichtspielercharaktere (NSC) zu steuern. Bei einem einfachen Shooter könnte ein NSC wie folgt modelliert werden:

Hier kann man sich vorstellen, dass der NSC in jedem Zustand ein komplett anderes Verhalten zeigt, also eine andere "Persönlichkeit" annimmt.

Wenn wir in Processing unserem Ball eine "andere Persönlichkeit" je nach Zustand geben wollen, ändern wir einfach seine Form zu Quadrat und Dreieck. Den Zustand schalten wir mit der Leertaste von 0 zu 1 zu 2 und wieder zu 0.

int x = 0;
int speed = 1;
int state = 0; // 0: circle, 1: square, 2: triangle

void draw() {
  background(100);
  noStroke();
  rectMode(CENTER);

  switch (state) {
    case 0:
      ellipse(x, height/2, 30, 30);
      break;
    case 1:
      rect(x, height/2, 30, 30);
      break;
    case 2:
      triangle(x - 15, height/2 + 15,
      x, height/2 - 15,
      x + 15, height/2 + 15);
      break;
  }

  x = x + speed;
  if (x < 0 || x > width) {
    speed = -speed;
  }
}

void keyPressed() {
  if (key == ' ') {
    state++;
    if (state > 2) {
      state = 0;
    }
  }
}

In Spielen wird das Zustandskonzept auch verwendet, um zwischen verschiedenen "Modi" oder "Screens" zu unterscheiden. Nehmen wir an, bei unserem langweiligen "Ballspiel" ist das Spiel vorbei, sobald der Ball 3x die Wand berührt.

Dann unterscheiden wir drei Spielzustände:

1. play
2. pause
3. game over

Probieren Sie es aus:

Beachten Sie zum Beispiel, dass Sie im Spiel (play) die Leertaste verwenden können, um es zu pausieren. Im Zustand Game Over hingegen hat die Leertaste keine Funktion. Solche Unterschiede lassen sich mit der gezeigten Methode (Zustand als Integer, Fallunterscheidung mit Switch) leicht und vor allem verständlich realisieren.

int x = 0;
int speed = 1;
int counter = 0; // Wie oft Ball gegen Wand
int state = 0; // 0: play, 1: pause, 2: game over

void draw() {
  background(100);
  noStroke();
  ellipse(x, height/2, 30, 30);

  // Steuert Verhalten im Zustand

  switch (state) {

    case 0:
      x = x + speed;
      if (x < 0 || x > width) {
        speed = -speed;
        counter++;
        if (counter > 2) {
          state = 2; // Gehe zu "game over"
        }
      }
      break;

    case 2:
      background(0);
      textAlign(CENTER);
      textSize(14);
      text("Game Over\n(press ENTER)", width/2, height/2);
      break;
    }
  }

// Steuert Übergange
void keyPressed() {

  switch (state) {

    case 0:
      if (key == ' ') {
        state = 1; // Gehe über zu "pause"
      }
      break;

    case 1:
      if (keyCode == ENTER) {
        state = 0; // Gehe über zu "play"
      }
      break;

    case 2:
      if (keyCode == ENTER) {
        counter = 0;
        state = 0; // Gehe über zu "play"
      }
      break;
  }
}

Konstanten

Ein unschöner Aspekt unserer bisherigen Methodik ist die Tatsache, dass Zahlen nicht sehr aussagekräftig sind. Bedeutet 0 jetzt Play oder Pause? Beginnt unsere Zustandszählung bei 1 oder bei 0?

Am liebsten würden wir unseren Zuständen Namen geben! Wir könnten doch für jeden Zustand eine Variable definieren, die die Zustandszahl enthält und einen aussagekräftigen Namen hat, also zum Beispiel:

int play = 0;
int pause = 1;

Prinzipiell eine gute Idee, aber theoretisch könnte man diese Variablen auch im Programmcode ändern (z.B. indem man play = 42 schreibt). Nun erlaubt Processing/Java, dies zu verbieten, indem man ein final vor die Variablendeklaration setzt. Dies ist dann eine Konstante.

Wichtig: Der Name einer Konstanten wird üblicherweise in GROSSBUCHSTABEN geschrieben. Wenn Ihre Namen aus mehreren Teilwörtern bestehen, verwenden Sie den Unterschrich zur Trennung, z.B. MOVE_UP oder LEVEL_ONE.

In unserem Beispiel:

// Zustände als Konstanten

final int PLAY = 0;
final int PAUSE = 1;

Wenn Sie jetzt versuchen, an einer anderen Stelle im Code die Variable PLAY auf einen neuen Wert zu setzen, bekommen Sie eine Fehlermeldung, denn Java besteht darauf, dass der Wert konstant bleibt.

Jetzt können wir die Konstanten einbauen. Dank der Konstanten wird der Code praktisch selbsterklärend.

final int PLAY = 0;
final int PAUSE = 1;
int x = 0;
int speed = 1;
int state = PLAY;

void draw() {
  background(100);
  noStroke();
  ellipse(x, height/2, 30, 30);

  // Was im Zustand "play" gemacht werden soll:
  if (state == PLAY) {
    x = x + speed;
    if (x < 0 || x > width) {
      speed = -speed;
    }
  }
}

void keyPressed() {
  switch (state) {

    case PLAY:
      if (key == ' ') {
        state = PAUSE;
      }
      break;

    case PAUSE:
      if (keyCode == ENTER) {
        state = PLAY;
      }
      break;
  }
}

Sie kennen übrigens bereits einige Konstanten. Wenn Sie schreiben rectMode(CENTER), ist CENTER eine Konstante, welche die Processing-Macher definiert haben. Sie können das testen:

println(CENTER);

3

Konstanten haben hier den Vorteil, dass Sie sich nicht merken müssen, dass ausgerechnet die "3" für das Zentrieren steht. Und - vielleicht noch wichtiger - wenn sich die Processing-Macher mal entscheiden sollten, dass jetzt die "5" für das Zentrieren steht, müssen Sie Ihren Code nicht ändern.

Auch bei Tastaturabfragen wie if (keyCode == LEFT) haben Sie Konstanten wie LEFT, welche den Tastencode (ganze Zahl) der Cursortaste-links enthält.

int zahl = 3;

12.2 Listen im Eigenbau

Listen sind so ähnlich wie Arrays. Der große Nachteil eines Arrays ist, dass man seine Länge nicht ändern kann. Bei Listen ist das anders. In diesem Abschnitt sehen wir uns an, wie man eine Liste selbst implementiert, um uns die interne Funktionsweise von Listen klar zu machen.

Klassen und Objekte im Diagramm

Ein kurzer Ausflug vorab: Um Klassen und Objekte grafisch darzustellen, gibt es sogenannte Klassen- und Objektdiagramme.

Klassendiagramm

Ein Klasse wird als gelber Kasten dargestellt, der drei Bereiche hat. Ganz oben steht der Klassennamen, in der Mitte alle Instanzvariablen und unten die Methoden - also in der gleichen Reihenfolge wie im Code.

Schauen wir uns eine konkrete Klasse "Person" an:

Randbemerkung: Die Instanzvariablen und Methoden werden normalerweise nicht wie hier "Java-Code-ähnlich" hingeschrieben, sondern etwas anders. Wir machen es dennoch, weil es so für Sie leichter zu lesen ist.

Klassendiagramme enthalten i.d.R. mehrere Klassen und sollen u.a. die Beziehungen zwischen den Klassen darstellen. Das wird erst im nächsten Kapitel wirklich relevant.

Objektdiagramm

Aus einer Klasse können wir beliebig viele Objekte erzeugen, indem wir die Klasse instanziieren. Diese konkreten Objekte wollen wir auch darstellen, wobei wir uns immer bewusst sein müssen, dass Objekte etwas anderes sind als Klassen. Es gibt z.B. genau eine Klasse Person, aber potenziell viele Objekte vom Typ Person.

Objekte werden als Boxen mit runden Kanten dargestellt. Ganz oben steht der Typ des Objekts (also die Klasse, aus der dies Objekt instanziiert wurde) und darunter stehen alle Instanzvariablen und die aktuellen Werte.

Stellen wir z.B. zwei Person-Objekte her, könnten diese so aussehen:

Objektdiagramme setzt man ein, um die Entwicklung der Werte darzustellen oder - noch wichtiger - die Beziehungen zwischen den Objekten. Eine "Beziehung" tritt dann auf, wenn eine Instanzvariable eines Objekts auf ein anderes Objekt "zeigt".

Vorüberlegungen

Überlegen wir uns nochmal kurz, wie Arrays funktionieren. Ein Array muss zunächst mal erzeugt werden. Dabei werden zwei Dinge festgelegt: die Länge des Arrays und der Typ der Elemente (hier: String). Sie können in diesem Array also keine Zahlen und keine Objekte vom Typ Person oder Spaceship ablegen. Nur Strings!

String[] namen = new String[3];

Das Befüllen des Arrays findet über Indices statt:

namen[0] = "Superman";
namen[1] = "Batman";
namen[2] = "Catwoman";

Werden die Element gebraucht, läuft man oft mit einer For-Schleife durch alle Indices und holt sich mit namen[i] die Elemente.

for (int i = 0; i < namen.length; i++) {
  println(namen[i]);
}

Für unsere Listen wünschen wir uns ähnliche Funktionen: Liste herstellen, Liste befüllen, auf Elemente zugreifen (über einen Index).

Einfach verkettete Liste

Die Grundidee einer sogenannten einfach verketteten Liste ist die einer Eisenbahn: jedes Element der Liste wird "eingepackt" in einen Waggon und die Waggons hängen aneinander.

Ein "Waggon" ist ein Objekt mit zwei Eigenschaften (Instanzvariablen):

• Inhalt: ein String, eine Zahl oder ein anderes Objekt (Person, Spaceship etc.)
• Verweis auf den nächsten Waggon

Die "Lokomotive" ist ein Objekt, das die Liste als ganzes repräsentiert. Dies Objekt muss lediglich auf das erste Listenelement verweisen. Als Objektdiagramm sieht unsere Listen wie folgt aus:

Wir formulieren zunächst die "Waggons" als Klasse. Diese Klasse erzeugt also Objekte, die ein einzelnes Listenelement repräsentieren. Nennen wir die Klasse also ListItem mit zwei Instanzvariablen:

Der Inhalt (content) wird in einer Variablen vom Typ Object gespeichert. Dies erlaubt uns, beliebige Objekte (String, Person, Spaceship etc.) dort zu speichern. Warum das funktioniert, erfahren wir in einem späteren Kapitel mit dem Thema "Klassenhierarchie".

In next wird ein Verweis auf das nächste Listenelement gespeichert oder null, wenn es keines gibt (d.h. dies ist das letzte Element).

Wir setzen das next zunächst auf null (d.h. es gibt anfangs keinen Nachfolger) und spendieren unserer Klasse gleich einen Konstruktor:

class ListItem {
  Object content; // Inhalt, z.B. String
  ListItem next = null; // nächstes Element

  // Konstruktor
  ListItem(Object x) {
    content = x;
  }
}

Ein frisch erzeugtes Objekt könnte so aussehen:

Als nächstes müssen wir noch die Liste als Ganzes repräsentieren. Dazu erstellen wir eine eigene Klasse MyList, die lediglich auf das erste Element zeigen muss - oder auf null, wenn die Liste leer ist.

class MyList {
  ListItem first = null; // erstes Element oder null
}

Diese Klasse erlaubt es uns auch, alle Methoden unterzubringen, die man sich so wünschen würde:

• add: Element hinzufügen
• printAll: alle Elemente ausgeben
• get: Element abfragen
• remove: Element löschen

Ein neues Listenobjekt, das noch keine Elemente hat, sieht so aus (eine Lokomotive ohne Waggons):

Beginnen wir mit add, um unsere Liste befüllen zu können. Wenn wir ein neues Element hinzufügen, erzeugen wir ein ListItem Objekt und hängen es hinten an die Liste an.

Wir erzeugen also ein neues ListItem-Objekt mit dem entsprechenden Inhalt (hier: x). Ganz zu Beginn ist die Liste leer, d.h. wir setzen einfach first auf das neue Objekt:

void add(Object x) {
  ListItem li = new ListItem(x);

  if (first == null) {
    // Fall 1: dies ist das erste Element überhaupt
    first = li;

  } else {
    // TODO
  }
}

Für den Fall, dass die Liste nicht leer ist, müssen wir zunächst das letzte Element suchen, und den Zeiger next dieses letzten Elements auf das neu erzeugte ListItem-Objekt setzen:

Dazu schreiben wir eine neue Hilfsmethode getLastItem, die das für uns erledigt:

ListItem getLastItem() {
  // zur Sicherheit: Liste darf nicht leer sein
  // ... sonst bekommen Sie unten bei item.next einen Fehler!
  if (first == null) {
    return null;
  }

  // Schleife: solange Nachfolger vorhanden,
  // gehe zum Nachfolger

  ListItem item = first; // beginne beim ersten Item

  // Hat das Item einen Nachfolger... ?
  while (item.next != null) {
    item = item.next; // ... dann gehe zum Nachfolger
  }

  // Dieses Item hatte keinen Nachfolger
  // => muss das letzte sein
  return item;
}

Jetzt können wir add vervollständigen: Wir lassen uns das letzte Element raussuchen und hängen an das next dieses letzten Elements unser neues Element:

void add(Object x) {
  ListItem li = new ListItem(x);

  if (first == null) {
    // Fall 1: dies ist das erste Element überhaupt
    first = li;

  } else {

    // Fall 2: es gibt bereits Elemente
    ListItem last = getLastItem();
    last.next = li;

  }
}

Eine Liste baut sich also wie folgt auf:

Wenn wir alle Listenelemente auf der Konsole drucken wollen, verwenden wir wieder eine While-Schleife. Wir benutzen außerdem einen Zähler, um die Elemente durchzunumerieren. Als gute Informatiker beginnen wir bei Null, wenn wir zählen. Ähnlich wie bei Arrays sprechen wir auch vom Index eines Listen-Elements.

void printAll() {
  ListItem item = first;
  int counter = 0;
  while (item != null) {
    println(counter + ": " + item.content);
    item = item.next;
    counter++;
  }
}

Um unsere Liste zu testen, können wir jetzt die Liste befüllen und ausdrucken:

void setup() {
  MyList list = new MyList();
  list.add("Superman");
  list.add("Batman");
  list.add("Catwoman");
  list.printAll();
}

0: Superman
1: Batman
2: Catwoman

Jetzt möchten wir auf beliebige Elemente der Liste zugreifen. Dazu verwenden wir den Index eines Elements, also Null für das erste Element, 1 für das zweite, 2 für das dritte usw.

Zunächst stellen wir sicher, dass kein Unfug getrieben wird (negativer Index) und dass die Liste nicht leer ist. In diesen Fällen geben wir null zurück.

Object get(int index) {
  if (first == null || index < 0) {
    return null;
  }
  // TODO
}

Jetzt können wir mit Hilfe einer For-Schleife so oft zum jeweils nächsten Element springen, wie uns der Index vorgibt. Wir müssen natürlich die Möglichkeit in Betracht ziehen, dass der Index größer ist als die Liste (Fehler des Programierers), also testen wir jedes Mal, ob es überhaupt einen Nachfolger gibt:

Object get(int index) {
  if (first == null || index < 0) {
    return null;
  }

  // For-Schleife: springe so oft zum Nachfolger,
  // wie der Index vorgibt

  ListItem li = first; // beginne beim ersten Element

  for (int i = 0; i < index; i++) {

    // Prüfe, ob es überhaupt einen Nachfolger gibt
    if (li.next != null) {
      li = li.next;
    } else {
      // wenn nicht, war der Index zu groß
      // gibt null zurück
      return null;
    }
  }

  // gibt den Inhalt des gefundenen Elements zurück
  return li.content;
}

Die Methoden zum Feststellen der Größe einer Liste (size()) und zum Löschen eines Elements (remove(int index)) sollten Sie als Übung selbst versuchen zu implementieren.

Unterschiede: Liste vs. Array

Listen haben in modernen Hochsprachen die Arrays weitestgehend ersetzt. Dennoch finden Sie immer noch Arrays sowohl in alten wie auch in neuen Sprachen. Warum eigentlich? Der Grund ist, dass Arrays sehr sehr efffizient sind.

Ein Array wird hintereinander weg im Speicher abgelegt. Da der Typ der Elemente von Beginn an klar ist, kennt Java die notwendige Speichergröße pro Element. Da auch die Länge des Arrays von Beginn an klar ist, wird einfach ein zusammenhängender Speicherbereich von (Größe x Länge) reserviert. Wenn jetzt Element mit Index N gesucht wird, muss Java nur Startadresse + N * Größe rechnen, um das entsprechende Element zu finden.

Im Vergleich dazu muss bei einer einfach verketteten Liste beim get() eine Schleife durchlaufen werden. Beim 1000-sten Element sind das 1000 Operationen. Im Vergleich muss beim Array eine einzige Operation (obige Formel) durchgeführt werden.

Es gibt allerdings auch alternative Listen-Implementierungen. Statt der einfach verketteten Liste kann man sich auch vorstellen, intern einen Array zu erstellen, der zu Beginn eine bestimmte Größe hat (z.B. 100 Elemente). In der Klasse merkt man sich einfach die Anzahl der besetzten Zellen, z.B. mit currentSize.

class MyArrayList {
  Object[] content = new Object[100];
  int currentSize = 0;
}

Beim add() verwendet man die Zahl currentSize, um das "letzte" Element zu besetzen:

void add(Object x) {
  content[currentSize] = x;
  currentSize++;
}

Beim get() greift man auf die entsprechende Zelle im Array zu. Ein printAll() bekommt man auch schnell hin:

Object get(int index) {
  return content[index];
}

void printAll() {
  for (int i = 0; i < currentSize; i++) {
    println(i + ": " + content[i]);
  }
}

Wo ist der Haken? Wenn wir bei add() das 101-ste Element hinzufügen wollen, müssen wir einen komplett neuen Array erstellen (z.B. mit 200 Elementen) und den alten Array in den neuen kopieren, bevor wir das neue Element anhängen. Das kostet natürlich Zeit. (Sie können sich auch überlegen, was passiert, wenn Sie das 50-ste Element entfernen müssen.)

void add(Object x) {
  if (currentSize < content.length) {
    content[currentSize] = x;
    currentSize++;
  } else {
    // Fall: Array ist zu klein!
    // TODO: neues Array, Inhalte kopieren, ...
  }
}

Dennoch wird diese alternative Implementierung häufig genutzt und heißt sinnvollweise ArrayList. Wir lernen die fertige Implementierung, die Java von Haus aus anbietet, in einem späteren Kapitel kennen.

void setup() {
  MyList ls = new MyList();
  ls.add("foo");
  ls.add("bar");

  MyList list2 = new MyList();
  list2.add("one");
  list2.add("two");

  ls.addAll(list2);
  ls.printAll();
}

foo
bar
one
two

void setup() {
  MyList ls = new MyList();
  ls.add("foo");
  ls.add("bar");

  MyList list2 = new MyList();
  list2.add("one");
  list2.add("two");

  ls.addAll(list2);
  ls.printAll();

  println("+ + +")
  list2.add("three");
  ls.printAll();
}

foo
bar
one
two
+ + +
foo
bar
one
two

foo
bar
one
two
+ + +
foo
bar
one
two
three

12.3 ArrayList und Generics

Wir sehen uns jetzt die Klasse ArrayList genauer an, die Java/Processing "von Haus aus" anbietet und dem Programmierer erlaubt, Listen anzulegen und dort beliebig Elemente hinzuzufügen oder zu entfernen. Java bietet eine ganze Reihe von Klassen zur Verwaltung von mehreren Objekten an (z.B. LinkedList, HashMap, TreeSet etc.) diese Klassen laufen unter dem Oberbegriff Collections.

Eine solche Liste ist - ähnlich wie MyList - ein Objekt, das zunächst mal erzeugt werden muss. Im Gegensatz zu unserer Implementierung im Eigenbau können wir bei ArrayList den Typ der Elemente angeben, die wir in der Liste speichern wollen:

ArrayList<String> namensListe = new ArrayList<String>();

Wie Sie sehen, wird der Element-Typ in spitzen Klammern angegeben. Klassen, bei denen man einen zusätzlichen Typen in spitzen Klammern angibt, nennt man Generics. Für uns ist wichtig: in dieser Liste kann man nur Strings speichern!

Jetzt wollen wir die Liste befüllen. Das machen wir mit der Methode add() der Klasse ArrayList:

namensListe.add("Superman");
namensListe.add("Batman");
namensListe.add("Catwoman");

Sie sehen hier keine Indices. Die Methode add() hängt das übergebene Objekt immer hinten an die Liste an. Dabei werden automatisch Indices vergeben, d.h. am Ende haben wir wieder Element 0, 1 und 2. Wenn wir auf diese Elemente zugreifen wollen, verwenden wird die Methode get() :

for (int i = 0; i < namensListe.size(); i++) {
  println(namensListe.get(i));
}

Wichtig: Um die aktuelle Länge der Liste zu bekommen, verwendet man die Methode size(). Das ist ein großer Unterschied zu Arrays, wo eine Instanzvariable namens length diese Aufgabe hat.

Erweiterte For-Schleife (For-each)

Eigens für die Listen wurde eine vereinfachte For-Schleife entwickelt, die den Index i überflüssig macht. Stattdessen stelle man sich vor, man wolle "alle String-Elemente der List namensListe" durchlaufen. In jeden Durchlauf möchte man das durchlaufene Element in der Variable element zur Verfügung haben:

for (String element: namensListe) {
  println(element);
}

Das kann man lesen als "Für alle Strings element aus der Liste namensListe...". In unserem Beispiel läuft die Schleife dreimal durch den Code. Beim ersten Mal enthält sie "Superman", beim zweiten Mal "Batman", beim dritten Mal "Catwoman". Ein Index i wird in dem Beispiel nicht benötigt.

Allgemein ist die Form der erweiterten For-Schleife:

for (<ELEMENT-TYP> <LAUFVARIABLE> : <LISTE>) {
  ...
}

Man nennt dies auch For-each-Schleife, weil man im englischen lesen kann: "for each element of type <ELEMENT-TYP> out of <LISTE> do the following ..."

Unbegrenzte Länge

Wichtig ist, dass man jederzeit add() aufrufen kann, um die Liste zu verlängern. Man kann mit der Methode remove() auch Elemente entfernen:

// String-Liste erzeugen
ArrayList<String> namensListe = new ArrayList<String>();

// Liste füllen
namensListe.add("Superman");
namensListe.add("Batman");
namensListe.add("Catwoman");

// Zugriff
for (int i = 0; i < namensListe.size(); i++) {
  println(namensListe.get(i));
}

// Liste ändern
namensListe.remove("Batman");
namensListe.add("Grüne Laterne");
namensListe.add("Krümelmonster");

println("- - -");

// Zugriff mit erweiterter For-Schleife
for (String element: namensListe) {
  println(element);
}

Superman
Batman
Catwoman
- - -
Superman
Catwoman
Grüne Laterne
Krümelmonster

Listen verwendet man immer dann, wenn Mengen sich verändern, was so oft vorkommt, dass man teils keine Arrays mehr verwendet. Zum Beispiel sind Listen auch sinnvoll, wenn Sie Objekte einlesen. Listen verbrauchen mehr Speicher als Arrays und sind evtl. auch langsamer im Zugriff. Solange man nicht zeit- oder speicherkritisch arbeiten muss, sollte man den Komfort von Listen auf jeden Fall nutzen.

Beispiel mit der Klasse Person

Listen können natürlich nicht nur mit Strings verwendet werden. Listen werden oft mit eigenen Klassen verwendet, zum Beispiel Person:

class Person {
  String name;
  int age;

  Person (String n, int a) {
    name = n;
    age = a;
  }
}

Machen wir uns eine Liste mit Personen. In die spitzen Klammer kommt der Typ der Elemente, die von der Liste gespeichert werden sollen.

void setup() {
  ArrayList<Person> plist = new ArrayList<Person>();

  plist.add(new Person("Harry", 15));
  plist.add(new Person("Sally", 5));
  plist.add(new Person("Joe", 3));
}

Jetzt wollen wir eine Funktion schreiben, die uns für eine Person das entsprechende Alter ausgibt. Denken Sie daran, dass der Name eine Eigenschaft der Klasse Person ist, so dass Sie per Punktoperator auf die Eigenschaft "name" zugreifen müssen. Hier sehen Sie auch, dass Sie Listen als Parameter verwenden können.

int findAge(String searchName, ArrayList<Person> liste) {

  // erweiterte For-Schleife
  for (Person p: liste) {
    if (p.name.equals(searchName)) {
      return p.age;
    }
  }
  return -1;
}

Jetzt rufen wir die Funktion in setup() auf:

void setup() {
  ArrayList<Person> plist = new ArrayList<Person>();

  plist.add(new Person("Harry", 15));
  plist.add(new Person("Sally", 5));
  plist.add(new Person("Joe", 3));

  println(findAge("Sally", plist));
}

5

Elemente innerhalb einer Schleife entfernen

Elemente können mit der Methode remove() aus der Liste entfernt werden. Beachten Sie, dass das Objekt durchaus noch existiert, es ist lediglich nicht mehr in der Liste enthalten. Häufig wollen wir Elemente entfernen, während wir eine Schleife durchlaufen, zum Beispiel, um die Liste zu filtern (nicht mehr sichtbare Schüsse entfernen, alle nicht-aktiven Vereinsmitglieder entfernen etc.).

Eine wichtige Regel ist, dass Elemente nicht innerhalb einer For-each-Schleife entfernt werden dürfen.

Folgender Code ist also fehlerhaft:

ArrayList<String> namensListe = new ArrayList<String>();

namensListe.add("Superman");
namensListe.add("Batman");
namensListe.add("Catwoman");

for (String element: namensListe) {
  // Name, der mit S beginnt
  if (element.startsWith("S")) {
    namensListe.remove(element); // NICHT ERLAUBT IN SCHLEIFE
  }
}

Processing gibt in der Regel eine ConcurrentModificationException und beendet das Programm. Der Grund ist, dass die Verwaltung der Schleife aus dem Tritt kommt, wenn ein Element entfernt wird.

Selbst wenn der Fehler bei Ihnen nicht vorkommt, kann es sein, dass er in der Zukunft auftritt, deshalb sollten Sie ein remove() in der For-each-Schleife vermeiden.

Man darf innerhalb einer For-each-Schleife nicht Elemente einer Liste (mit remove) entfernen!

Da es aber häufig vorkommt, dass man Elemente in einer Schleife entfernen möchte, müssen wir auf die konventionelle For-Schleife zurückgreifen. Wir haben aber ein Problem, wenn wir vorwärts durch die Schleife gehen: wenn wir in der Schleife bei Element i sind und in diesem Durchlauf das Element i löschen, dann rutscht das Element i+1 auf Position i. Aber dies Element wird im nächsten Schleifendurchlauf nicht mehr untersucht, da wir dann bei i+1 sind! Wir überspringen also bei jedem Löschen das jeweils nächste Element (Ausnahme: wir löschen das letzte Element).

Lösung 1: Liste rückwärts durchlaufen

Als Lösung durchlaufen wir die List rückwärts. Wenn wir jetzt Element i löschen, macht es nichts, wenn i+1 nach vorn rutscht, da wir als nächstes ja i-1 untersuchen.

Codebeispiel (alle Namen, die mit S beginnen, entfernen):

ArrayList<String> namensListe = new ArrayList<String>();

namensListe.add("Superman");
namensListe.add("Superman"); // 2x Superman!
namensListe.add("Batman");
namensListe.add("Catwoman");

for (int i = namensListe.size()-1; i >= 0; i--) {
  if (namensListe.get(i).contains("S")) {
    namensListe.remove(i);
  }
}

// Ausgeben
for (String element: namensListe) {
  println(element);
}

Ausgabe:

Batman
Catwoman

Zum Vergleich sehen wir uns die normale Vorwärtsschleife an:

for (int i = 0; i < namensListe.size(); i++) {
  if (namensListe.get(i).contains("S")) {
    namensListe.remove(i); // Element i+1 rutscht nach!	
  }
}

Jetzt bekommen wir:

Superman
Batman
Catwoman

Denn das zweite "Superman" wurde übersprungen.

Lösung 2: Iterator verwenden (empfohlen)

Alternativ können Sie einen sog. Iterator verwenden, um eine Liste zu durchlaufen und gleichzeitig Elemente zu löschen. Ein Iterator ist ein Objekt, welches das Durchlaufen einer Liste "verwaltet". Man kann es sich als eine Art Zeiger auf das aktuelle Element vorstellen. Einen Iterator zu verwenden, ist die empfohlene Methode in Java, auf die wir an dieser Stelle aber nicht tiefer eingehen (siehe z.B. javabeginners). Wichtig ist hier, dass das Iterator-Objekt die Löschung eines Elements vornehmen kann und entsprechend seinen Zeiger anpasst.

Nur damit Sie das mal gesehen haben, der obige Code mit Hilfe eines Iterators. Beachten Sie, dass Sie das Paket java.util.* importieren müssen.

import java.util.*;

ArrayList<String> namensListe = new ArrayList<String>();

namensListe.add("Superman");
namensListe.add("Superman");
namensListe.add("Batman");
namensListe.add("Catwoman");

Iterator<String> it = namensListe.iterator();
while (it.hasNext()) {
  String element = it.next();
  if (element.startsWith("S")) {
    it.remove();
  }
}

// Ausgeben
for (String element: namensListe) {
  println(element);
}

Wichtige ArrayList-Methoden

Da Listen im Grunde die Arrays im Programmieralltag ersetzt haben, lohnt es sich, die vielen Methoden anzuschauen, die ArrayList zu bieten hat.

Hier stellen wir einige überblicksartig vor. Das T steht im folgenden für den Typ, den Sie bei Generics in spitzen Klammern angeben. Wenn Sie eine Liste mit ArrayList<Person> angeben, wäre T also die Klasse Person:

Wrapperklassen

Eine Liste kann nur Objekte speichern, keine primitiven Datentypen wie z.B. ganze Zahlen. Das ist ein herber Nachteil, denn vielleicht möchten Sie Geldbeträge, Jahreszahlen oder Indexzahlen in Listen speichern.

Eine Liste kann keine Elemente primitiver Datentypen (z.B. float, int, boolean) beinhalten.

Dies geht also nicht:

ArrayList<int> zahlen = new ArrayList<int>(); // PRIMITIV!

Um dem abzuhelfen bietet Java für jeden primitiven Datentyp wie int, float, boolean eine entsprechende sogenannte Wrapperklasse an: Integer, Float und Boolean. Man kann sich eine Klasse so vorstellen:

// Diese Klasse brauchen Sie nicht zu implementieren,
// denn Java/Processing stellt sie bereits zur
// Verfügung...

class Integer {
  int value;

  // Konstruktor
  Integer(int v) {
    value = v;
  }

  // Zugriff auf den Wert
  int intValue() {
    return value;
  }
}

Die Klasse "wickelt" (engl. to wrap) einen int-Wert einfach in ein Objekt. Dieses Objekt macht nichts anderes, als diesen einen Wert zu speichern. Jetzt kann man eine Liste für solche Objekte anlegen:

ArrayList<Integer> zahlen = new ArrayList<Integer>();

Um Zahlen hinzuzufügen, nutzen wir den Konstruktor von Integer:

zahlen.add(new Integer(10));
zahlen.add(new Integer(-5));
zahlen.add(new Integer(42000));

Um die Zahlen auszulesen, verwenden wir die Methode intValue:

for (Integer z: zahlen) {
  println(z.intValue());
}

Autoboxing

Die Verwendung von Konstruktor und intValue() macht die Sache sehr sperrig, daher wurde in Java das sog. Autoboxing eingeführt. Java erkennt selbst, wenn eine Zahl "eingepackt" (engl. boxing) werden sollte. Sie können also folgendes schreiben und Java fügt selbständig das "new Integer(..)" hinzu:

zahlen.add(10); // Zahl wird automatisch in neues Objekt gepackt
zahlen.add(-5);
zahlen.add(42000);

Autounboxing

Analog gibt es das Autounboxing, d.h. die Werte werden aus den Objekten ausgepackt, ohne dass die Methode intValue() explizit aufgerufen werden muss:

for (Integer z: zahlen) {
  println(z); // Zahl wird aus Objekt rausgezogen
}

Hier ein weiteres Code-Beispiel, das zeigt, wie Java mit den Wrapperklassen umgeht. Im Grunde kann man sagen, dass Objekte von Wrapperklassen genauso behandeln können, als ob Sie einen primitiven Datentypen vor sich hätten:

Float f1 = 12.5; // Autoboxing
println(f1 - 2.5); // Autounboxing

Float f2 = f1 - 10; // Autounboxing + Autoboxing

float x = f1 + f2; // 2x Autounboxing
println(x);

Eigene Generics programmieren (*)

Im vorigen Abschnitt haben wir eine eigene Liste MyList programmiert. Diese konnte beliebige Objekte speichern und war somit nicht typisiert, d.h. man könnte verschiedene Objekte mischen und muss zur Laufzeit casten, um auf spezifische Objekteigenschaften zuzugreifen.

Weiterhin haben wir Generics am Beispiel der ArrayList kennen gelernt. Hier können Sie in spitzen Klammern den Typ der Objekte angeben, die in der Liste gespeichert werden können. Wie können wir selbst eine solche generische Klasse programmieren?

In Java können Sie bei Definition einer Klasse einen generischen Typen als Variable übergeben. Konvention ist, diesen Typ mit einem einzigen Großbuchstaben zu benennen. Bei MyList wollen wir den Typ Object ersetzen durch eine Variable:

class MyList<T> {
  ...
}

Genauso wie bei ArrayList möchten Sie dadurch erlauben, dass die Liste mit einem spezifischen Typ erstellt werden kann:

MyList<String> l = new MyList<String>();

Zurück zum Code. Ab sofort können Sie überall, wo Sie den spezifischen Typ erzwingen möchten, die Variable T einsetzen. Die Methode add() etwa, möchte natürlich nur Inhalte vom Typ T als Parameter zulassen:

void add(T x) {
  ...
}

Auch die Hilfsklasse ListItem sollte ein Generic sein:

class ListItem<T> {
  T content;
  ListItem next = null;

  ListItem(T x) {
    content = x;
  }
}

Jetzt können wir uns die Klasse MyList in ihrer Gesamtheit ansehen:

class MyList<T> {
  ListItem<T> first;

  void add(T x) {
    ListItem<T> li = new ListItem<T>();
    li.content = x;
    if (first == null) {
      first = li;
    } else {
      ListItem<T> last = getLastItem();
      last.next = li;
    }
  }

  ListItem<T> getLastItem() {
    if (first == null) {
      return null;
    }
    ListItem<T> last = first;
    while (last.next != null) {
      last = last.next;
    }
    return last;
  }

  void printAll() {
    ListItem<T> li = first;
    int counter = 0;
    while (li != null) {
      println(counter + ": " + li.content);
      li = li.next;
      counter++;
    }
  }
}

Der einzige Fall, der hier nicht auftaucht, ist, dass ein generischer Typ als Rückgabetyp einer Methode verwendet wird. Auch das ist natürlich möglich.

for (<ELEMENT-TYP> <LAUFVARIABLE> : <LISTE>) {
...
}