7.7.1 Vor- und Nachteile einer ArrayList
Betrachten wir den internen Aufbau einer kleinen Arrayliste einmal in einem vereinfachten Schema:
Stark vereinfachtes Schema einer Arrayliste aus sechs Elementen
Autor: Ulrich Helmich 04/2026, Lizenz: Public domain
Dieses Bild zeigt den (vereinfacht dargestellten) internen Aufbau eines kleinen ArrayList-Objekts aus sechs Elementen. Die Zahlen unter den Kästchen sollen die relative Speicheradresse symbolisieren.
Vorteile einer ArrayList:
- Es ist ein direkter Zugriff auf einzelne Elemente möglich. Wenn beispielsweise mit get(3) auf das Element mit dem Index 3 zugegriffen werden soll, wird die Speicheradresse des ersten Elements genommen (@1200) und dann um 3 x 50 inkrementiert.
- Eine ArrayList kann zudem einfach mit einer for-each-Schleife durchlaufen und dabei zum Beispiel ausgegeben oder durchsucht werden.
Nachteile einer ArrayList:
- In der obigen Abbildung ist das Einfügen eines Elementes dargestellt. Ein neues Element soll an Position 2 eingefügt werden. Um Platz für dieses neue Element zu schaffen, müssen die rechts neben dieser Einfügeposition stehenden Elemente um je eine Position nach rechts verschoben werden - ein sehr aufwändiger Prozess. Dies macht sich vor allem dann negativ bemerkbar, wenn sich die Einfügeposition im Anfangsbereich der Liste befindet und wenn die Liste sehr lang ist.
- Auch beim Löschen von Elementen zeigt sich der Nachteil einer solchen linearen Struktur. Alle nachfolgenden Elemente müssen um je eine Position nach links verschoben werden.
7.7.2 Vor- und Nachteile einer LinkedList
Aufbau einer LinkedList
Betrachten wir nun den internen Aufbau einer LinkedList:
Stark vereinfachtes Schema einer LinkedList aus fünf Elementen
Autor: Ulrich Helmich 04/2026, Lizenz: Public domain
Eine LinkedList besteht aus einzelnen Knoten. Jeder Knoten enthält
- die eigentlichen Daten (hier zum Beispiel "Hund", "Katze" etc.)
- eine oder mehrere Referenzen auf andere Knoten (hier zum Beispiel @1250).
Bei einer einfach verketteten Liste besitzt jeder Knoten genau eine Referenz auf einen weiteren Knoten, der dann als sein Nachfolger bezeichnet wird.
Der Knoten "Hund" an Adresse @1200 besitzt eine Referenz, die auf den Nachfolger-Knoten an Adresse @1250 verweist. Dieser Knoten - "Katze" - verweist auf einen Nachfolger-Knoten an Adresse @1600.
Der Nachfolgerknoten von "Katze" kann sich also an irgendeiner Adresse im Speicher befinden. Die Adresse des Nachfolgerknotens kann nicht aus der Adresse des Vorgängerknotens berechnet werden wie bei einem Array oder einer ArrayList. Stattdessen muss der Vorgängerknoten die Adresse des Nachfolgerknotens selbst verwalten.
In der aktuellen Java-Version werden Objekte der Klasse LinkedList durch eine doppelt verkettete dynamische Liste realisiert. Das heißt, jeder Knoten besitzt nicht nur eine Nachfolger-Referenz, sondern zusätzlich auch einen Verweis auf den jeweiligen Vorgänger.
Wenn wir selbst einen Knoten einer doppelt verketteten Liste programmieren wollten, könnte das beispielsweise so aussehen:
public class Knoten
{
Object wert;
Knoten vorgaenger;
Knoten nachfolger;
// Methoden
}
Einfügen in eine LinkedList
Soll ein neuer Knoten in eine solche einfach verkettete Liste eingefügt werden, so müssen lediglich die beteiligten Referenzen angepasst werden:
Stark vereinfachtes Schema einer LinkedList aus fünf Elementen
Autor: Ulrich Helmich 04/2026, Lizenz: Public domain
Das neue Element "Gans" soll zwischen "Maus" und "Rind" eingefügt werden. Dazu sind nur zwei Schritte notwendig, bei denen Referenzen "umgebogen" werden müssen:
- Die Referenz von "Maus" muss auf das neue Element "Gans" gesetzt werden
- Die Referenz von "Gans" wird auf "Rind" gesetzt.
Vorteile einer LinkedList
Das Einfügen und Löschen von Elementen ist sehr viel einfacher als bei einer ArrayList, es müssen lediglich ein paar Referenzen geändert werden. Ein Aufrücken vieler Elemente nach links oder rechts ist nicht erforderlich. Allerdings muss dazu die Position des einzufügenden oder zu löschenden Elements bekannt sein. Das Suchen einer solchen Position kann nämlich selbst wieder viel Zeit kosten.
Nachteile einer LinkedList
Wo Vorteile sind, sind immer auch Nachteile. Der wichtigste Nachteil besteht darin, dass kein Direktzugriff auf ein beliebiges Element möglich ist. Wenn man zum Beispiel das Element an Position 5000 benötigt, muss man die Liste Knoten für Knoten durchlaufen, bis diese Stelle erreicht ist - das sind dann 4999 Operationen. Der Zugriff auf ein bestimmtes Element dauert daher deutlich länger als bei einer ArrayList.
Wie bereits erwähnt, liegt das daran, dass man die Adresse eines Elements nicht wie bei einem Array oder einer ArrayList berechnen kann.
Hier könnte man sich natürlich mit Hilfszeigern die Arbeit erleichtern. Wenn die verkettete Liste beispielsweise aus 5000 Elementen besteht, könnte man in einem ersten Durchlauf Hilfs-Variablen erzeugen, die auf die Knoten an den Positionen 1000, 2000, 3000 und 4000 verweisen. Will man sich dann das Element an Position 4670 ausgeben lassen, folgt man zunächst der Hilfs-Variablen, die auf die Position 4000 zeigt, und beginnt dann dort mit der Suche. Dieses Vorgehen erinnert etwas an die Sprungsuche oder die Indexsuche, die wir bei den Suchverfahren besprochen haben.
Fazit
ArrayList: schnell beim Zugriff auf Elemente über deren Indizes; langsam beim Einfügen und Löschen von Elementen.
LinkedList: schnell beim Einfügen und Löschen von Elementen, falls deren Position bereits bekannt ist; langsam beim Suchen von Elementen.
7.7.3 Untersuchung der Implementation
Wir erstellen eine kleine Java-Klasse LinkedListDemo:
import java.util.LinkedList;
public class LinkedListDemo
{
LinkedList wortliste;
public LinkedListDemo()
{
wortliste = new LinkedList<>();
}
public void einfuegenDemo()
{
wortliste.add("Hund");
wortliste.add("Katze");
wortliste.add("Maus");
wortliste.add("Rind");
wortliste.add("Huhn");
}
}
Dieses Programm erstellt ein Objekt wortliste der Klasse LinkedList und fügt dann mit der add()-Methode fünf Strings in die Liste ein.
Wenn wir in BlueJ ein Objekt der Klasse LinkedListDemo erzeugen und dieses Objekt mit dem Objektinspektor untersuchen, sehen wir Folgendes:
Der BlueJ-Objektinspektor zeigt die Elemente der LinkedList an
Autor: Ulrich Helmich 04/2026, Lizenz: Public domain
Das Objekt wortliste besitzt mehrere Instanzvariablen, von denen drei besonders wichtig sind: size, first und last.
Dabei verwaltet size die Anzahl der in der Liste vorhandenen Elemente, first ist eine Referenz auf das erste Listenelement, und last verweist auf das letzte Element der Liste.
Wenn man nun auf das Zeigersymbol klickt, das first repräsentiert, zeigt der Objektinspektor das erste Listenelement an. Hier sehen wir drei Instanzvariablen, nämlich item, next und prev.
Hier ist item eine Referenz auf ein Objekt (hier: ein String-Objekt), next ist eine Referenz auf das nächste Listenelement und prev eine Referenz auf das vorherige Listenelement.
Man kann also gut erkennen, dass es sich bei dieser Liste um eine doppelt verkettete Liste handelt: Jedes Element hat einen Vorgänger und einen Nachfolger. Die Variable prev des ersten Elementes ("Hund") hat den Wert null, da das erste Element keinen Vorgänger hat. Entsprechend hat die Variable next des letzten Elementes ("Huhn") ebenfalls den Wert null, denn das letzte Listenelement hat keinen Nachfolger.
Kästchenschema einer LinkedList mit fünf Elementen
Autor: Ulrich Helmich 04/2026, Lizenz: Public domain
Dieses Bild zeigt die innere Struktur der Beispiel-Liste noch einmal in Form eines sogenannten Kästchenschemas. Im Informatik-Unterricht der gymnasialen Oberstufe sind Ihnen solche Kästchenschemata sicherlich schon begegnet. In NRW gehört die Kenntnis solcher doppelt verketteten dynamischen Listen sogar zum Pflichtstoff für das Abitur.
7.7.4 Wichtige Methoden der Klasse LinkedList
Die wichtigsten Methoden dieser Klasse sollen hier nur kurz dargestellt werden, alles Andere würde den Rahmen dieser Folge 7.7 sprengen.
addFirst(E element) // Vorne einfügen addLast(E element) // Ans Ende anhängen removeFirst() // Erstes Element entfernen removeLast() // Letztes Element entfernen E getFirst() // Wert des ersten Elements liefern E getLast() // Wert des letzten Elements liefern add(int index, E element) // Neues Element an Position index einfügen set(int index, E element) // Element an Position index überschreiben remove(int index) // Element an Position index entfernen remove(Object o) // Element o entfernen. E get(int index) // Wert des Elements an der Position index liefern clear() // Liste löschen contains(Object o) // liefert true, wenn o in Liste enthalten ist indexOf(Object o) // liefert den Index des ersten Vorkommens von o lastIndexOf(Object o) // liefert den Index des letzten Vorkommens von o isEmpty() // liefert true, wenn die Liste leer ist size() // liefert die Zahl der Listenelemente
7.7.5 Sinnvoller Einsatz von LinkedList
Für die meisten Anwendungen verwendet man eine ArrayList, vor allem dann, wenn häufig auf Listenelemente über den Index zugegriffen wird.
Eine LinkedList lohnt sich vor allem dann, wenn nicht das schnelle Finden per Index im Vordergrund steht, sondern das häufige Einfügen und Löschen von Elementen.
Diese Operationen können - sofern die entsprechende Position bereits bekannt ist - in sehr kurzer Zeit durchgeführt werden, da lediglich zwei oder drei Referenzen umgebogen werden müssen, während bei einer ArrayList eventuell Tausende von Elementen nach rechts oder links verschoben werden müssen.
Allerdings sollte man beachten, dass das Finden der Einfüge- oder Löschposition in einer LinkedList durchaus mit einem hohen Rechenaufwand verbunden sein kann, da die Liste nur sequenziell durchlaufen werden kann. Dadurch relativiert sich der eben genannte Vorteil oft.
Ein sinnvoller Einsatz von Objekten der Klasses LinkedList ergibt sich daher vor allem in folgenden Situationen:
- Wenn häufig am Anfang oder am Ende der Liste Elemente eingefügt oder gelöscht werden. Das ist beispielsweise bei einem Stack oder bei einer Queue der Fall (siehe Abstrakte Datentypen im Q1-Kurs).
- Wenn bereits Referenzen auf bestimmte Listenelemente vorliegen und dort gezielt Änderungen (Einfügen, Löschen, Überschreiben) vorgenommen werden sollen.
Fazit
In der Praxis ist die ArrayList meistens die bevorzugte Wahl. Eine LinkedList sollte vor allem dann eingesetzt werden, wenn viele Einfüge- und Löschoperationen vorkommen.
7.7.6 Eine eigene dynamische Liste
In diesem Abschnitt betrachten wir die Entwicklung einer einfach verketteten Liste. Die Liste - wir nennen die Klasse einfach mal MyLinkedList - soll Objekte der Klasse Object speichern.
Die Klasse Knoten
Unsere Modell-Liste MyLinkedList, die wir hier implementieren wollen, ist - im Gegensatz zur richtigen LinkedList - nur einfach verkettet. Jeder Knoten verweist auf seinen Nachfolger, nicht jedoch auf seinen Vorgänger.
public class Knoten
{
public Object wert;
public Knoten nachfolger;
}
Die beiden Instanzvariablen wurden bewusst als public deklariert, so dass man ohne Setter- und Getter-Methoden jederzeit auf sie zugreifen kann. Das entspricht zwar nicht ganz exakt den Prinzipien der OOP, vereinfacht aber die Implementation der Liste selbst, wie wir gleich noch sehen werden.
Kästchen-Darstellungen für dynamische Datenstrukturen
Diese Zeichnung stellt das Einfügen eines neuen Knotens an den Anfang der Liste graphisch mit einem sogenannten Kästchen-Schema dar. In der Klasse MyLinkedList ist die Methode addFirst() für diese Art des Einfügens zuständig.
In diesem Bild ist die Ausgangssituation dargestellt. Das Objekt der Klasse MyLinkedList besteht aus fünf Elementen vom Typ Knoten. Eine Referenzvariable anfang verweist auf das erste dieser fünf Elemente. Jedes Element verweist auf das Nachfolger-Element, und das letzte Element hat keinen Nachfolger mehr.
In diesem Bild wurde ein neuer Knoten erzeugt, beispielsweise mit den Anweisungen
Knoten neu = new Knoten(); neu.wert = "Test"; neu.nachfolger = null;
In diesem Bild ist dargestellt, wie die Referenzvariablen "umgebogen" werden.
Im ersten Schritt wird der Nachfolger-Zeiger des neuen Knotens auf das erste Listenelement gesetzt. Da die Variable anfang immer auf dieses erste Element zeigt, kann man jetzt ganz einfach schreiben:
neu.nachfolger = anfang;
Jetzt zeigt anfang auf das zweite Element und neu auf das neue Element, das jetzt das erste Element der Liste ist. Im nächsten Schritt müssen wir den Zeiger anfang auf das neue Element "umbiegen":
anfang = neu;
Die entsprechende Java-Methode für das Einfügen an den Anfang der Liste sieht dann so aus:
public void addFirst(Object neu)
{
Knoten neuerKnoten = new Knoten();
neuerKnoten.wert = neu;
neuerKnoten.nachfolger = anfang;
anfang = neuerKnoten;
}
Da die Instanzvariablen wert und nachfolger der Knoten-Objekte public sind, kann hier direkt darauf zugegriffen werden, ohne Setter- oder Getter-Methoden.
Auf ähnliche Weise kann man die Klasse MyLinkedList auch mit den Methoden
public void addLast(Object neu) public void add(int index, Object neu) public void show()
aussatten, den gleichen Methoden, wie sie auch bei der Java-Klasse LinkedList vorkommen.