Logo Logo
InfoHome Themen Projekte Links Software
Themen
JavaHamster
BlueJ
Java
Sprachelemente
Abstrakte Datentypen
Array
Array aus Arrays
Keller
Schlange
Liste
Sortierte Liste
Baum
Binärbaum
Swing
Sortieren
HTML
XHTML
CSS
XML
Datenbanken
MySQL
Theoretische Informatik
PHP
Kara
Lego-Roboter
Algorithmen

ADT Liste

Für viele Anwendungen ist es doch eine starke Einschränkung, wenn man nur auf die Enden der Speicherkette zugreifen kann. Sicher könnte man Keller oder Schlange vorübergehend teilweise in einen Zwischenspeicher (am liebsten natürlich wieder in einen linearen ADT) entleeren, bis man das gesuchte Element oder eine passende Einfügestelle gefunden hat. Aber dann muss wieder viel kopiert werden, steigt der Aufwand und ein Zugriff ist nicht mehr unabhängig von der Anzahl der gespeicherten Elemente in einem Schritt zu realisieren. Also wird nun ein Datenspeicher gesucht, der zwar auch wieder linear organisiert und dynamisch ist, aber wo man trotzdem an jeder beliebigen Stelle in (oder vor oder hinter) der Kette der vorhandenen Elemente mit insert ein neues Element einfügen kann, oder wo man sich jedes beliebige Element mit elem ansehen oder es mit delete löschen kann (sofern die Liste nicht leer ist). Zudem muss es noch weitere Methoden zur Auswahl der richtigen Stelle oder des richtigen Elements geben.

Man kann den Datenspeicher (mit reset) sozusagen an den Beginn zurück setzen und/oder mit advance immer von einem gespeicherten Element zum nächsten vorrücken - aber nur nach hinten in Richtung auf das Ende der Speicherkette zu. Es ist nicht möglich, Datensätze in dieser Richtung zu überspringen oder sich umgekehrt um einen Datensatz nach vorne zu bewegen. Die einzige Möglichkeit, nach vorne zu kommen, besteht in der Verwendung von reset, was aber immer direkt nach ganz vorne führt. Mit diesen beiden Methoden, reset und advance, kann man trotzdem jeden Datensatz der Liste auswählen und ihn dadurch zum aktuellen Datensatz erklären. elem und delete zeigen dann das aktuell ausgewählte Element oder löschen es aus dem Speicher.

Mit insert ließe sich ein neues Element vor oder hinter dem aktuellen Element einfügen.

Hält man sich vor Augen, dass man später die einfache Liste vielleicht mal zu einer sortierten Liste erweitern will - also z.B. einen neuen Schüler an die passende Stelle in eine nach Nachnamen alphabetisch sortierte Kursliste aufnehmen will - so hat das Einfügen vor dem aktuellen Element unschätzbare Vorzüge: Um die richtige Stelle z.B. für "Ortmanns" zu finden, muss man mit reset ganz vorne, etwa bei "Bartholomäus" anfangen. Wenn man dann mit advance und elem "Fischer" liest, weiß man noch nicht, ob man "Ortmanns" einfügen kann. Vielleicht kommen noch "Glüsekamp" und "Grüter". Man muss also weiter und weiter gehen. Erst wenn man nach "Möller" endlich auf "Steffen" trifft, weiß man, dass man dazwischen "Ortmanns" einfügen muss(te). Inzwischen ist aber schon "Steffen" aktuell (sonst hätte man den Namen nicht mit elem lesen können). Ein zurück zu "Möller" ist nicht mehr möglich - in der Liste gib's kein Zurück! Nach "Möller" kann also nicht mehr eingefügt werden. Wird aber mit insert vor dem aktuellen Element eingefügt, dann stört es nicht, dass "Steffen" schon aktuell ist - "Ortmanns" kommt dann nämlich genau an die richtige Stelle! Damit man dann auch noch einen Namen wie "Wöhrmeyer" ganz hinten an die Liste anfügen kann, muss man 'aktuell' praktisch noch hinter das letzte Element setzen können. Diese Positionierung des Auswahlzeigers soll durch das Ergebnis true der Kontrollmethode endpos überprüfbar werden.

public interface Liste {

  public boolean empty(); // true, wenn Liste leer, false sonst

  public boolean endpos(); // true, wenn Liste am Ende, false sonst

  public void reset(); // rueckt an den Anfang der Liste

  public void advance(); // rueckt in Liste eine Position weiter

  public Object elem(); // liefert Inhalt des aktuellen Elements

  public void insert(Object x); // fuegt x vor das aktuelle Element ein und macht x zum aktuellen Element

  public void delete(); // entfernt aktuelles Element und macht seinen Nachfolger zum aktuellen Element

}

Liste.java | ZeigerListe.java

/*
* Konzept zur Implementation einer Liste
*
* dummy
* +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
* | | --+-->| B | --+-->| F + --+-->| A | --+-->| C | * |
* +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
* ^ ^ aktuelles
* | | Element
* +-+-+---+ |
* | | + --+-----------------+
* +---+---+
* anf pos
*
*/

public class ZeigerListe implements Liste {

private static class ListenEintrag // innere Klasse
{
Object inhalt; // Inhalt des ListenEintrags
ListenEintrag next; // Verweis auf naechsten ListenEintrag
}

private ListenEintrag anf; // zeigt auf nullten ListenEintrag (dummy)
private ListenEintrag pos; // zeigt vor aktuellen Listeneintrag

public ZeigerListe() // kreiert eine leere Liste
{
pos = anf = new ListenEintrag();
anf.next = null;
}

public boolean empty() // true, wenn Liste leer
{
return anf.next == null;
}

public boolean endpos() // true, wenn am Ende
{
return pos.next == null;
}

public void reset() // rueckt an Anfang
{
pos = anf;
}

public void advance() // rueckt in Liste vor
{
if(!endpos())
{
pos = pos.next;
}
else
{
throw new RuntimeException("Liste.advance: Liste am Ende");
}
}

public Object elem() // liefert aktuelles Element
{
if(!endpos())
{
return pos.next.inhalt;
}
else
{
throw new RuntimeException("Liste.elem: Liste am Ende");
}
}

public void insert(Object x) // fuegt ListenEintrag ein
{
ListenEintrag hilf = new ListenEintrag(); // Das neue Listenelement
hilf.inhalt = x; // kommt vor das aktuelle
hilf.next = pos.next;
pos.next = hilf;
}

public void delete() // entfernt aktuelles Element
{
if(!empty())
{
pos.next = pos.next.next;
}
else
{
throw new RuntimeException("Liste.delete: Liste leer");
}
}

public void print()
{
reset();
while(!endpos())
{
System.out.print(elem() + " ");
advance();
}
System.out.println();
reset();
}

}

 

Aufgabe:

  1. Erweitern Sie die LinkedList (einfach verkettete Liste) zu einer DoubleLinkedList, einer doppelt verketteten Liste. In einer doppelt verketteten Liste merkt sich jedes ListenElement neben seinem Nachfolger auch seinen Vorgänger. Dazu ist es notwendig, der inneren Klasse ListenEintrag ein weiteres Datenfeld für einen Verweis auf das Vorgänger-Objekt zu verpassen. Außerdem gibt es eine zusätzliche Methode, die in der Liste um eine Position zurück rückt. Überdenken Sie ggf. das Implementationskonzept mit dem Dummy-Element...

 

» drucken: pdf | html

© 2004-2024 M. Blanke · Ursulaschule · Kleine Domsfreiheit 11-18 · 49074 Osnabrück