Programmierung
Listen
Michael Goedicke (Basis Volker Gruhn und Mathias Book)
Die verkettete Liste: Motivation
▪ Beispiel: Ein Ordner besteht aus mehreren Dokumenten.
▪ Da ein Dokument nicht in verschiedenen Ordnern enthalten sein kann
und die Entsorgung eines Ordners die Entsorgung der in ihm enthaltenen Dokumente zur Folge hat, wird dieses Szenario wie folgt modelliert:
Ordner
-beschriftung
+einordnen(dokument)
Dokument
-inhalt
:Ordner
:Dokument
:Dokument
Programmierung – VE06
2
:Dokument
Die verkettete Liste: Motivation
▪ In Java kann die Situation mit Hilfe eines Arrays umgesetzt werden: public class Ordner {
private String beschriftung; private Dokument[] dokumente;
public Ordner(String beschriftung) { this.beschriftung = beschriftung; dokumente = new Dokument[5];
}
public void einordnen(Dokument dokument) { }
}
▪ Frage: Wie kann die Methode einordnen() implementiert werden? Programmierung – VE06
3
Die verkettete Liste: Motivation
▪ Idee: Man kann sich die erste freie Stelle des Arrays merken. public class Ordner {
private String beschriftung; private Dokument[] dokumente;
public Ordner(String beschriftung) { this.beschriftung = beschriftung; dokumente = new Dokument[5];
}
public void einordnen(Dokument dokument) { }
}
private int ersteFreieStelle; erste freie Stelle des Arrays
ersteFreieStelle = 0;
das Array ist noch leer
Programmierung – VE06
4
Die verkettete Liste: Motivation
▪ Der erste Entwurf der Methode einordnen() könnte dann folgendermaßen aussehen:
public void einordnen(Dokument dokument) { dokumente[ersteFreieStelle] = dokument; ersteFreieStelle = ersteFreieStelle + 1;
}
▪ Problem: Das Array hat die Länge 5. Daher kann das sechste Dokument nicht ohne weitere Vorkehrungen eingeordnet werden.
public void einordnen(Dokument dokument) {
if (ersteFreieStelle < dokumente.length) {
dokumente[ersteFreieStelle] = dokument;
ersteFreieStelle = ersteFreieStelle + 1; } else {
} }
// Umgang mit der Situation „Array voll“
Programmierung – VE06
5
Die verkettete Liste: Motivation
▪ Wenn mehr als 5 Dokumente eingeordnet werden sollen, dann muss ein neues Array mit der Länge beispielsweise 10 erzeugt werden.
▪ Der Inhalt des alten Arrays muss in das neue Array kopiert werden. einordnen(e)
a
b
c
d
a
b
c
d
e
a
b
c
d
e
a
b
c
d
e
a
b
c
d
e
f
einordnen(f)
Programmierung – VE06
6
Die verkettete Liste: Konzept
Ergebnis: Da sich der Inhalt eines Ordners dynamisch ändert, kann das Szenario mit Arrays nicht gut abgebildet werden.
▪ Dagegen können Listenstrukturen, die sich dynamisch ändern, mit verketteten Listen sehr gut abgebildet werden.
▪ Eine verkettete Liste (engl. „List“) besteht aus Knoten, wobei vom „Listenkopf“ (engl. „head“) nur der erste Knoten der Liste referenziert wird.
▪ Jeder Knoten (engl. „Node“) kann einen Wert speichern und referenziert (d.h. merkt sich) seinen Nachfolger.
Node
-value: Document
List
0..1
head 0..1
0..1 next
:List
0..1
:Node
:Node
:Node
:Node
:Node
Programmierung – VE06
7
Die verkettete Liste: Warteschlange als Beispiel
▪ Ein weiteres Beispiel für eine verkette Liste ist eine Warteschlange an Leuten, die in alphabetischer Reihenfolge der Namen geordnet ist.
▪ Fall 1: Keiner ist in der Warteschlange
▪ Der „Head“ in List referenziert die leere Liste, d.h. er ist null
▪ Fall 2: Kunden mit den Namen „a“, „b“, „c“, „d“ sind in der Warteschlange
▪ Die Liste wird dann häufig durch folgende Notation dargestellt: (Sie endet mit einer Referenz auf null)
Person Person „a“ „b“
Person „c“
Referenz auf Nachfolger
gespeicherter Wert
:List
a
b
c
d
Position
0
1 2 3
Programmierung – VE06
8
Die verkettete Liste: Warteliste als Beispiel
▪ Fall 3: Der Kunde „a“ verlässt die Warteschlange gespeicherter Wert Referenz auf Nachfolger
:List
Position 0 1 2 ▪ Fall 4: Der Kunde „bb“ kommt hinzu
:List
Position 0 1 2 3
Fazit:
• Die Positionen sind veränderlich
• Liste endet mit der Referenz auf null
b
c
d
b
bb
c
d
Programmierung – VE06
9
Die verkettete Liste: Konzept
▪ Listenkopf, „head“, referenziert immer nur den ersten Knoten
▪ Ein Knoten kann nicht gleichzeitig der Nachfolger eines anderen
Knoten und der erste Knoten einer Liste sein.
:List :List
:Node
:Node
:Node
:Node
:Node
Programmierung – VE06
10
Die verkettete Liste: Konzept
▪ Ein Knoten wird in Java durch folgende Klasse implementiert:
public class Node { private Document value;
private Node next;
public Node(Document value) { this.value = value;
0..1 next
Node
-value: Document
}
public Document getValue() { . . . }
public void setValue(Document value) { . . . } public Node getNext() { . . . }
public void setNext(Node next) { . . . }
}
0..1
Programmierung – VE06
11
Die verkettete Liste: Konzept
▪ Wenn eine Liste auf der Konsole ausgegeben werden soll, dann sollte man die toString()-Methode überschreiben:
public class Node { ...
public String toString() { return "[" + value + "]->“;
} }
class Document { String text;
0..1 next
Node
-value:Document
+toString():String
Document (String v)
{ text = v;}
public String toString() {return text;}
}
0..1
main()-Methode
String value = ′′Was wird passieren?′′; System.out.println(
new Node(new Document(value)));
Programmierung – VE06
12
Konsole
[Was wird passieren?]->
Die verkettete Liste: Basisoperationen
▪ Eine verkettete Liste besitzt in der Regel folgende Basisoperationen:
▪ Anhängen eines Elements an das
Ende der Liste
▪ Einfügen eines Elements an einer
bestimmten Position
▪ Löschen aller Elemente aus der Liste
▪ Zugriff auf ein Element über dessen
Position
▪ Bestimmung der Position eines Elements
▪ Bestimmen, ob die Liste leer ist
▪ Löschen eines Elements aus der
Liste
▪ Berechnung der Länge der Liste
List
+add(value:Object):void +add(index:int, value:Object):void +clear():void +get(index:int):Object +indexOf(value:Object):int +isEmpty():boolean +remove(index:int):void +size():int
Programmierung – VE06
13
Die verkettete Liste: Basisoperationen
▪ Eine verkettete Liste ist genau dann leer, wenn sie kein erstes Element besitzt.
a
b
c
Liste ist nicht leer: :List Liste ist leer: :List
▪ Damit erhalten wir:
public void clear() { head = null;
}
public boolean isEmpty() { return head == null;
}
Nicht mehr verlinkte Elemente werden automatisch vom Garbage Collector zerstört
a
b
c
Programmierung – VE06
14
Die verkettete Liste: Basisoperationen
▪ Die Länge der Liste berechnet man mit Hilfe einer Schleife:
public int size() { int size = 0;
Node node = head; while (node != null) {
node = node.getNext();
size = size + 1;
}
return size; }
▪ Die Liste wird dabei mit node = node.getNext() durchlaufen.
node
node
a
b
a
b
node
a
b
Programmierung – VE06
15
Die verkettete Liste: Basisoperationen
▪ Die Liste muss ebenfalls durchlaufen werden, um auf einen Knoten an einer bestimmten Position zuzugreifen:
private Node getNodeAt(int index) { if (index < 0) {
return null; }
int currPos = 0;
Node node = head;
while (currPos < index && node != null) {
node = node.getNext();
currPos = currPos + 1;
}
return node; }
▪ Der Index des ersten Elements ist 0 und der Index des letzten
Elements ist size() – 1.
▪ Wenn der übergebene Index ungültig ist, dann gibt die Methode null
zurück.
Programmierung – VE06
16
Die verkettete Liste: Basisoperationen
▪ Mit Hilfe der gerade gezeigten privaten Methode kann man in der öffentlichen get-Methode auf ein bestimmtes Element zugreifen:
public Document get(int index) { Node node = getNodeAt(index); if (node == null) {
return null; }
return node.getValue(); }
Programmierung – VE06
17
Die verkettete Liste: Basisoperationen
▪ Wenn ein Element an der i-ten Stelle in die Liste eingefügt werden soll, dann geht man folgendermaßen vor:
• Ist i = 0, dann muss der head-Zeiger der Liste umgehängt werden.
• Ist i > 0, dann muss der next-Zeiger des (i-1)-ten Knotens umgehängt
werden.
i > 0:
a
i = 0: :List
b
a
b
c
Programmierung – VE06
18
Die verkettete Liste: Basisoperationen
public void add(int index, Document value) { Node node = new Node(value);
if (index == 0) {
node.setNext(head);
head = node;
} else if (index > 0) {
} }
Node prev = getNodeAt(index – 1); if (prev != null) {
node.setNext(prev.getNext());
prev.setNext(node); }
▪ Wenn ein Element an das Ende der Liste angehängt wird, dann wird es an der Position size() eingefügt (Länge entspricht Index des letzen Listenelements):
public void add(Document value) { add(size(), value);
}
Programmierung – VE06
19
Die verkettete Liste: Basisoperationen
▪ Das Anhängen eines Elements an das Ende der Liste kann man
beschleunigen, indem man die Liste um eine Referenz auf den letzten
Knoten erweitert, sodass kein kompletter Durchlauf erforderlich ist:
0..1
List
0..1
tail
private Node head; private Node tail;
public void add(Document value) { Node node = new Node(value); if (isEmpty()) {
head = node;
tail = head; } else {
Allerdings müssten dann die anderen Methoden entsprechend angepasst werden. Im Folgenden verzichten wir daher auf die Referenz auf den letzten Knoten.
tail.setNext(node);
tail = node;
0..1
head 0..1
}
}
Programmierung – VE06
20
Node
Die verkettete Liste: Basisoperationen
▪ Wenn die Position eines Elements bestimmt werden soll, dann brauchen wir zunächst eine Möglichkeit, um die Elemente der Liste mit dem vorgegebenen Element zu vergleichen.
▪ Dazu realisieren wir die private Klassenmethode isEqual, der zwei zu vergleichende Objekte übergeben werden können:
private static boolean isEqual(Document first, Document second) {
if (first == null) { return second == null;
}
return first.equals(second); }
Programmierung – VE06
21
Die verkettete Liste: Basisoperationen
▪ Mit Hilfe der gerade entwickelten Klassenmethode kann sodann die Position eines Elements bestimmt werden:
public int indexOf(Document value) { int index = 0;
Node node = head; while (node != null
&& !isEqual(node.getValue(), value)) { index = index + 1;
node = node.getNext();
}
return node == null ? -1 : index; }
▪ Die Methode gibt -1 zurück, wenn die Liste das übergebene Element nicht enthält.
▪ Wenn die Liste das übergebene Element enthält, dann gibt die Methode diejenige Position zurück, an der das Element zum ersten Mal auftritt.
Programmierung – VE06
22
Die verkettete Liste: Basisoperationen
▪ Wenn das Element an der i-ten Stelle aus der Liste gelöscht werden soll, dann geht man folgendermaßen vor:
• Ist i = 0, dann muss der head-Zeiger der Liste auf den Nachfolger des ersten Knotens umgehängt werden.
• Ist i > 0, dann muss der next-Zeiger des (i-1)-ten Knotens auf den Nachfolger des i-ten Knotens umgehängt werden.
▪ Man muss sowohl auf den i-ten Knoten als auch auf den (i-1)-ten Knoten zugreifen.
i = 0: :List
i > 0:
a
b
a
b
c
Programmierung – VE06
23
Die verkettete Liste: Basisoperationen
public void remove(int index) { if (index == 0) {
head = head == null ? null : head.getNext(); } else if (index > 0) {
} }
Node node = getNodeAt(index); if (node != null) {
Node prev = getNodeAt(index – 1);
prev.setNext(node.getNext()); }
Zugriff auf den i-ten und den (i-1)-ten Knoten
▪ Wenn getNodeAt(index) != null und index > 0 gilt, dann gilt auch getNodeAt(index – 1) != null.
▪ Da der Knoten an der Stelle index nach einem Aufruf der Methode nicht mehr referenziert wird, wird er vom Garbage Collector aus dem Speicher gelöscht.
Programmierung – VE06
24
Die verkettete Liste: Basisoperationen
▪ Da die Methode getNodeAt() zweimal aufgerufen wird, wird die Liste zweimal durchlaufen. Das ist aber unnötig:
public void remove(int index) { if (index == 0) {
head = head == null ? null : head.getNext(); } else if (index > 0) {
} }
int currPos = 0;
Node prev = null;
Node node = head;
while (currPos < index && node != null) {
currPos = currPos + 1;
prev = node;
node = node.getNext();
}
if (node != null) {
prev.setNext(node.getNext()); }
Programmierung – VE06
25
Die verkettete Liste: Basisoperationen
▪ Den Zugriff auf den i-ten und den (i-1)-ten Knoten kann man vereinfachen, indem die Knoten um einen Zeiger auf ihre Vorgänger erweitert werden.
Node
-value:Document
+toString():String
:List
0..1 0..1 prev next
0..1 0..1
a
b
c
▪ Das Löschen eines Knotens orientiert sich dann an folgendem Schema:
a
b
c
Programmierung – VE06
26
Die verkettete Liste: Basisoperationen
▪ Wenn die Liste auf der Konsole ausgegeben werden soll, dann muss die toString()-Methode überschrieben werden:
public String toString() { Node node = head; String temp = ′′′′; while (node != null) {
temp = temp + node;
node = node.getNext(); }
return temp; }
main()-Methode
List liste = new List(); liste.add(new Document(′′b′′)); liste.add(0, new Document(′′a′′)); System.out.println(liste); liste.remove(1); System.out.println(liste);
Konsole
[a]->[b]->
[a]->
Programmierung – VE06
27
Die verkettete Liste: Beispiel
▪ Nun können wir das Ordner-Modell mit Hilfe einer verketten Liste implementieren:
Ordner
-beschriftung
+einordnen(dokument)
Dokument
-inhalt
public class Ordner {
private String beschriftung;
private List dokumente;
public class Document { private String value; . . .
… } }
Programmierung – VE06
28
Die verkettete Liste: Beispiel
▪ Der Konstruktor der Ordner-Klasse und die einordnen()-Methode haben dann folgende Form:
public Ordner(String beschriftung) { this.beschriftung = beschriftung; dokumente = new List();
}
public void einordnen(Document dokument) { dokumente.add(dokument);
}
Ordner
+einordnen(dokument):void
Document
-titel -inhalt
Programmierung – VE06
29