Verkettung
Grundlagen
Die meisten gängigen Programmiersprachen definieren eine Reihe von primitiven Datentypen für atomare Werte. Typischerweise sind das Typen für Ganz- und Fließkommazahlen. Dazu kommen aus Gründen der Benutzbarkeit Datentypen für boolesche Werte, Buchstaben1 oder Zeichenketten. Will man mehrere gleichartige Variablen zusammenfassen, unterstützen viele Sprachen Arrays (auch Feld oder Reihung genannt). Diese werden durch einen zusammenhängenden Bereich im Speicher repräsentiert.
Beispiel: Den Speicher des Computers (genauer gesagt den „Heap“) kann man sich als lange Reihe nummerierter Zellen vorstellen, in denen jeweils eine Zahl abgelegt werden kann.
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Wenn eine Variable angelegt (deklariert) wird, erfolgt zur Laufzeit eine Zuordnung zwischen der Variablen und einer gerade freien Speicherzelle. Diese wird für die Variable reserviert:
int a; // a entspricht Speicherzelle 1000Wenn bei der Ausführung des Programms der Variablen ein Wert zugewiesen wird, wird dieser Wert an die entsprechende Stelle im Speicher geschrieben.
a = 42; // speichere den Wert 42 in der Zelle 1000
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Wird ein Array angelegt, dann wird ein zusammenhängender freier Block Speicher für das Array reserviert.
int[] b = new int[5];
// b beginnt bei Adresse 1001 und ist 5 Zellen lang2
int[] c = new int[10];
// c beginnt bei Adresse 1006 und ist 10 Zellen lang3
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Will man nun einen Wert im Array speichern, verwendet man den Index, an dem der Wert abgelegt werden soll. Daraus kann auf einfache Weise die zugehörige Adresse berechnet werden:
b[3] = 28; // b[3] gehört nach 1001 + 3 = 10044
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Der Speicherbedarf eines Arrays entspricht dem Speicherbedarf der darin enthaltenen Werte sowie einer Information über die Länge des Arrays. Damit sind Arrays die kompakteste Form, in der man Werte speichern kann. Zudem ist der wahlfreie Zugriff (Lesen oder Überschreiben) auf beliebige Elemente des Arrays („random access“) in konstanter Zeit möglich.
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Problematisch wird es, wenn einem Array weitere Werte hinzugefügt werden sollen. Unerheblich, ob die Werte am Ende, am Anfang oder irgendwo in der Mitte des Arrays eingefügt werden, müsste eine weitere Speicherzelle an den Block angefügt werden. Im obigen Beispiel müsste beim Erweitern des gelb markierten Arrays die Zelle 1006 hinzugenommen werden. Leider beginnt ab Zelle 1006 bereits der Speicherblock des grünen Arrays.
Wenn man als Programmierer Arrays verwenden will, muss man also im Vorfeld bereits wissen, wie viele Elemente das Array aufnehmen soll. Das ist aber nicht in allen Anwendungsfällen möglich. In diesem Fall sind verkettete Listen eine mögliche Lösung.
Eine Element einer verketteten Liste besteht aus einem Datum (z.B. einer Zahl) sowie einem Verweis auf ihren Nachfolger.
Abbildung 1: Einfach verkettete Liste von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Im obigen Beispiel verweist das erste Element mit dem Wert „12“ auf seinen Nachfolger mit dem Datum „99“, dieser auf seinen Nachfolger mit dem Wert „37“ und dieser auf „nichts“ (bzw. „null“). Die 37 ist damit das Ende der Liste.
Im Speicher kann eine solche Liste wie folgt aussehen:
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Um mit der Liste arbeiten zu können, benötigt man einen Verweis auf ihr erstes Element, die Speicheradresse 1001. Von dort aus kann man die weiteren Elemente der Liste erreichen, indem man den Nachfolger-Verweisen folgt.
Man sieht, dass die Elemente der verketteten Liste nicht zwangsläufig als ein zusammenhängender Block im Speicher liegen müssen, auch die Reihenfolge im Speicher muss nicht unbedingt ihrer Reihenfolge in der Liste entsprechen.
Um ein neues Element an die Liste anzuhängen, wird es (z.B. an der Speicherstelle 1015) erzeugt und der Nachfolgerverweis des letzten Elements auf seine Adresse gesetzt:
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Auf diese Weise ist das Fassungsvermögen einer verketteten Liste nur durch den insgesamt verfügbaren Speicher beschränkt.
Auch das Einfügen eines Elements am Anfang oder in der Mitte der Liste ist effizient möglich.
Beispiel: Der Wert 70 soll direkt hinter der 12 eingefügt werden. Dazu werden die folgenden Schritte ausgeführt:
- neues Element mit Datum 70 erzeugen (hier an der Adresse 1017)
- der Nachfolger des Elements mit dem Wert 70 ist der bisherige Nachfolger der 12 (also Adresse 1009)
- der neue Nachfolger des Elements mit dem Datum 12 ist das Element mit dem Wert 70 (also Adresse 1017)
Bildquelle: Tabelle von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Die Schritte, die durchgeführt wurden, sind nicht abhängig von der Länge der Liste. Allerdings muss man den Verweis auf das Element, hinter dem eingefügt werden soll, erst einmal finden.
Vergleich von Array und verketteter Liste
Sowohl Array als auch verkettete Liste haben ihre Anwendungsbereiche. Je nachdem, welche Ziele man hat, ist die eine oder die andere Datenstruktur besser geeignet.
Zunächst einmal kann man feststellen, dass der benötigte Speicherbedarf für ein Array geringer ist. Man benötigt so viel Platz, wie die zu speichernden Werte belegen sowie einmalig Platz für die Array-Länge. Bei einer verketteten Liste benötigt man für jeden Wert zusätzlich Platz, um die Adresse seines Nachfolgers zu speichern.
Beispiel: Um 1000 int-Zahlen (32 Bit = 4 Byte) in einem Array zu speichern, benötigt man 4∙1000 = 4000 Byte sowie 4 Byte für die Länge des Arrays. Eine verkettete Liste mit 1000 int-Zahlen benötigt auf einer 32-Bit-Maschine 4∙1000 Byte für die Daten sowie weitere 4∙1000 Byte für die Nachfolgeradresse.
Um mit einem Array arbeiten zu können, benötigt man die Adresse des ersten Elements sowie die Länge des Arrays. Für die Liste muss man die Adresse des ersten Elements kennen.
Bei Arrays ist – wie oben erwähnt – ein direkter Zugriff auf jedes Element möglich. Um auf ein Element einer verketteten Liste zuzugreifen, muss diese vom Anfang her durchgegangen werden, indem jeweils der Nachfolgerverweis genommen wird.
Implementation in Java
Bildquelle: Listenknoten<T> von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Eine konkrete Implementation einer verketteten Liste kann mit der Klasse Listenknoten<T> umgesetzt werden, wie sie im UML-Diagramm rechts dargestellt ist.
Hier wird auf das get/set-Pattern, das in der Objektorientierten Programmierung üblich ist, verzichtet. Der Grund dafür ist, dass die Getter und Setter eigentlich „nichts tun“. Es wird keine Überprüfung oder Berechnung vorgenommen. Der Wert von daten bzw. nachfolger wird nur gesetzt bzw. zurückgegeben. Der Code würde nur unnötig aufgebläht werden. Da die Listenknoten-Objekte ohnehin nur von der Klasse Liste verwendet werden, fällt auch die Notwendigkeit, sich gegen spätere Änderungen der internen Implementation abzusichern, hier weg.
Die Liste bestehend aus den Werten „12, 99 und 37“ in Abbildung 1 könnte man folgendermaßen erzeugen:
Listenknoten<Integer> a = new Listenknoten<Integer>(37, null);
Listenknoten<Integer> b = new Listenknoten<Integer>(99, a);
Listenknoten<Integer> c = new Listenknoten<Integer>(12, b);
Um mit der Liste arbeiten zu können, benötigt man den Verweis auf das erste Listenelement c. Jetzt könnte das Anhängen eines Elements wie folgt realisiert werden: Man beginnt beim ersten Knoten der Liste und springt so lange zum Nachfolger, bis man ein Element ohne Nachfolger gefunden hat.
void anhaengen(Listenknoten k, T neuerWert) {
while(k.nachfolger != null) {
k = k.nachfolger;
}
k.nachfolger = new Listenknoten(neuerWert, null);
} Alternativ wäre eine rekursive Implementation möglich:
void anhaengen(Listenknoten k, T neuerWert) {
if (k.nachfolger == null) {
k.nachfolger = new Listenknoten(neuerWert, null);
}
else {
anhaengen(k.nachfolger, neuerWert);
}
} Auf diese Weise kann man auch Operationen für das Einfügen am Anfang oder an einer bestimmten Stelle in der Mitte implementieren. Ebenso wäre das Suchen eines Wertes, das Abfragen des n-ten Wertes oder das Entfernen eines Wertes möglich.
Es gibt aber zwei Probleme, wenn ein Programmierer die Datenstruktur Listenknoten und die Algorithmen, wie sie oben beschrieben sind, direkt verwenden würde:
-
Niemand hindert den Programmierer daran, zyklisch verkettete Listen zu erzeugen. Der folgende Code wäre möglich:
Würde man z.B. die MethodeListenknoten<Integer> a = new Listenknoten<Integer>(37, null); Listenknoten<Integer> b = new Listenknoten<Integer>(99, a); a.nachfolger = b;anhaengenmitaoderbals Parameter aufrufen, würde diese nicht terminieren, da niemals ein Knoten erreicht würde, der keinen Nachfolger hat. -
Die Methode oben geht davon aus, dass der übergebene
Listenknotenzu Beginn nichtnullist. Dies würde einer leeren Liste entsprechen. Ein Programmierer, der denListenknotenselbst verwalten würde, müsste Spezialfälle für den Fall einbauen, dass die Liste leer ist.
Bildquelle: VerketteteListe<T> ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 02_hintergrund_adts.odt
Als Lösung ist es daher sinnvoll, die Verwaltung der Listenknoten in einer Klasse zu kapseln. Diese gibt zu keinem Zeitpunkt Zugriff auf Objekte der Klasse Listenknoten, sondern erlaubt nur die Manipulation der gesamten Liste mittels öffentlicher Methoden5
. Das UML-Diagramm rechts zeigt eine Auswahl von Methoden, die die Klasse anbieten könnte. Alles, was sich die Listen-Klasse in ihrer einfachsten Form merken muss, ist der erste Listenknoten, von dort aus kann sie alle anderen Knoten erreichen.
1 Beides sind auch atomare Typen, die intern auf Zahlen zurückgeführt werden.
2 Wo die Länge des Arrays abgelegt wird, hängt von der Programmiersprache ab. Bei C/C++ z.B. muss der Programmierer noch selbst eine Variable dafür anlegen und verwalten. In Java hängt es von der Java Virtual Machine ab, wo die Arraylänge steht – für den Programmierer ist sie jedoch stets als b.length abrufbar.
3 In Java werden int-Arrays standardmäßig mit Nullen initialisiert. In anderen Sprachen wie z.B. C/C++ ist der Arrayinhalt undefiniert, d.h. der vorher dort vorhandene Wert bleibt einfach im Speicher. Für unser Beispiel ist das jedoch irrelevant.
4 Wir unterschlagen hier zur didaktischen Reduktion, dass die Werte im Array meist mehr als 1 Byte Speicher benötigen. ints benötigen z.B. meist 4 Byte.
Die korrekte Adresse würde als „Adresse des Arrays + Größe des Datentyps * Index“ berechnet.
5 Java bietet das Sprachkonzept der inneren Klassen an, das hier nützlich sein könnte. Innere Klassen werden innerhalb einer anderen („äußeren“) Klasse definiert. Wenn ihre Sichtbarkeit zudem auf private oder protected gesetzt wird, ist sie nur innerhalb ihrer umgebenden Klasse bzw. deren Unterklassen bekannt. Innere Klassen sind aber nicht Teil des Bildungsplans.
Hintergrundinformationen: Herunterladen [odt][305 KB]
Weiter zu Abstrakte Datentypen