Datenstrukturen
Wenn ein Programm viele Daten verarbeitet, wird es umständlich oder sogar unmöglich, jedem einzelnen Wert einen Namen zu geben. Die Lösung: Datenstrukturen.
MATERIALIEN
In einem Computerprogramm werden Daten in Variablen gespeichert, so dass sie flexibel verwaltet, verglichen, verändert – allgemeiner: verarbeitet – werden können. Dabei unterscheidet man verschiedene Datentypen (z.B. int, double, char, boolean, usw.) und Geltungsbereiche: So gilt eine Methodenvariable nur innerhalb der Methode, in der sie deklariert wurde; während eine Instanzvariable aus allen Methoden heraus zugänglich ist, solange die entsprechende Instanz existiert.
Die oben erwähnten «einfachen Datentypen» können genau einen Wert des entsprechenden Typs speichern. Wollen wir mit mehreren gleichartigen Werten arbeiten, wird es schnell umständlich, jedem Wert seinen eigenen Namen zu geben. Die Lösung schaffen Datenstrukturen.
Datenstruktur
Eine Datenstruktur fasst mehrere Werte unter einem Namen zusammen und ermöglicht so, dass Computerprogramme flexibel und effizient auch mit grösseren Datenmengen umgehen können. Die üblichsten Datenstrukturen kann man sich vorstellen wie eine Liste (bzw. eine Tabelle) – dabei werden die einzelnen Werte durch einen Index adressiert (ähnlich wie in Excel).
Eine Datenstruktur kann aber auch anders organisiert sein, z.B. wie ein Baum (allgemeiner: Graph), oder mit benannten Elementen arbeiten – beispielsweise verwaltet die Klasse Color drei Werte für red, green und blue. An diesem Beispiel zeigt sich auch, dass jede Klasse die Funktion einer Datenstruktur haben kann, da sie üblicherweise bestimmte Werte (=Instanzvariablen) unter einem Namen (=Instanzname) speichert und verwaltet.
Analogie
Deine Joggingschuhe? Ich glaube, die sind im Keller-Regal auf dem drittobersten Tablar im fünften Abteil.
In Anlehnung an die initiale Kisten-Analogie: Wenn eine einfache Variable eine Kiste ist, dann ist eine typische Datenstruktur so etwas wie ein Regal mit abgezählten (indizierten) Fächern. In die Fächer kann man Werte legen – oder Kisten mit Werten drin, oder andere Regale – und an die Inhalte kommt man, indem man den Namen des Regals und den Index des Faches nennt.
Ein Beispiel: In einem Joe-Programm sollen zehn Kreise mit unterschiedlichen, vordefinierten Radien gezeichnet werden. Anstatt mit zehn einzelnen Variablen (radius1, radius2, … , radius10) zu arbeiten, fasst man die zehn Werte in einer Datenstruktur namens radien zusammen und hat dann Zugang zu den individuellen Werten, indem man sinngemäss sagt: «i-ter Wert von radien» – wobei i, also die Position des Werts innerhalb der Datenstruktur, der sogenannte Index ist.
Achtung! Computer zählen üblicherweise ab Null, der Index 0 entspricht also dem ersten Fach!
int[] radien = {2, 5, 2, 1, 6, 3, 12, 1, 1, 4}; //zehn Ganzzahlen
System.out.print(radien[3]); //den vierten Wert ausgeben, also 1
int r = radien[0]; //den ersten Wert in r speichern
radien[9] = 17; //den letzten Wert mit 17 überschreibenArrays
Die grundlegendste Datenstruktur in den meisten Programmiersprachen ist der Array, ein solcher wurde im obigen Beispiel auch verwendet. In Java erkennt man Arrays an den eckigen Klammern:
Deklarieren: Um einen Array zu deklarieren, schreibt man eckige Klammern hinter den Datentyp, int[] bedeutet also, dass es um ein «Regal» geht, in dessen Fächern Ganzzahlen gespeichert werden können.
Datentyp: Ein Array in Java kann nur Elemente desselben Datentyps speichern, also z.B. lauter float-Zahlen oder mehrere Wahrheitswerte. Man kann also nicht im ersten «Fach» eine Zahl speichern und im zweiten einen Buchstaben. Es muss allerdings nicht zwingend ein einfacher Datentyp sein, so kann man z.B. durchaus auch Joes in einem Array speichern.
Wie bei einzelnen Variablen gilt auch hier: Jede Klasse ist ein eigener Typ, Instanzen sind die dazu passenden Werte.
Zugriff: Für den Zugriff auf die im Array gespeicherten Werte braucht es eckige Klammern – hinter dem Namen, mit dem gewünschten Index zwischen den Klammern, z.B. meinArray[2]. Das funktioniert sowohl rechts von einem Gleichheitszeichen (Wert auslesen) als auch auf der linken Seite (Zuweisung an diese Stelle im Array).
Index: Der Index, also die Zahl, die angibt, das wievielte Fach gemeint ist, beginnt bei Null! Im Vergleich zum normalen Sprachgebrauch muss man daher immer eins abziehen: Das erste Fach hat den Index 0, das siebte Fach hat den Index 6, …
Länge: Der Array bekommt seine Länge (= Anzahl Fächer, bzw. Elemente) bei der Initialisierung. In Java können Arrays ihre Länge danach nicht mehr ändern. Um die Länge eines Arrays herauszubekommen, benutzt man die Array-Eigenschaft length:
System.out.print(meinArray.length); //die Länge von meinArray wird ausgegebenInitialisierung:
Variante 1:
int[] meinArray = {1, 2, 3};
//Erstellt einen Array mit drei Elementen und weist die Werte gleich zuVariante 2:
int[] meinArray = new int[17];
//Erstellt einen Array mit siebzehn leeren Elementen. Genau genommen erhalten alle Elemente den Wert 0 (oder null, bei komplexen Datentypen)Schleifen: In Verbindung mit Arrays werden häufig Schleifen benutzt, meist um mit jedem im Array enthaltenen Element etwas zu tun – beispielsweise eine Zufallszahl zwischen 0 und 99 zuweisen:
for (int i = 0; i < meinArray.length; i++) { // Achtung: < length, nicht <=
meinArray[i] = Greenfoot.getRandomNumber(100);
}OOP-Datenstrukturen in Java
Zu Beginn der Entwicklung von «höheren Programmiersprachen» war der Array die einzige Datenstruktur. Hauptsächlich aus diesem Grund gibt es ihn auch heute noch in so gut wie jeder Programmiersprache, obwohl er genau genommen nicht in das OOP-Konzept passt – hauptsächlich, weil er weder ein einfacher Datentyp noch eine Klasse ist.
Aber auch in praktischer Hinsicht ist der Array ein seltsames Zwischending; er ist gleichzeitig zu sehr und zu wenig flexibel:
- zu inflexibel, weil er seine Grösse nicht ändern kann. Das ist natürlich lösbar – durch Umfüllen der Werte in einen grösseren Array (siehe Aufgabe 2) – aber nicht eben bequem.
- zu flexibel, weil man zu jeder Zeit jedes Element lesen, überschreiben, löschen, usw. kann. Oft benötigt man beispielsweise immer nur das letzte Element; in so einem Falle wäre es besser, eine Datenstruktur zu benutzen, die gar nichts anderes zulässt (hier bräuchte es einen Stack) – so können sich weniger Fehler einschleichen.
Aus diesen Gründen ist es sauberer, sich aus dem Fundus der mit Java gelieferten Datenstrukturen die für die jeweilige Aufgabe am besten geeignete auszusuchen – also eine, die möglichst nur das Nötige kann. Diese Java-eigenen Datenstrukturen sind Klassen, sie werden im sogenannten «Java Collection Framework» zusammengefasst, das sich im Paket java.util befindet. Einteilen lässt es sich in vier «Familien»: Listen (java.util.List), Sets (java.util.Set), Maps (java.util.Map) und Queues (java.util.Queue).
Bei der Wahl der passenden Datenstruktur kann man sich an der folgenden Tabelle orientieren:
| Klasse | Familie | Zugriff | Duplikate erlaubt | Ordnung | Kommentar |
| ArrayList | Liste (List) | wahlfrei über Index | Ja | geordnet | effizientes Lesen |
| LinkedList | Liste (List) | wahlfrei über Index | Ja | geordnet | effizientes Einfügen |
| Vector | Liste (List) | wahlfrei über Index | Ja | geordnet | synchronisiert (!) |
| Stack | Liste (List) | sequentiell (nur letztes Element) | Ja | geordnet | LIFO: Last In First Out |
| HashSet | Menge (Set) | ungeordnet; Test auf Existenz |
Nein | ungeordnet | schnelles Lesen |
| TreeSet | Menge (Set) | sortiert; Test auf Existenz |
Nein | sortiert | |
| LinkedQueue | Warteschlange (Queue) | sequentiell, Nachfolger | Ja | geordnet | effizientes Einfügen (am Rand) |
| PriorityQueue | Warteschlange (Queue) | sequentiell, Nachfolger | Ja | sortiert | |
| HashMap | Verzeichnis (Map) | wahlfrei über Schlüssel | Schlüsselduplikate nein Werteduplikate ja |
ungeordnet | effizientes Lesen |
| TreeMap | Verzeichnis (Map) | wahlfrei über Schlüssel | Schlüsselduplikate nein Werteduplikate ja |
sortiert |
Alle diese Bibliotheksklassen befinden sich im Paket java.util.* und müssen importiert werden. ArrayList und LinkedList sind im Wesentlichen gleich; die ArrayList ist schneller bei Zugriff auf einzelne Elemente, die LinkedList ist schneller bei Operationen wie löschen, hinzufügen.
ArrayList
Eine diese «sauberen», Java-eigenen Datenstrukturen soll hier noch kurz vorgestellt werden, und zwar diejenige, die dem klassischen Array am nächsten kommt: die ArrayList (eine vollständige deutsche Dokumentation findet sich hier: https://www.dpunkt.de/java/Referenz/Das_Paket_java.util/7.html)
Initialisieren
ArrayList <String> eineListe = new ArrayList <String> (); //neue, noch leere Liste für Strings
ArrayList <Integer> eineListe = new ArrayList <Integer> (); //neue, noch leere Liste für Ganzzahlen
ArrayList <String> stringList = new ArrayList <String> (Arrays.asList("Eins", "Zwei", "Viele")); //neue String-Liste mit drei WertenHinweise: In Spitzklammern wird der Datentyp für die Elemente auf der Liste angegeben. Diese Technik mit den spitzen Klammern gehört zum Schlagwort «generische Datentypen» – eingehender müssen wir uns an dieser Stelle damit nicht beschäftigen (auch wenn es schon interessant ist). Die ArrayList kann übrigens keine primitiven Datentypen (z.B. int, double,…) verwalten, sondern nur Klassen. Möchte man primitive Datentypen in einer ArrayList speichern, muss man als generischen Typen eine Wrapperklasse benutzen (z.B. Integer, siehe zweites Beispiel oben).
Elemente in der Liste manipulieren
liste.get(13); //Element auslesen
liste.add("Heinrich"); //Element einfügen (am Ende)
liste.add(0, "Heinrich"); //Element einfügen (an bestimmte Stelle, hier an Index 0)
liste.set(0, "Heini"); //bestimmtes Element ändern (überschreiben)
liste.remove("Heinrich"); //Element entfernen, hier dasjenige mit dem Wert "Heinrich"
liste.remove(1); //Element entfernen, hier dasjenige mit Index 1
liste.size(); //Größe zurückgeben
liste.contains("Heinri"); //Prüfen, ob Wert enthalten ist (gibt true oder false zurück)
liste.indexOf("Heinri"); //Welchen Index hat ein Wert?
liste.clear(); //Alle Werte aus Liste löschenListen ausgeben/durchlaufen
ArrayList <Integer> liste = new ArrayList <Integer> (); //Liste erstellen
liste.add(12); //erstes Element einfügen, also den Wert 12 an den Index 0
liste.add(1000); // jetzt haben wir eine Liste der Länge 2 ...Für eine ArrayList wie die eben kreierte gibt es verschiedene Möglichkeiten, an die enthaltenen Elemente zu kommen, bspw. um sie auszugeben:
a) Am einfachsten:
System.out.println(liste.toString());Hinweis: Mit toString() wird der Inhalt der ArrayList in einen einzigen String verpackt. Damit kann man natürlich meist nicht gut arbeiten, es ist aber ganz hilfreich, um mal rasch in eine ArrayList reinzuschauen. Übrigens beinhaltet jede Klasse in JAVA die toString()-Methode, da diese von der generischen Elternklasse Object geerbt wird. Eine hilfreiche Zeichenkette ergibt sich meist nur, wenn toString() in der entsprechenden Klasse selbst überschrieben wurde.
b) Gängig und flexibel:
for (int ausgabe : liste) {
System.out.println(ausgabe);
}Hinweis: Anstatt der knapperen foreach-Schleife kann man natürlich auch eine normale for-Schleife benutzen, z.B:
for (int i=0; i<liste.size(); i++) {
System.out.println(liste.get(i));
}c) Professionell:
ListIterator li = liste.listIterator();
while(li.hasNext()) {
System.out.println(li.next());
}Hinweis: Der ListIterator durchläuft die ArrayList und bietet zusätzlich einige Methoden zur Verarbeitung. So springt z.B. next() zum nächsten Element der Liste. Der entsprechende Index wird mit nextIndex() abgefragt.
Weitere Aufgaben
Aufgabe
Am Ende des Aufgabenblatts finden Sie eine Anleitung zu einem Mini-Projekt (ausgehend von ColorTest.zip), in dem Sie den Umgang mit (listenartigen) Datenstrukturen üben können.