Listen
Verkettete Liste
Eine verkettete Liste (linked list) stellt eine Datenstruktur dar, die aus einer Reihe von Knoten besteht, die miteinander verknüpft sind. Jeder Knoten enthält einen Wert und einen Verweis auf den nächsten Knoten in der Liste. Der letzte Knoten hat keinen Nachfolger und ist entsprechend gekennzeichnet, z. B. durch den Wert null in der Referenz auf das nächste Element.
verkettete Liste (linked list)
- zwei Formen
- einfach verkettet
- doppelt verkettet
- Knoten können leicht eingefügt und gelöscht werden
- Zugriff über Index ist aufwändig
Typische Methoden
prepend: Fügt ein Element vorne einappend: Fügt ein Element am Ende eininsert: Fügt ein Element an einer bestimmten Stelle einremove: Entfernt ein Element an einer bestimmten Stellefind: findet ein Elementsize: gibt die Anzahl der Elemente in der Liste zurückisEmpty: gibt an, ob die Liste leer ist oder nicht
Eine verkettete Liste hat den Vorteil, dass Elemente einfach hinzugefügt oder entfernt werden können, ohne dass die restlichen Elemente verschoben werden müssen.
Es gibt zwei Arten von verketteten Listen: einfach verkettete Listen (engl. singly linked list) und doppelt verkettete Listen (engl. doubly linked list).
- Einfach verkettete Liste: Jeder Knoten enthält einen Wert und einen Verweis auf den nächsten Knoten.
- Doppelt verkettete Liste: Jeder Knoten enthält einen Wert, einen Verweis auf den nächsten Knoten und einen Verweis auf den vorherigen Knoten.
Die erste und die letzten Knoten haben spezielle Bezeichnungen: head und tail.
verkettete Listen sind nützlich in Situationen, in denen häufig Elemente eingefügt oder entfernt werden, da diese Operationen in einer verketteten Liste in der Regel in konstanter Zeit durchgeführt werden können. Ein Nachteil von verketteten Listen ist, dass es schwieriger und zeitaufwendiger ist, ein Element an einer bestimmten Position zu finden, da man durch die Liste iterieren muss, um die richtige Position zu finden.
Einfach verkettete Liste
Die einfach verkettete Liste besteht aus Knoten (Node), die neben den eigentlichen Daten (data) auch noch eine Referenz auf den nächsten Knoten (next) enthalten.
Das folgende Beispiel zeigt eine einfach verkettete Liste, die int-Werte verarbeiten kann. Das Schema lässt sich auf jeden anderen Datentyp erweitern. In der Praxis würde man die Liste als generichen Typ ausprägen, sodass man mit einer Implementierung beliebige Datentypen speichern und verarbeiten kann.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
Die Liste selbst hat nur eine einzige Referenz auf den Anfangsknoten (head).
public class LinkedList {
private Node head;
...
}
Bei einer realen Implementierung würde man aus Effizienzgründen noch weitere Daten mitführen, z. B. die Anzahl der Elemente.
Eine Hilfsmethode last() innerhalb der Liste sucht den letzten Knoten der Liste. Diese Methode würde man bei einer doppelt verketteten Liste nicht benötigen, weil diese ihren Endknoten speichert.
Diese Methode muss die gesamte Liste durchlaufen, benötigt also bei einer Liste der Länge n auch n Schritte, \( \mathcal{O}(n) \).
private Node last() {
Node result = head;
while (result != null && result.next != null) {
result = result.next;
}
return result;
}
Einfach verkettete Liste: append
Das folgende Beispiel zeigt, wie man am Ende der Liste einen neuen Eintrag anfügt. Die Methode append() greift hier auf die last()-Methode zurück, um das Ende der Liste zu finden.
public void append(int data) {
Node newNode = new Node(data);
Node last = last();
if (last == null) {
head = newNode;
}
else {
last.next = newNode;
}
}
Die Benutzung der last()-Methode führt dazu, dass das Anfügen eines Elements bei der einfach verketteten Liste keine effiziente Operation ist.
Die folgende Grafik zeigt, wie das Programm die Liste beim Anfügen verändert.
Einfach verkettete Liste: prepend
Die prepend()-Methode fügt ein Element am Anfang der Liste hinzu. Die Methode is effizient und unabhängig von der Größe der Liste, weil der erste Knoten bekannt ist und nicht gesucht werden muss.
public void prepend(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
newNode.next = head;
head = newNode;
}
Einfach verkettete Liste
Die Grafik zeigt den Ablauf des Hinzufügens eines Elements am Anfang der Liste.
Doppelt verkettete Liste
Das Anfügen von Elemente an eine Liste ist eine sehr häufige Operation in realen Programmen. Gerade hier ist aber die einfach verkettete Liste ineffizient und muss jedes Mal die gesamte Liste durchlaufen, um das Ende zu finden. Dieses Problem löst man mit der doppelt verketteten Liste, bei der jeder Knoten (Node) sowohl seinen Nachfolger (next), als auch seinen Vorgänger (prev) kennt.
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
Die Liste selbst speichert dann sowohl den ersten (head) als auch den letzten Knoten (tail) der Liste.
public class DoubleLinkedList {
Node head;
Node tail;
}
Doppelt verkettete Liste: append
Durch die doppelte Verkettung ist es sehr effizient möglich, neue Knoten am Ende der Liste einzufügen. Der Aufwand dieser Operation ist unabhängig von der Anzahl der Elemente und damit in konstanter Zeit, \( \mathcal{O}(1) \), möglich.
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
return;
}
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
Die Grafik zeigt den Ablauf beim Anfügen eines neuen Elements an das Ende der List.
Doppelt verkettete Liste: prepend
Möchte man ein Element am Anfang der doppelt verketteten Liste anfügen, so unterscheidet sich dieser Vorgang nicht von der einfach verketteten Variante. Der einzige Unterschied ist, dass man eine Referenz mehr (prev) setzen muss.
public void prepend(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
return;
}
newNode.next = head;
head.prev = newNode;
head = newNode;
}
Iterator
Ein Iterator (auch als Zeiger oder Cursor bezeichnet) ist ein abstrakter Datentyp, der es ermöglicht, durch die Elemente einer Datenstruktur (wie z. B. einer Liste oder eines Arrays) zu iterieren, ohne dass die tatsächliche Implementierung der Datenstruktur bekannt ist.
Iterator bietet einheitlichen Zugriff auf unterschiedliche Datenstrukturen (Listen, Sets, …)
Typische Methoden
next: gibt das nächste Element in der Datenstruktur zurück und bewegt den Iterator eine Position weiterhasNext: gibt an, ob es noch weitere Elemente in der Datenstruktur gibtreset: setzt den Iterator zurück auf den Anfang der Datenstruktur
Ein Iterator ermöglicht es, durch die Elemente einer Datenstruktur zu iterieren, ohne dass die tatsächliche Implementierung der Datenstruktur bekannt ist. Es erhöht auch die Wiederverwendbarkeit von Code, da der Iterator unabhängig von der spezifischen Datenstruktur verwendet werden kann.
Beispiel: Ein Iterator kann verwendet werden, um durch die Elemente einer Liste zu iterieren, ohne dass die tatsächliche Implementierung der Liste (z. B. Array, verkettete Liste) bekannt ist. So kann der Iterator auf jede Art von Liste angewendet werden, solange sie die notwendigen Methoden zum Durchlaufen der Elemente bereitstellt.
Ein weiteres Beispiel wäre das Verwenden von einem Iterator für das Durchlaufen durch eine komplexe Datenstruktur wie einem Baum oder einem Graphen.
Das folgende Beispiel zeigt einen einfachen Iterator, der über int-Array iterieren kann.
public class ArrayIterator {
private final int[] array;
private int pos = 0;
public ArrayIterator(int[] array) {
this.array = array.clone();
}
public boolean hasNext() {
return pos < array.length;
}
public int next() {
return array[pos++]; // ArrayIndexOutOfBoundsException
}
public void reset() { pos = 0; }
}
Die clone()-Operation im Konstruktor ist hier eingefügt, damit der Iterator gegen Änderungen des Arrays während der Iteration immun ist. Will man solche Änderungen live im Iterator sehen, muss man das clone() entfernen.