| Themen |
|
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:
- 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
|