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 – VE065 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 da b c d e a b c d e a b c d ea b c d e feinordnen(f)Programmierung – VE066 Die verkettete Liste: KonzeptErgebnis: 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 List0..1head 0..10..1 next :List0..1:Node:Node:Node:Node:Node Programmierung – VE067 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 Nachfolgergespeicherter Wert:List abcd Position01 2 3Programmierung – VE068 Die verkettete Liste: Warteliste als Beispiel▪ Fall 3: Der Kunde „a“ verlässt die Warteschlange gespeicherter Wert Referenz auf Nachfolger:ListPosition 0 1 2 ▪ Fall 4: Der Kunde „bb“ kommt hinzu:ListPosition 0 1 2 3Fazit:• Die Positionen sind veränderlich• Liste endet mit der Referenz auf nullbcd bbbcd Programmierung – VE069 Die verkettete Liste: Konzept▪ Listenkopf, „head“, referenziert immer nur den ersten Knoten▪ Ein Knoten kann nicht gleichzeitig der Nachfolger eines anderenKnoten und der erste Knoten einer Liste sein.:List :List :Node:Node:Node:Node:NodeProgrammierung – VE0610 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..1Programmierung – VE0611 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 letztenElements ist size() – 1.▪ Wenn der übergebene Index ungültig ist, dann gibt die Methode nullzurück.Programmierung – VE0616 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 – VE0617 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 – VE0625 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 :List0..1 0..1 prev next0..1 0..1 a b c▪ Das Löschen eines Knotens orientiert sich dann an folgendem Schema:a b c Programmierung – VE0626 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
Reviews
There are no reviews yet.