2.1 Verkettete Listen
Synopsis: [Wikipedia: Liste (Datenstruktur)] [Class LinkedList<E>] [W3schools: Java LinkedList]
Verkettete Listen dienen zur Speicherung beliebiger Elemente (Zahlen, Strings, Objekte …) im Hauptspeicher. Sie fallen in die Kategorie der dynamischen Datenstrukturen. Hierbei handelt es sich um Datenstrukturen, die beliebig im Hauptspeicher wachsen können, sich aber auch wieder beliebig verkleinern können.
Um eine verkettete Liste realisieren zu können, benötigt man einen Verweis (Zeiger) auf das erste Element der Liste. Jedes Listenelement hat wiederum einen Verweis auf das nächste Listenelement der Liste sowie einen Inhalt.
Unterscheidung der Bezeichnungen für Verweise in verschiedenen Programmiersprachen:
- Java: Verweis auf die ID eines Objekts
- C/C++: Zeiger (Pointer) auf eine Speicheradresse
Hier wird für “Listenelement” als Inhalt ein Integerwert verwendet.
Die Knoten dienen als Verwaltungsstruktur.
Listenelemente können auch Verweise auf andere Objekte (z.B Strings) sein.
Das Ende der Liste wird durch einen Nullverweis (Java: Null), C: Nullpointer, heißt einen Verweis auf „Nichts“ dargestellt.
Wie könnte eine leere Liste nach obigen Schema dargestellt werden?
Beispiel in Java implementieren
Ich habe mich hier gegen den strengen OO-Ansatz entschieden und die Attribute public gemacht um näher am Geschehen zu sein, den Code schlanker zu gestalten. Die VkListe beginnt mit dem Verweis auf den ersten Knoten kopf. Die Listenelemente sind als Integerwerte in den Knoten gespeichert. Die Knoten haben ein Attribut Knoten next als Verweis zum nächsten Knoten.
public class VkListe{
public Knoten kopf;
public void erzeugeTestliste(){
kopf = new Knoten(78);
kopf.next = new Knoten(33);
kopf.next.next = new Knoten(2);
kopf.next.next.next = new Knoten(10);
}
public void ausgebenListe(){
Knoten k = kopf; // k verweist auf den naechsten Knoten
while (k != null){
System.out.print(k.inhalt + " ");
k=k.next;
}
System.out.println();
}
public static void teste(){
VkListe test = new VkListe();
test.erzeugeTestliste();
test.ausgebenListe();
}
}public class Knoten{
public int inhalt;
public Knoten next;
public Knoten(int n){
inhalt = n;
}
}Erstellen Sie ein Klassendiagramm.
Implementieren und testen Sie den Code.
Einfügen von Elementen am Anfang und Ende
Beschreiben Sie, wie das Element mit dem Inhalt 25 am Anfang der Liste eingefügt werden kann.
Lösung
Der next-Verweis des neuen Knotens wird auf den Listenkopf-Verweis gesetzt.
Der Listenkopf-Verweis wird auf die ID des neuen Knotens gesetzt.
Erstellen und testen Sie den Quellcode für eine Operation
addFirst(int n) der Klasse VkListe.
Lösung
public void addFirst(int n){
Knoten k = new Knoten(n);
k.next = kopf;
kopf = k;
}
public static void teste(){
VkListe test = new VkListe();
test.erzeugeTestliste();
test.addFirst(25);
test.ausgebenListe();
}Beschreiben Sie, wie das Element mit dem Inhalt 99 am Ende der Liste eingefügt werden kann.
Lösung
Gehe bis zum Ende der Liste.
Setze den next-Verweis des letzten Elements auf die ID des neuen Elements.
Erstellen und testen Sie den Quellcode für eine Operation
addLast(int n) der Klasse VkListe.
Lösung
public void addLast(int n){
Knoten k = new Knoten(n);
if (kopf == null){
kopf = k;
return;
}
Knoten i = kopf;
while (i.next != null){
i = i.next;
}
i.next = k;
}Durchnummerieren der Elemente
Die Listenelemente bekommen Positionsnummern p = 0,1,2,.. (vergleichbar mit dem Index eines Arrays).
Erstellen und testen Sie den Quellcode für eine Operation
get(int p) der Klasse VkListe, die den Inhalt des p-ten Elements zurückgibt, falls das Element nicht existiert wird 0 zurückgegeben.
Lösung
public int get(int p){
int i = 0;
Knoten k = kopf;
while (k != null){
if(i==p) return k.inhalt;
i++;
k = k.next;
}
return 0;
}Einfügen an Position p
Ein Element n soll an Position p eingefügt werden.
Beschreiben Sie stichwortartig Ihr Vorgehen, um das Einfügen an der Position p zu realisieren.
Lösungsvorschlag
- Durchlaufe die Liste bis zum Element k mit der Positionsnummer p-1 (vorhergehendes Element).
- Erstelle Knoten kn mit Inhalt n.
- Setze kn.next = k.next.
- Setze k.next = kn.
Erstellen und testen (mit p={0,1,6,20}) Sie den Quellcode für eine Operation add(int p,int n) der Klasse VkListe, die das Element n an der Position p einfügt. Falls dies nicht möglich sein sollte wird eine Fehlermeldung auf der Konsole ausgegeben.
Lösung
public void add(int p,int n){
if(p<0){
System.out.println("Negative Position: "+p);
return;
}
Knoten kn = new Knoten(n);
if(p==0){
kn.next = kopf;
kopf = kn;
return;
}
int i = 0;
Knoten k = kopf;
while (k != null){
if(i==p-1){
kn.next = k.next;
k.next = kn;
return;
}
i++;
k = k.next;
}
System.out.println("Einfuegen nicht möglich: "+p);
}Suchen von Elementen
Erstellen Sie den Quellcode für eine Operation enthaelt(int n):Boolean, die true zurück gibt, wenn ein Element n gefunden wurde.
Lösung
public boolean enthaelt(int n){
Knoten k = kopf;
while(k!=null){
if(k.inhalt == n) return true;
k = k.next;
}
return false;
}Die Liste sei nun aufsteigend sortiert. Erstellen Sie eine Operation enthaeltSortiert(int n):Boolean, die true zurück gibt, wenn ein Element n gefunden wurde.
Lösung
public boolean enthaeltSortiert(int n){
Knoten k = kopf;
while(k!=null){
if(k.inhalt == n) return true;
if(k.inhalt > n) return false; // kommt nicht mehr
k = k.next;
}
return false;
}ToDo: Rechenaufwand zwischen unsortierter und sortierter Liste vergleichen. Experiment mit Schleifenzähler und zufälligen Listen und Suchdaten…
Bonus: 🏋️ Sortiertes Einfügen (nicht leicht)
Die Liste sei aufsteigend sortiert. Ein neues Element n soll passend eingefügt werden, ist der Vergleichswert schon vorhanden wird ein Fehler auf der Konsole ausgegeben. Erstellen Sie den Quellcode für eine Operation einfuegenSortiert(int n).
Lösungsvorschlag (wer hat “schönere” Lösung?)
public void einfuegenSortiert(int n){
Knoten nk= new Knoten(n);
if(kopf==null){
kopf = nk;
return;
}
if(kopf.inhalt==n){
System.out.println("Fehler: Inhalt schon vorhanden");
return;
}
if(kopf.inhalt>n){ // davor einfuegen
nk.next=kopf;
kopf=nk;
return;
}
Knoten k = kopf;
while(k.next!=null){
if(k.next.inhalt==n){
System.out.println("Fehler: Inhalt schon vorhanden: "+n);
return;
}
if(k.next.inhalt>n){ // davor einfuegen
nk.next=k.next;
k.next=nk;
return;
}
k=k.next;
}
k.next=nk; // dahinter einfuegen
}Löschen von Elementen
Erstellen Sie eine Operation int removeFirst(), die den Inhalt des ersten Elements zurückgibt und dieses aus der Liste löscht.
Beschreiben Sie stichwortartig, wie das letzte Element aus der Liste gelöscht werden kann.
Lösung
- Gehe zum vorletzten Knoten k der Liste
- Setze k.next = null.
Erstellen Sie eine Operation int removeLast(), die den Inhalt des letzten Elements zurückgibt und dieses aus der Liste löscht.
Sie möchten das Element an der Position p = 2 löschen.
Beschreiben Sie stichwortartig Ihr Vorgehen.
Lösung
- Gehe zum Knoten k mit der Positionsnummer p-1.
- Setze k.next = k.next.next.
Zeichnen Sie die Veränderung der Liste.
Erstellen und testen (mit p={0,1,5,20}) Sie den Quellcode für eine Operation int remove(int p) der Klasse VkListe, die das Element an der Position p löscht und zurück gibt. Falls dies nicht möglich sein sollte wird 0 zurück gegeben.
Ein Kommentar
Kommentare sind geschlossen.