Liste
Einführung
Die verkettete Liste ist eine dynamische Datenstruktur, die eine Speicherung von miteinander in Beziehung stehenden Objekten erlaubt. Die Liste wird durch Zeiger auf die jeweils folgende(n) Objekte (hier auch als Knoten bezeichnet) realisiert. Ein Knoten (engl. node) bezeichnet ein Element der Liste, welches die Daten und einen Zeiger auf seinen Nachfolger enthält (Quelle http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29). Die Knoten könne bi- und unidirektional implementiert werden.
Objekte der Klasse List verwalten beliebig viele, linear angeordnete Objekte. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste können durch einen Aufruf zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden. Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.
Im Gegensatz zu Arrays müssen die einzelnen Speicherzellen nicht nacheinander im Speicher abgelegt sein, es kann also nicht mit einfachen Indizies gearbeitet werden um Speicherorte anzusprechen, sondern die Speicherorte müssen absolut referenziert werden. Der Vorteil einer Liste gegenüber einem Array ist, dass das Einfügen und Löschen von Elementen an jedem Punkt in der Liste in konstanter Zeit möglich ist. Dies liegt daran, dass nur Verweise neu gesetzt werden und nicht - wie bei Arrays - alle nachfolgenden Elemente verschoben werden müssen. Die Liste verbraucht jedoch mehr Speicher, da die Verweise auf andere Listenelemente gespeichert werden müssen.
Aufbau
Eine Liste sollte über folgende Methoden bzw. Konstruktoren verfügen:
Konstruktor
List(): Eine leere Liste wird erzeugt.
Methoden
boolean isEmpty(): Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.
boolean hasAccess(): Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.
void next(): Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d.h. hasAccess() liefert den Wert false.
void toFirst(): Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.
void toLast(): Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.
Object getObject(): Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt zurückgegeben, andernfalls (hasAccess()== false) gibt die Anfrage den Wert null zurück.
void setObject(Object pObject): Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pObject ungleich null ist, wird das aktuelle Objekt durch pObject ersetzt. Sonst bleibt die Liste unverändert.
void append(Object pObject): Ein neues Objekt pObject wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pObject in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls pObject gleich null ist, bleibt die Liste unverändert.
void insert(Object pObject): Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues Objekt vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt (hasAccess() == false), wird pObject in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste nicht leer ist oder pObject gleich null ist, bleibt die Liste unverändert.
void concat(List pList): Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls pList null oder eine leere Liste ist, bleibt die Liste unverändert.
void remove(): Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false), bleibt die Liste unverändert.
