Nachdem im vorigen Kapitel gezeigt wurde, wie Datenstrukturen unabhängig von ihrer Realisierung beschrieben werden können, wollen wir nun konkrete Implementierungen mithilfe der Programmiersprache Java vorstellen. Wir werden zunächst die bereits eingeführten Datentypen Keller (Stack) und Warteschlange (Queue) unter Nutzung von einfachen Feldern umsetzen. Da diese Implementierungen jedoch für den praktischen Einsatz nur bedingt geeignet sind, werden wir mit den verketteten Listen eine grundlegende Datenstruktur kennen lernen, die sehr häufig verwendet wird und auch zur Implementierung von Stacks und Queues genutzt werden kann.
Auch wenn das Verständnis grundlegender Datenstrukturen unabdingbar ist, wird man in der praktischen Arbeit oft einfach nur vorhandene Klassen mit der Implementierung dieser Datenstrukturen wiederverwenden. So zeichnen sich gute Programmierumgebungen oder Klassenbibliotheken gerade dadurch aus, dass sie häufig benötigte Datenstrukturen bereits anbieten. Für die hier betrachteten Container- oder Kollektionsdatentypen werden mit der Java-Klassenbibliothek eine ganze Reihe von Implementierungen bereitgestellt. Auf dieses Java Collection Framework werden wir daher zum Abschluss dieses Kapitels noch genauer eingehen.
Stack LIFO
Generische Datenstrukturen
Die Grundidee der Datenstruktur Stack haben wir bereits in Abschnitt 11.3.1 kennen gelernt. Das LIFO-Prinzip (Last-In-First-Out) wird mittels der Operationen push zum Ablegen eines Elementes auf dem Stack und pop zum Herunternehmen des obersten Elementes verwirklicht. Für eine Implementierung als Java-Klasse ist zunächst zu entscheiden, welcher Typ von Elementen mit dem Stack verwaltet werden soll, d.h., wie der Sortenparameter zu wählen ist. Bei der Vorstellung der Sortieralgorithmen in Abschnitt 5.2 sind wir aus Gründen der Vereinfachung von Folgen von int-Werten ausgegangen. Allerdings ist diese Vorgehensweise nicht sehr flexibel: Für double-Werte oder Zeichenketten des Typs String müssten jeweils eigene Methoden bzw. – angewendet auf den Stack – eigene Stack-Klassen implementiert werden. Zur Implementierung generischer, d.h. allgemein nutzbarer Datenstrukturen bietet sich in Java daher die Verwendung der Klasse java.lang.Object an. Da dies die Basisklasse aller Java-Klassen ist, lassen sich alle Objekte durch Objekte dieser Klasse repräsentieren. Mit diesem Wissen kann der abstrakte Datentyp Stack als Java-Schnittstelle (Interface) wie in Programm 13.1 angegeben, definiert werden. Insgesamt umfasst diese Schnittstelle die Methoden:
public interface Stack {
public void push(Object obj)
throws StackException;
public Object pop()
throws StackException;
public Object top()
throws StackException;
public boolean isEmpty();
}
Lesen vom leeren Stack
Eine besondere Behandlung erfordert noch der Fall, dass versucht wird, ein Element vom leeren Stack zu lesen. In der obigen Definition wird dies über eine Ausnahme des Typs StackException signalisiert, die beim Aufruf der Methoden pop und top auftreten kann. Diese Ausnahme wird auch ausgelöst, wenn es zu einem Überlauf des Stacks kommt, beispielsweise weil die Implementierung auf einem nicht vergrößerbaren Feld basiert. Diese Klasse StackException wird nach dem in Abschnitt 12.5 beschriebenen Schema implementiert (siehe auch Programm 12.3).
Es sei noch einmal angemerkt, dass es sich bisher bei Stack nur um einen abstrakten Datentyp in Form einer Schnittstelle handelt, der nicht instantiiert werden kann. Die Definition einer Schnittstelle gestattet es uns, später verschiedene Implementierungen zu nutzen. Zur Nutzung müssen wir noch eine konkrete Klasse bereitstellen, die die Stack-Schnittstelle implementiert. Auf mögliche Implementierungen werden wir in den folgenden Abschnitten noch näher eingehen.
Erzeugen eines Stacks
Nehmen wir zunächst an, dass eine solche Implementierung in Form einer Klasse ArrayStack verfügbar ist. In diesem Fall kann der Stack wie in Programm 13.2 genutzt werden. Der erste Schritt ist das Erzeugen eines Stack-Objektes durch Aufruf des Konstruktors der Klasse ArrayStack. Im Anschluss daran können Objekte (hier Strings) durch Aufruf der push-Methode auf dem Stack abgelegt werden. Schließlich werden die Stack-Elemente in einer Schleife über die Methode pop wieder ausgelesen. Dabei ist zu beachten, dass pop nur Objekte (oder besser Objektreferenzen) vom Typ Object zurückgibt. Soll wie im Beispiel der Ursprungstyp wiederhergestellt werden, ist eine explizite Typkonvertierung (Type Cast) notwendig.
public class StackExample {
public static void main(String args[ ]) {
Stack stack = new ArrayStack();
try {
// Elemente auf Stack ablegen
stack.push("Eins");
stack.push("Zwei");
stack.push("Drei");
while (! stack.isEmpty()) {
// Elemente herunternehmen
String s = (String) stack.pop();
System.out.println(s);
}
} catch(StackException exc) {
System.out.println(exc);
}
}
}
Objekte als Stack-Elemente
Da wir als Datentyp für die Stack-Elemente die Klasse Object gewählt haben, lässt sich der Stack für Objekte aller Java-Klassen nutzen. Werte von primitiven Datentypen wie int oder float können dagegen nicht direkt auf dem Stack verwaltet werden. Stattdessen müssen die objektwertigen Versionen in Form der Klassen java.lang.Integer, java.lang.Float usw. verwendet werden (siehe auch Abschnitt 12.2), die die primitiven Werte kapseln:
Stack stack = new ArrayStack();
stack.push(new Integer(1));
stack.push(new Integer(2));
stack.push(new Integer(3));
while (! stack.isEmpty()) {
try {
Integer i = (Integer) stack.pop();
System.out.println(i.intValue());
} catch (StackException exc) {
System.out.println(exc);
}
}
Queue FIFO
In ähnlicher Weise wie für den Datentyp Stack kann eine Schnittstelle für den Datentyp Warteschlange (Queue) definiert werden. Dieser Datentyp verwirklicht das FIFO-Prinzip (First-In-First-Out): Elemente können nur in der Reihenfolge ihres Eintragens wieder ausgelesen werden. Auch hier bietet sich wieder die Verwendung der Klasse java.lang.Object als Elementtyp an. Daraus ergibt sich die in Programm 13.3 dargestellte Schnittstelle mit den folgenden Methoden:
public interface Queue {
public void enter(Object obj)
throws QueueException;
public Object leave()
throws QueueException;
public Object front()
throws QueueException;
public boolean isEmpty();
}
Lesen aus einer Warteschlange
Ausleseversuche aus einer leeren Warteschlange werden wieder über eine entsprechende Ausnahme der Klasse QueueException signalisiert.
Auf die Darstellung der Nutzung der Warteschlange verzichten wir an dieser Stelle, da dies ähnlich zu Programm 13.2 ist.
Feld als Basis
Zeiger auf die »Spitze«
Für die Implementierung des Stacks ist eine geeignete Repräsentation der Elemente zu finden. Wir wählen zunächst eine sehr einfache Form auf der Basis eines Feldes. Felder haben wir bereits in Abschnitt 2.5.2 kennen gelernt. Da Objekte – als Instanzen der Klasse Object – mit dem Stack verwaltet werden sollen, ist ein Feld vom Typ Object[] zu verwenden. Felder haben jedoch einen Nachteil: Sie können nicht in der Größe verändert werden. Dies bedeutet, dass erstens das Feld mit einer festen Größe initialisiert und dass zweitens ein Zeiger auf die »Spitze« des Stacks verwaltet werden muss. In der Implementierung in Programm 13.4 wird dies durch die Variable num realisiert, die die Anzahl der Elemente auf dem Stack beinhaltet. Die Position num im Feld elements ist damit die nächste freie Position, das Element elements[num-1] das oberste Element des Stacks.
public class ArrayStack implements Stack {
private Object elements[ ] = null; // Elemente
private int num = 0; // aktuelle Anzahl
// Stack mit vorgegebener Kapazität erzeugen
public ArrayStack(int size) {
elements = new Object[size];
}
// Stack mit Standardkapazität erzeugen
public ArrayStack() {
elements = new Object[100];
}
public void push(Object obj) throws StackException {
if (num == elements.length)
// Kapazität erschöpft
throw new StackException();
elements[num++] = obj;
}
public Object pop() throws StackException {
if (isEmpty ())
// Stack ist leer
throw new StackException();
Object o = elements[−− num];
elements[num] = null;
}
public Object top() throws StackException {
if (isEmpty())
throw new StackException();
return elements[num − 1];
}
public boolean isEmpty() {
return num == 0;
}
}
Konstruktor
Zur Erzeugung von ArrayStack-Objekten stehen zwei Konstruktoren zur Verfügung: Der Konstruktor ohne Parameter legt ein Feld mit einer Standardgröße an (hier: 100), der zweite Konstruktor erlaubt die Angabe der gewünschten Feldgröße.
Leerer Stack
In der Methode push wird die übergebene Objektreferenz obj auf die erste freie Position des Feldes kopiert und die Variable num inkrementiert. Da das Feld in der Größe begrenzt ist, wird vor dem Ablegen des Elementes geprüft, ob das Feldende bereits erreicht ist. In diesem Fall wird eine Ausnahme der Klasse StackException signalisiert. Die Methode pop überprüft zuerst, ob der Stack leer ist, d.h., ob num gleich 0 ist. Auch in diesem Fall wird eine Ausnahme signalisiert. Sind dagegen noch Elemente auf dem Stack, so wird num dekrementiert und das sich an dieser Stelle befindliche Element zurückgegeben. Damit zeigt num wieder auf die erste freie Position.
Automatisches Löschen
Die nun freie Position im Feld wird wieder mit null belegt. Dadurch wird das dort zuvor gespeicherte Objekt vom Stack nicht mehr referenziert und kann vom Java-Laufzeitsystem automatisch gelöscht werden, wenn es auch außerhalb des Stacks nicht mehr benötigt wird.
Implementierungsvarianten
Eine Queue kann auf Basis eines Feldes im Prinzip ähnlich wie der Stack implementiert werden. Auch hier markiert ein Zeiger u (für »upper«) die erste freie Position im Feld. Da bei einer Queue jedoch die Elemente am anderen Ende des Feldes entfernt werden, müssen wir uns auch den Beginn des Feldes, d.h. die Position des ersten Elementes, merken. Hier gibt es zwei Implementierungsvarianten:
Zirkuläres Durchwandern
Die Implementierung aus Programm 13.5 realisiert die zweite Variante. Betrachten wir zunächst die Methode isEmpty am Ende des Programms. Es ist sofort klar, dass die Queue leer ist, wenn beide Zeiger auf die gleiche Position verweisen. Beim Einfügen eines Elementes in der Methode enter müssen der obere Zeiger u, beim Herausnehmen (Methode leave) entsprechend der untere Zeiger l inkrementiert werden. Die Verwendung von zwei Zeigern hat noch einen besonderen Effekt: Erreicht der obere Zeiger u die Feldgrenze, bedeutet dies nicht notwendigerweise, dass die Queue damit voll ist. Zeigt der untere Zeiger l auf eine Position > 0, so ist noch Platz am unteren Ende. Die beiden Zeiger wandern demnach zirkulär durch das Feld. Dies kann auf einfache Weise dadurch erreicht werden, dass die Zeiger nach dem Inkrementieren modulo der Feldgröße aktualisiert werden.
public class ArrayQueue implements Queue {
private Object[ ] elements = null; // Elemente
private int l = 0, u = 0; // unterer und oberer Zeiger
// Queue mit vorgegebener Kapazität erzeugen
public ArrayQueue(int size) {
elements = new Object[size];
}
// Queue mit Standardkapazität erzeugen
public ArrayQueue() {
elements = new Object[100];
}
public void enter(Object obj) throws QueueException {
if ((elements.length − l + u) % elements.length
== elements.length − 1)
// Kapazität ist erschöpft
throw new QueueException();
elements[u] = obj;
// oberen Zeiger aktualisieren
u = (u + 1) % elements.length;
}
public Object leave() throws QueueException {
throw new QueueException();
Object obj = elements[l];
elements[l] = null;
// unteren Zeiger aktualisieren
l = (l + 1) % elements.length;
return obj;
}
public Object front() throws QueueException {
if (isEmpty())
throw new QueueException();
return elements[l];
}
public boolean isEmpty() {
return l == u;
}
}
Überlauf
Ein Problem ergibt sich dann, wenn die Queue vollständig gefüllt ist. In diesem Fall würde die Bedingung l = u erfüllt sein, d.h., es kann nicht mehr zwischen »leer« und »voll« unterschieden werden. Die in Programm 13.5 verwendete Lösung aus [GT14] vermeidet dies, indem die Queue für ein Feld der Größe N nur mit N − 1 Elementen gefüllt wird. Somit bleibt immer eine Position frei und auch für eine vollständig gefüllte Queue gilt: l ≠ = u. Die Einhaltung dieser Forderung wird zu Beginn der Methode enter überprüft. Die aktuelle Anzahl der Elemente der Queue ergibt sich aus (N − l + u) mod N. Ist diese Anzahl gleich N − 1, so wird eine Ausnahme der Klasse QueueException ausgelöst.
Zeitkomplexität
Betrachten wir abschließend noch die Komplexität der Implementierungen auf Basis von Feldern. Bezüglich der Laufzeit ist leicht ersichtlich, dass in allen Methoden eine konstante, d.h. von der Anzahl der Elemente unabhängige Zahl von Zuweisungen, Vergleichen und arithmetischen Operationen durchgeführt wird. Die Zeitkomplexität beträgt daher O(1) für alle Operationen.
Speicherplatzkomplexität
Der Speicherplatzbedarf wird dagegen durch das Anlegen eines Feldes einer vorgegebenen Größe N verursacht und ist somit unabhängig von der tatsächlichen Anzahl der Elemente im Stack bzw. in der Queue. Für die Speicherplatzkomplexität kann demnach O(N) angegeben werden.
Ein Problem der hier vorgestellten Implementierungen ist die Größenbeschränkung des Feldes. So werden nur so lange Elemente eingefügt, bis die Kapazität des Feldes erschöpft ist. Ein Ausweg wäre das Erzeugen eines neuen, größeren Feldes und das Umkopieren der Elemente aus dem alten Feld. Dennoch haben Felder durchaus vorteilhafte Eigenschaften, wie etwa den günstigen Platzverbrauch (keine zusätzlichen »Verwaltungsinformationen«) oder die kompakte und dadurch Cache-freundliche Organisation der Daten.
Dynamische Datenstrukturen
Die Probleme statischer Datenstrukturen lassen sich durch die Verwendung dynamischer Strukturen umgehen. Dynamisch bedeutet dabei, dass sie zur Laufzeit »wachsen« oder »schrumpfen« können und sich dadurch an den tatsächlichen Speicherbedarf anpassen lassen.
Verkettete Liste
Verweis
Anker
Ein typischer Vertreter einer dynamischen Datenstruktur ist die verkettete Liste. Eine solche Liste besteht aus einer Menge von Knoten, die untereinander »verzeigert« oder auch »verkettet« sind. Jeder Knoten besteht damit aus einem Verweis (in Java eine Objektreferenz) auf das eigentliche zu speichernde Element sowie einem Verweis auf das nachfolgende Element. Das letzte Element verweist demzufolge auf null. In der Liste selbst muss nur noch der erste Knoten direkt verankert sein, alle anderen Knoten sind durch das Navigieren über die Zeiger erreichbar. Abbildung 13–1 verdeutlicht dieses Prinzip. Der »Anker« für den Beginn der Liste wird mit head bezeichnet. Die einzelnen Knoten sind durch Rechtecke dargestellt, die eigentlichen Elemente (»Siggi«, »Benny« etc.) durch Ovale und die Verweise durch Pfeile. Anhand dieser Struktur wird deutlich, dass nur so viele Knoten benötigt werden, wie tatsächlich Elemente in der Liste vorhanden sind. Daraus ergibt sich eine Speicherplatzkomplexität von O(n) für eine Liste mit n Elementen.
Abb. 13–1 Prinzip der verketteten Liste
Verkettung
Das Prinzip der Verkettung von Knoten lässt sich nun direkt zur Implementierung von Datentypen wie Stack und Queue verwenden. Wir wollen aber stattdessen zunächst einen eigenen Datentyp List definieren, der dann leicht als Basis für andere Datentypen genutzt werden kann.
Benötigte Operationen
Betrachten wir als Erstes die für die Realisierung von Stack und Queue auf Basis einer verketteten Liste notwendigen Operationen. Für den Stack benötigen wir offensichtlich das Einfügen und Auslesen von Elementen an einem Ende der Liste. Für die Queue muss das Herausnehmen eines Elementes am anderen Ende möglich sein. Wir können demnach folgende Operationen festlegen:
Für die Realisierung von Stack und Queue ist die Operation addLast eigentlich nicht notwendig. Im Interesse der Wiederverwendbarkeit der Liste wollen wir diese Operation aber dennoch bereitstellen.
Einfügen
Löschen
Geht man davon aus, dass der Zeiger head auf das erste Element der Liste zeigt, können die Operationen addFirst und removeFirst einfach implementiert werden. Beim Einfügen muss nur ein neuer Knoten erzeugt werden, der das eigentliche Element aufnimmt und auf das ursprüngliche erste Element verweist. Anschließend muss der Zeiger head auf den neuen Knoten umgesetzt werden (Abbildung 13–2). Zum Löschen des ersten Elementes wird der Zeiger head einfach auf den Knoten gesetzt, auf den der erste Knoten verweist. Das Element des ursprünglichen Knotens wird abschließend zurückgegeben. Die Operation getFirst ist trivial, da das erste Element direkt über head verfügbar ist. Die drei Operationen weisen damit offensichtlich eine Zeitkomplexität von O(1) auf, da sie unabhängig von der Länge der Liste einen konstanten Aufwand verursachen.
Manipulation des Listenendes
Die Operationen zur Manipulation des Listenendes sind dagegen etwas komplexer. Da nur der Listenanfang bekannt ist, muss für das Anhängen eines Elementes zunächst der letzte Knoten (tail) durch Verfolgen der next-Zeiger ermittelt werden. Dieser ist dadurch gekennzeichnet, dass sein next-Zeiger auf null verweist. Ist der letzte Knoten gefunden, wird dessen next-Zeiger auf den neu angelegten Knoten mit dem anzuhängenden Element gesetzt (Abbildung 13–3).
Abb. 13–2 Einfügen am Beginn einer verketteten Liste
Abb. 13–3 Einfügen und Löschen am Ende einer verketteten Liste
Zum Löschen des letzten Elementes wird dagegen auch der vorletzte Knoten benötigt, da dessen Verweis auf null gesetzt werden muss. Entsprechend muss der Knoten gesucht werden, dessen Nachfolgerknoten auf null verweist (Abbildung 13–3). Da in jedem Fall die gesamte Liste durchlaufen werden muss, ist der Aufwand abhängig von der Anzahl n der Elemente in der Liste und beträgt für diese Operationen entsprechend O(n). Der Aufwand aller Listenoperationen ist noch einmal in Tabelle 13–1 dargestellt.
Repräsentation eines Knotens
Mit dem Verständnis zu den Listenoperationen kann nun eine Klasse List implementiert werden. Hierfür benötigen wir eine Hilfsklasse Node zur Repräsentation der Knoten mit den Verweisen auf das eigentliche Element (element) und den Nachfolger (next). Als Datentyp für die Elementreferenz wählen wir zweckmäßigerweise wieder die Klasse java.lang.Object. Die Definition der Klasse Node ist in Programm 13.6 angegeben. Zusätzlich zu den beiden Verweisen sind nur noch Methoden für deren Manipulation vereinbart. Da diese Klasse außerhalb einer Liste nicht benötigt wird und auch nicht sichtbar sein soll, ist sie als interne Klasse von List definiert.
Tab. 13–1 Komplexität der Listenoperationen
Operation |
Komplexität |
addFirst getFirst removeFirst |
O(1) |
addLast getLast removeLast |
O(n) |
class List {
static class Node {
Object element; // Element
Node next; // Verweis auf Nachfolger
// Konstruktoren
public Node(Object o, Node n) {
element = o; next = n;
}
public Node() {
element = null; next = null;
}
// Element neu belegen
public void setElement(Object o) {
element = o;
}
// Zugriff auf Element
public Object getElement() {
return element;
}
// Nachfolger setzen
public void setNext(Node n) {
next = n;
}
public Node getNext() {
return next;
}
}
...
}
Behandlung der leeren Liste
In der Klasse List selbst wird der Listenkopf head als Attribut vom Typ Node repräsentiert. Ausgehend von dieser Referenz sind alle Knoten der Liste erreichbar. Ein kleiner Trick hilft dabei, die Behandlung der leeren Liste zu vereinfachen. Zeigt head nämlich auf das tatsächliche erste Element, so bedeutet dies für den Fall der leeren Liste, dass head == null ist. Da in diesem Fall aber beispielsweise die Methode getNext nicht aufgerufen werden kann, müsste die Bedingung immer gesondert geprüft werden. Dies kann vermieden werden, wenn ein echter head-Knoten verwendet wird, der als Element null enthält und auf das eigentliche erste Element bzw. für den Fall der leeren Liste auf null verweist. Dieser head-Knoten wird beim Erzeugen der Liste im Rahmen des Konstruktors angelegt (Programm 13.7).
public class List {
// ...
private Node head = null; // Listenkopf
public List() {
head = new Node();
}
public void addFirst(Object o) {
// neuen Knoten hinter head einfügen
Node n = new Node(o, head.getNext());
head.setNext(n);
}
public void addLast(Object o) {
Node l = head;
// letzten Knoten ermitteln
while (l.getNext() != null)
l = l.getNext();
Node n = new Node(o, null);
// neuen Knoten anfügen
l.setNext(n);
public Object getFirst() throws ListEmptyException {
if (isEmpty())
throw new ListEmptyException();
// erstes Element ist Nachfolger von head
return head.getNext().getElement();
}
public Object getLast() throws ListEmptyException {
if (isEmpty ())
throw new ListEmptyException ();
Node l = head;
// letzten Knoten ermitteln
while (l.getNext() != null)
l = l.getNext();
return l.getElement();
}
public Object removeFirst() throws ListEmptyException {
if (isEmpty())
throw new ListEmptyException();
Object o = head.getNext().getElement();
// Verweis von head aktualisieren
head.setNext(head.getNext().getNext());
return o;
}
public Object removeLast() throws ListEmptyException {
if (isEmpty())
throw new ListEmptyException();
Node l = head;
// vorletzten Knoten ermitteln
while (l.getNext().getNext() != null)
l = l.getNext();
Object o = l.getNext().getElement();
// Verweis auf Nachfolger löschen
l.setNext(null);
return o;
}
public int size() {
int s = 0;
Node n = head;
// Knoten zählen
while (n.getNext() != null) {
n = n.getNext();
}
return s;
}
public boolean isEmpty() {
return head.getNext() == null;
}
}
Löschen der Knoten
Die weiteren Methoden aus Programm 13.7 implementieren die bereits beschriebenen Listenoperationen. Der Test mittels isEmpty weist Versuche ab, eine leere Liste auszulesen, und löst im Fehlerfall eine Ausnahme der Klasse ListEmptyException aus. Weiterhin ist zu beachten, dass bei removeFirst und removeLast eine Referenz auf das Element, auf das der zu löschende Knoten verweist, vor dem Umsetzen der Zeigers gesichert wird (in beiden Methoden in der Variablen o), da das Element sonst nicht mehr erreichbar ist. Ein echtes »Löschen« der Knoten ist dagegen aufgrund der automatischen Speicherbereinigung von Java nicht notwendig.
Für die Klasse sind noch zwei weitere Methoden implementiert: size liefert die Anzahl der Elemente in der Liste und isEmpty testet, ob die Liste leer ist. In der Methode size werden dazu ausgehend von head alle Knoten durchlaufen und der Zähler s jeweils um 1 inkrementiert. Eine andere Implementierungsmöglichkeit wäre das Mitführen eines Attributes size, das beim Einfügen bzw. Löschen jeweils inkrementiert bzw. dekrementiert wird. Die Methode isEmpty prüft einfach, ob der next-Verweis des Kopfknotens null ist. In diesem Fall ist die Liste leer.
Implementierung des Stacks
Mithilfe dieser Klasse lässt sich der Stack aus Abschnitt 13.1 nun sehr einfach implementieren. Anstelle des bei ArrayStack verwendeten Feldes wird ein List-Objekt zur Speicherung der Stack-Elemente genutzt. Hierbei ist zu entscheiden, welches Ende der Liste die Spitze des Stacks repräsentiert. Da nach Tabelle 13–1 die Operationen am Listenanfang nur einen konstanten Aufwand erfordern, sollten die Elemente entsprechend am Listenanfang eingefügt bzw. von dort entfernt werden, so dass sich die Implementierung aus Programm 13.8 ergibt.
public class ListStack implements Stack {
private List list; // Liste zur Verwaltung der Elemente
list = new List();
}
public void push(Object obj) {
// Element vorn anfügen
list.addFirst(obj);
}
public Object pop() throws StackException {
if (isEmpty())
throw new StackException();
// Element von vorn entfernen
return list.removeFirst();
}
public Object top() throws StackException {
if (isEmpty())
throw new StackException();
return list.getFirst();
}
public boolean isEmpty() {
return list.isEmpty();
}
}
Die Queue kann man in ähnlicher Weise auf Basis der Klasse List implementieren. Dies sei dem Leser jedoch als Übung überlassen.
Zugriffauf das letzte Element
Ein Problem der Implementierung der verketteten Liste ist der mit dem Zugriff auf das letzte Element verbundene Aufwand. Da jeder Knoten nur mit seinem Nachfolger verkettet ist, muss das letzte Element immer erst durch Navigieren vom Listenkopf ausgehend über alle Knoten ermittelt werden. Zwar könnte man die Liste um einen tail-Zeiger auf das letzte Element ergänzen und so das Einfügen von Elementen am Ende der Liste vereinfachen. Dies würde beispielsweise die Implementierung der Klasse Queue vereinfachen. Trotzdem ist beim Löschen des letzten Elementes immer noch das Durchlaufen aller Knoten zum Auffinden des vorletzten Knotens notwendig.
Eine Verbesserung bietet daher die doppelt verkettete Liste, bei der jeder Knoten nicht nur seinen Nachfolger, sondern auch seinen Vorgänger kennt (Abbildung 13–4).
Abb. 13–4 Doppelt verkettete Liste
Listenanfang und -ende
Anhängen eines Elementes
Für eine doppelt verkettete Liste werden zwei spezielle Knoten, head für den Listenanfang und tail für das Listenende, verwaltet. Durch die Verfügbarkeit des Listenendes und der rückwärts gerichteten Verweise vereinfachen sich die Operationen am Listenende. So kann das letzte Element für die Operation getLast direkt über tail mit konstantem Aufwand O(1) ermittelt werden. Auch beim Anhängen eines Elementes mit addLast kann über tail sofort der bisher letzte Knoten bestimmt werden, dessen next-Zeiger nun auf den neuen Knoten zeigt. Zusätzlich muss noch der prev-Zeiger des neuen Knotens auf den bisherigen letzten Knoten verweisen (Abbildung 13–5).
Abb. 13–5 Anhängen am Ende einer doppelt verketteten Liste
Beim Löschen (removeLast) wird zunächst über den prev-Zeiger des letzten Knotens der vorletzte Knoten bestimmt, dessen next-Zeiger dann auf null gesetzt wird. Auch für die Operationen addLast und removeLast beträgt der Aufwand daher O(1) (Tabelle 13–2). Ebenso einfach ist das Einfügen und Löschen von Elementen in der Mitte der Liste. Allerdings muss hierzu zunächst die entsprechende Position in der Liste gefunden werden, indem beispielsweise vom Anfang der Liste ausgehend dasjenige Element gesucht wird, vor oder nach dem das neue Element eingefügt werden soll.
In Programm 13.9 sind die für eine doppelte Verkettung notwendigen Änderungen an der Klasse Node dargestellt. Es werden nur eine zusätzliche Objektreferenz auf den Vorgänger prev sowie die für den Zugriff benötigten Methoden getPrevious und setPrevious hinzugefügt.
Tab. 13–2 Komplexität der Operationen für eine doppelt verkettete Liste
Operation |
Komplexität |
addFirst getFirst removeFirst addLast getLast removeLast |
O(1) |
public class DList {
static class Node {
Object obj; // Element
Node prev, next; // Zeiger auf Vorgänger und Nachfolger
public Node(Object o, Node p, Node n) {
obj = o;
prev = p; next = n;
}
public Node() {
obj = null;
prev = next = null;
}
...
// Vorgänger neu belegen
public void setPrevious(Node p) {
prev = p;
}
// Zugriff auf Vorgänger
public Node getPrevious() {
return prev;
}
}
}
Konstruktor
Einfügen am Anfang
Die Klasse DList aus Programm 13.10 implementiert unter Nutzung der obigen Node-Klasse die doppelt verkettete Liste. Die beiden Zeiger auf den Listenanfang (head) bzw. das Listenende (tail) werden wieder wie in Abschnitt 13.2 über spezielle Knoten realisiert, um die Behandlung einer leeren Liste zu vereinfachen. Im Konstruktor der Klasse werden beide Knoten initialisiert und wechselseitig verknüpft. Der Test auf die leere Liste im Rahmen der Methode isEmpty liefert daher genau dann true, wenn gilt: head.getNext() == tail. Das Einfügen eines Elementes am Anfang reduziert sich damit auf das Einfügen des neuen Knotens zwischen den head-Knoten und dessen Nachfolger, entsprechend ist das Anhängen eines Elementes durch das Einfügen zwischen dem tail-Knoten und dessen Vorgänger realisiert.
public class DList {
// ...
private Node head = null; // Listenanfang
private Node tail = null; // Listenende
public DList() {
head = new Node();
tail = new Node();
// Anfang und Ende "verknüpfen "
head.setNext(tail);
tail.setPrevious(head); tail.setNext(tail);
}
public void addFirst(Object o) {
// Knoten zwischen head und dessen Nachfolger einfügen
Node n = new Node(o, head, head.getNext());
head.getNext().setPrevious(n);
head.setNext(n);
}
public void addLast(Object o) {
// Knoten zwischen tail und dessen Vorgänger einfügen
Node l = tail.getPrevious();
Node n = new Node(o, l, tail);
l.setNext(n);
tail.setPrevious(n);
}
public Object getFirst() throws ListEmptyException {
if (isEmpty())
throw new ListEmptyException();
return head.getNext().getElement();
}
public Object getLast() throws ListEmptyException {
if (isEmpty())
throw new ListEmptyException();
// Zugriff über Listenende
return tail.getPrevious().getElement();
}
public Object removeFirst() throws ListEmptyException {
if (isEmpty())
throw new ListEmptyException();
// Zugriff über Listenanfang
Object o = head.getNext().getElement();
// Knoten zwischen head und Nachfolger entfernen
head.setNext(head.getNext().getNext());
head.getNext().setPrevious(head);
return o;
}
public Object removeLast() throws ListEmptyException {
if (isEmpty())
throw new ListEmptyException();
// Zugriff über Listenende
Node n = tail.getPrevious();
// Knoten zwischen tail und Vorgänger entfernen
n.getPrevious().setNext(tail);
tail.setPrevious(n.getPrevious());
return n.getElement();
}
public int size() {
int s = 0;
Node n = head;
// Knoten zählen
while (n.getNext() != tail) {
s++;
n = n.getNext();
}
return s;
}
public boolean isEmpty() {
// keine Knoten zwischen head und tail
return head.getNext() == tail;
}
}
Da für die Klasse DList die gleichen Methoden wie für die Klasse List aus Abschnitt 13.2 definiert sind, lassen sich die Datenstrukturen Stack und Queue in gleicher Weise unter Benutzung der doppelt verketteten Liste implementieren. Für die Queue ergibt sich daraus der Vorteil, dass auch das Herausnehmen eines Elementes vom Ende der Liste mit konstantem Aufwand möglich ist.
Deque
Die Datenstruktur der doppelt verketteten Liste wird manchmal auch als Deque für »double-ended queue« bezeichnet. Hierbei handelt es sich um eine Warteschlange, die das Einfügen und Herausnehmen von Elementen an beiden Enden erlaubt.
Ein Nachteil von verketteten Listen gegenüber Feldern ist, dass die binäre Suche nicht einsetzbar ist, da man nicht beliebig »springen« kann. Eine Alternative ist es, mehrere Listen übereinanderzulegen, die dieses Springen ermöglichen. Eine derartige Datenstruktur wird als Skip-Liste bezeichnet.
Skip-Liste
Abbildung 13–6 zeigt eine Skip-Liste, die direkt die binäre Suche realisiert. Die Ebenen der Skip-Liste sind mit Li bezeichnet, wobei die Ebene L0 die eigentliche, sortiert abgespeicherte Liste darstellt. Die Listen der Ebene Li springen jeweils 2i Schritte weit und realisieren damit die binäre Aufteilung.
Abb. 13–6 Aufbau einer Skip-Liste
Es gibt jeweils einen initialen und einen terminalen Listenknoten, die die Werte −∞ und + ∞ tragen. Grundsätzlich gibt es zwei Möglichkeiten zur Speicherung der Listenelemente auf mehreren Ebenen:
In Abbildung 13–7 wird die Suche in einer solchen Liste skizziert. Man startet in der höchsten Ebene mit dem initialen Knoten. Wenn man einen Knoten ansieht, gibt es drei Möglichkeiten:
Abb. 13–7 Suche in einer Skip-Liste
Die bisher gezeigte Liste hat eine statische Struktur mit festen Schrittlängen, die durch das Einfügen und Löschen von Werten zerstört werden würde (etwa wenn die Werte 8 und 9 eingefügt werden). Allerdings ist der Algorithmus der Suche davon nicht betroffen: Selbst wenn 8 und 9 auf Ebene L0 eingefügt würden, würde die Suche weiterhin funktionieren – jedoch bei der Suche nach der 9 mehrere Schritte auf der untersten Ebenen durchlaufen.
Randomisierte Skip-Liste
Daher reicht es aus, wenn wir nur eine gute Näherung an feste Schrittlängen haben. Eine Möglichkeit ist es dabei, neu eingefügte Werte zufällig einer Ebene zuzuweisen, wobei im Mittel die Hälfte der Werte der Ebene L0 zugeordnet wird, ein weiteres Viertel der Ebene L1, ein Achtel dann L2 etc. Derartige Skip-Listen nennt man randomisiert. Abbildung 13–8 zeigt eine randomisierte Skip-Liste. Würde jetzt ein weiterer Wert hinzugefügt, würde er mit Wahrscheinlichkeit 
der Ebene Li zugeordnet, wobei die Anzahl der Ebenen sich aus der Gesamtzahl der Werte ergibt.
Abb. 13–8 Randomisierte Skip-Liste
Die zuerst eingeführten Skip-Listen mit Zweierpotenzen als festen Schrittlängen werden zur Abgrenzung von randomisierten Skip-Listen als perfekte Skip-Listen bezeichnet. Sie können insbesondere genutzt werden, wenn die Werte der Skip-Listen nicht mehr geändert oder ergänzt werden.
Betrachten wir eine einfache Implementierung der Skip-Liste. Zunächst benötigen wir eine Knotenklasse, die neben Vorgänger und Nachfolger auch die Verweise auf die Knoten der darunter liegenden Ebene Li−1 (down) und der darüber liegenden Ebene Li+1 (up) enthält. Diese Klasse ist in Programm 13.11 die Klasse SLItem, die als Element int-Werte enthalten kann. Wir implementieren dabei die Knotenvariante, bei der die Werte auf allen betroffenen Ebenen separat gespeichert sind:
public class SkipList {
public static int negInf = Integer.MIN_VALUE; // -inf
public static int posInf = Integer.MAX_VALUE; // +inf
static class SLItem {
public SLItem(int i) { element = i; }
int element; // Element
SLItem up, down, // Li+1 und Li-1
prev, next; // Vorgänger, Nachfolger
}
SLItem head, tail;
...
public boolean find(int o) {
SLItem item = head;
while (true) {
// zunächst nach rechts suchen ...
while (item.next.element != posInf &&
item.next.element <= o)
item = item.next;
if (item.down != null)
// eine Ebene nach unten
item = item.down;
else
// Ebene L0 erreicht
break;
}
return item.element == o;
}
}
Weiterhin benötigen wir noch die head- und tail-Knoten sowie die speziellen Werte für −1∞ und + ∞, die wir als kleinsten bzw. größten int-Wert repräsentieren.
In Programm 13.11 ist nur die Suche über die Skip-Liste mit der Methode find dargestellt. Ausgehend vom head-Knoten wird die oberste Ebene zunächst nach rechts durchlaufen, solange der Knotenwert ≤ dem gesuchten Wert ist. Erreicht man einen Knoten, dessen Wert größer ist, wird versucht, nach unten zu gehen. Ist dies nicht mehr möglich, weil die L0-Ebene erreicht ist, wird die Schleife mittels break abgebrochen. Da auf jeden Fall am Ende ein Knoten erreicht wird, muss abschließend noch geprüft werden, ob dessen Wert tatsächlich dem gesuchten Wert entspricht.
Durchwandern einer Kollektion
Iterator
Die Implementierungen der Listen aus den vorigen Abschnitten weist noch ein Manko auf, welches die praktische Verwendbarkeit einschränkt. So ist es oft notwendig, eine Kollektion zu »durchwandern«, d.h. über alle Elemente zu navigieren. Dieses Navigieren ist zunächst abhängig von der Implementierung: Während beispielsweise ein Feld mittels einer Indexvariablen durchlaufen wird, ist für verkettete Listen das Verfolgen der next-Zeiger der einzelnen Knoten notwendig. Auch im Hinblick auf die Erhaltung des Prinzips der Kapselung ist daher ein Konzept wünschenswert, das eine einheitliche Behandlung des Navigierens unabhängig von der internen Realisierung unterstützt. In Java wird dieses Konzept durch Iteratoren verwirklicht. Hierbei handelt es sich um Objekte zum Iterieren über Kollektionen, deren Klasse die vordefinierte Schnittstelle java.util.Iterator implementiert. Ein Iterator verwaltet einen internen Zeiger auf die aktuelle Position in der zugrunde liegenden Datenstruktur. Auf diese Weise ist es möglich, dass mehrere Iteratoren gleichzeitig auf einer Kollektion arbeiten (Abbildung 13–9).
Die Schnittstelle java.util.Iterator definiert die folgenden Methoden:
Abb. 13–9 Iterator-Konzept
Erzeugen eines Iterators
Diese Methoden lassen sich wie im folgenden Beispiel zum Durchlaufen einer Kollektion, wie z.B. einer Liste, anwenden. Zunächst muss der Iterator über eine entsprechende Methode der Kollektion (hier: iterator()) erzeugt werden. Anschließend kann in einer Schleife so lange die Iterator-Methode next aufgerufen werden, bis der Aufruf von hasNext den Wert false liefert. Da next eine Instanz vom Typ java.lang.Object liefert, ist gegebenenfalls wieder eine explizite Typkonvertierung notwendig.
java.util.Iterator iter = liste.iterator();
while (iter.hasNext()) {
Object obj = iter.next();
// Verarbeite obj ...
}
Wie kann nun ein solcher Iterator implementiert werden? Wir wollen dies am Beispiel der Klasse DList darstellen. Grundsätzlich muss eine Klasse bereitgestellt werden, die die Schnittstelle java.util.Iterator unterstützt. In dieser Klasse ListIterator ist ein Zeiger auf den aktuellen Knoten zu verwalten, der zu Beginn mit einem Verweis auf den ersten Knoten initialisiert wird (Programm 13.12).
public class DList {
class ListIterator implements java.util.Iterator {
private Node node = null; // aktueller Knoten
// Konstruktor
public ListIterator() {
// mit Listenanfang initialisieren
node = head.getNext();
}
public boolean hasNext() {
return node != tail;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Object next() {
if (! hasNext())
throw new java.util.NoSuchElementException();
Object o = node.getElement();
node = node.getNext();
return o;
}
}
// ...
public java.util.Iterator iterator() {
return new ListIterator();
}
}
Ausgehend vom Anfangsknoten kann in der Methode next zunächst geprüft werden, ob der letzte Knoten erreicht ist. In diesem Fall wird – wie in der Schnittstelle Iterator vorgegeben – eine Ausnahme NoSuchElementException erzeugt. Andernfalls wird das Element des aktuellen Knotens ausgelesen und der Zeiger node auf den Nachfolgeknoten gesetzt.
Erreichen des Listenendes
In der Methode hasNext wird auf Erreichen des Listenendes getestet. Hierzu wird einfach überprüft, ob der Nachfolger des aktuellen Knotens der tail-Knoten ist. Die Methode remove wird in unserer Implementierung nicht unterstützt und signalisiert dies durch eine entsprechende Ausnahme.
Die letzte Methode in Programm 13.12, die zur Klasse DList gehört, erzeugt schließlich einen Iterator der Klasse ListIterator und initialisiert diesen mit dem ersten Knoten der Liste. Dieser Iterator kann danach wie im obigen Beispiel genutzt werden.
Java Collection Framework
Datenstrukturen wie die bisher vorgestellten Kollektionen Liste, Stack oder Warteschlange werden im Programmieralltag häufig benötigt. Es ist daher nur verständlich, dass diese Datenstrukturen nicht jedes Mal neu implementiert werden, sondern dass sie in der Programmierumgebung für die allgemeine Verwendung bereitgestellt werden. In der Java-Umgebung sind entsprechende Klassen im Rahmen des Java Collection Framework (JCF) verfügbar, für andere Sprachen gibt es jedoch ähnliche Bibliotheken, so z.B. die STL für C++.
Basisdatentyp
Dictionary
Eine Besonderheit des Java Collection Framework ist die Trennung in Schnittstellen und Implementierungen. So werden zunächst eine Reihe von Schnittstellen als abstrakte Datentypen definiert (Abbildung 13–10). Die Schnittstelle java.util.Collection bildet den Basisdatentyp für die spezielleren Kollektionen List, Set und SortedSet. Zusätzlich gibt es noch den Datentyp Map, der – ähnlich einem Wörterbuch – die effiziente Verwaltung von Schlüssel-Wert-Paaren ermöglicht, d.h. den Zugriff auf ein Objekt bzw. Wert über einen Schlüssel erlaubt. Dieser Datentyp wird daher auch oft als Dictionary bezeichnet. Im Folgenden wollen wir uns allerdings auf die List- und Set-Typen beschränken.
Abb. 13–10 Struktur des Java Collection Framework
Zu diesen Schnittstellen sind jeweils verschiedene Implementierungen verfügbar, so dass der Programmierer die für seine Anforderungen am besten geeignete Klasse auswählen kann. Aus Tabelle 13–3 wird deutlich, dass beispielsweise für die Schnittstelle java.util.List eine Arraybasierte Implementierung (java.util.ArrayList) und eine Implementierung in Form einer verketteten Liste (java.util.LinkedList) angeboten werden. Für die anderen beiden Schnittstellen exisitiert jeweils eine Implementierung auf Basis einer Hashtabelle und eines Baumes. Beide Datenstrukturen werden wir später noch genauer vorstellen.
Tab. 13–3 Implementierungen für die Schnittstellen des Java Collection Framework
Die Collection-Schnittstelle als Basistyp für die anderen Kollektionen (mit Ausnahme von Map) definiert eine Reihe von grundlegenden Methoden. Hierzu gehören u.a.:
Sequenz
Zu Collection gibt es keine konkrete Implementierung. Stattdessen sind davon weitere Schnittstellen für Kollektionen mit speziellen Eigenschaften abgeleitet. So definiert List die Schnittstelle für geordnete Kollektionen (auch Sequenzen genannt). Dies bedeutet, dass die Einfügereihenfolge erhalten bleibt und dass außerdem ein positioniertes Auslesen bzw. Einfügen von Elementen möglich ist. Zusätzlich zu den Methoden von Collection sind in der java.util.List-Schnittstelle u.a. folgende Methoden verfügbar:
Iterator
Darüber hinaus unterstützt List noch einen speziellen Iterator vom Typ ListIterator, der auch eine rückwärts gerichtete Navigation über die Liste erlaubt.
Wie bereits in Tabelle 13–3 dargestellt, stehen als konkrete Implementierungen die Klassen ArrayList und LinkedList zur Verfügung. Erstere ist insbesondere dann sinnvoll, wenn ein direkter Zugriff über die Position notwendig ist und die Elemente im Wesentlichen am Ende der Liste eingefügt werden. Dagegen ist die Klasse LinkedList beim Einfügen von Elementen an einer beliebigen Position effizienter. Dies wird jedoch mit dem Nachteil des höheren Aufwandes beim positionierten Zugriff erkauft, da hierfür jeweils die Liste von Beginn an durchlaufen werden muss. Hinsichtlich der Nutzung unterscheiden sich beide Klassen nicht von den in den Abschnitten 13.2 und 13.5 vorgestellten Implementierungen.
Mengensemantik
Ordnung auf den Elementen
Die Schnittstelle java.util.Set ist für Kollektionen mit einer Mengensemantik vorgesehen. Dies bedeutet, dass keine Duplikate zugelassen sind: Jedes Objekt wird nur maximal einmal in die Kollektion aufgenommen. Gegenüber der Collection-Schnittstelle werden keine weiteren Methoden eingeführt. Für Set stehen zwei Implementierungen zur Verfügung: java.util.HashSet und java.util.TreeSet. Diese Implementierungen unterscheiden sich nicht nur in der Art der internen Organisation der Elemente, sondern auch in der Art und Weise, wie Duplikate erkannt werden. So sollte eine Klasse, deren Objekte in HashSet eingefügt werden sollen, die Methode hashCode aus der Klasse java.lang.Object überschreiben, da dieser Hashwert für die Bestimmung der Speicherposition (d.h. die Position in der zugrunde liegenden Hashtabelle) genutzt wird (Näheres zum Hashen in Kapitel 15). Dagegen werden in einem TreeSet die Elemente unter Verwendung der java.lang.Comparable-Schnittstelle verglichen. Diese Schnittstelle gestattet es, eine Ordnung auf den Elementen zu definieren. Objekte, die in ein TreeSet eingefügt werden, müssen daher diese Schnittstelle unterstützen. Daraus ergibt sich auch, dass die Elemente eines TreeSet geordnet vorliegen und über einen Iterator entsprechend ihrer Reihenfolge ausgelesen werden können. Im folgenden Beispiel wird die Anwendung von TreeSet demonstriert:
Set set = new TreeSet();
set.add("Eins");
set.add("Drei");
Iterator iter = set.iterator();
while (iter.hasNext())
System.out.println(iter.next());
Die java.lang.Comparable-Schnittstelle, die speziell von den Wrapper-Klassen java.lang.Double, java.lang.Float, java.lang.Integer usw. sowie von java.lang.String implementiert wird, definiert nur eine Methode:
Vordefinierte Algorithmen für Suchen und Sortieren
Unterstützt eine Klasse diese Schnittstelle, so können deren Objekte nicht nur in den Tree-basierten Kollektionen verwendet werden. Darüber hinaus eröffnet dies noch die Möglichkeit, die vordefinierten Algorithmen der Klasse java.util.Collections beispielsweise zum Suchen und zum Sortieren anzuwenden. Diese Klasse stellt eine Reihe von Klassenmethoden bereit, so z.B.:
Das nächste Beispiel demonstriert die Anwendung von sort und binarySearch:
java.util.List list = new java.util.LinkedList();
list.add("Eins");
list.add("Zwei");
list.add("Drei");
java.util.Collections.sort(list);
System.out.println("position = " +
java.util.Collections.binarySearch(list, "Eins"));
Mit diesen kurzen Beispielen wollen wir den Ausflug in die Java-Klassenbibliothek abschließen. Für weiter gehende Informationen sei auf die Dokumentation speziell zum Java Collection Framework [CWH98] verwiesen.
Bei der bisher beschriebenen Implementierungsform von Kollektionen auf Basis der Wurzelklasse java.lang.Object besteht jedoch grundsätzlich der Nachteil der Typunsicherheit, d.h., es lassen sich beispielsweise String-Objekte ebenso einfügen wie Integer-Objekte oder Instanzen beliebiger anderer Klassen. So muss gegebenenfalls beim Auslesen geprüft werden, ob die einzelnen Objekte tatsächlich der erwarteten Klasse angehören. Andernfalls kann es zu Laufzeitfehlern (Ausnahmen vom Typ ClassCastException) kommen, wie dies im folgenden Beispiel illustriert wird:
List list = new LinkedList();
list.add("Eins");
list.add("Zwei");
list.add(new Integer(3));
Iterator i = list.iterator();
while (i.hasNext()) {
String s = (String) i.next();
System.out.println("--> " + s);
}
Erreicht der Iterator hier das dritte Element, so führt die explizite Typkonvertierung nach String zu einer ClassCastException.
Generics
Dies gilt für die von uns eingangs dieses Kapitels vorgestellten Varianten von Stack und Queue genauso wie für die JCF-Klassen. Mit der Version J2SE 5.0 wurde daher das Konzept der sogenannten Generics eingeführt. Hierbei handelt es sich um parametrisierbare Datentypen: Der Typ der Elemente einer Kollektion kann hierbei festgelegt werden, so dass bereits zum Übersetzungszeitpunkt die Überprüfung der Typkompatibilität möglich ist.
Seit J2SE 5.0 sind die Kollektionen bereits als Generics implementiert. So kann das obige Beispiel wie folgt notiert werden, wobei der Elementtyp (in Form einer Klasse oder Schnittstelle) bei der Deklaration und Instanziierung der Kollektion sowie des zugehörigen Iterators in spitzen Klammern (< typ >) angegeben werden muss:
List<String> list = new LinkedList<String>();
list.add("Zwei");
Iterator<String> i = list.iterator();
while (i.hasNext()) {
String s = i.next();
System.out.println("--> " + s);
}
Ein Einfügen eines Integer-Objektes würde hier bereits beim Übersetzen abgewiesen werden.
Da die Angabe des Elementtyps sowohl bei der Variablendeklaration als auch der Instanziierung etwas umständlich ist, ist seit der Version 7.0 auch eine kompaktere Schreibweise möglich. Der Typ wird bei der Instanziierung dabei dynamisch bestimmt:
List<String> list = new LinkedList<>();
for-Schleife
In Abschnitt 3.6.1 haben wir bereits die neue Variante der for-Schleife vorgestellt. In Verbindung mit Generics lässt sich diese Form nun besonders einfach anwenden:
for (String s : list) {
System.out.println("--> " + s);
}
Einzige Bedingung für die Anwendung ist, dass die zu durchlaufende Kollektion die Schnittstelle java.lang.Iterable implementiert, was aber für alle JCF-Klassen zutrifft.
Autoboxing
Schließlich sei an dieser Stelle auch noch auf ein weiteres Konstrukt hingewiesen, das ebenfalls im Zusammenhang mit Kollektionen zum Tragen kommt: das Autoboxing. Wie bereits beschrieben, müssen Werte primitiver Datentypen unter Verwendung von Wrapper-Klassen gekapselt werden, um sie als Elemente in Kollektionen einfügen zu können. Dies erfodert jedoch wiederum entsprechende Typkonvertierungen, die die Lesbarkeit beeinträchtigen:
List list = new LinkedList();
list.add(new Integer(42));
int elem = ((Integer) list.get(0)).intValue();
Autoboxing macht diese Typkonvertierungen überflüssig, indem dies implizit (d.h. durch den Compiler) erfolgt. Das obige Beispiel kann deshalb wie folgt formuliert werden:
Es ist dabei aber zu beachten, dass als Elementtyp der Kollektion immer die entsprechende Wrapper-Klasse (hier Integer) einzusetzen ist.
Factory-Methode
Seit Version 9.0 vereinfacht für Klassen wie List und Map die Factory-Methode of() die Erzeugung und Initialisierung von Kollektionen:
List<String> l = List.of("Eins", "Zwei", "Drei");
Hierbei ist allerdings zu berücksichtigen, dass diese Methode eine unveränderliche Liste erzeugt. Soll die Liste dagegen später noch ergänzt oder verändert werden, muss die Liste in eine entsprechende veränderbare Klasse übertragen werden, z.B. durch:
List<String> l =
new ArrayList<>(List.of("Eins", "Zwei", "Drei"));
Die of-Methode gibt es auch für die Map-Klasse, ist allerdings auf maximal 10 Schlüssel-Wert-Paare beschränkt. Die Schlüssel und Werte müssen hierbei abwechselnd angegeben werden:
Map<Integer, String> map =
Map.of(10, "Zehn", 20, "Zwanzig", 39, "Dreißig");
Auch hier ist zu beachten, dass nur eine unveränderliche Map erzeugt wird.
