insert()
Die manipulierende Methode insert erzeugt ein neues Listen-Element und fügt dieses neue Element vor dem aktuellen Elemente in die Liste ein. Das neue Element wird dadurch aber nicht zum aktuellen Element.
/**
* 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.
*/
public void insert(Object x)
{
if (isEmpty())
{
first = new Knoten(x,null);
last = first;
act = null; // nur zur Verdeutlichung!
}
else if (hasAccess())
{
if (act == first)
{
Knoten neu = new Knoten(x,first);
first = neu;
}
else
{
Knoten help = first;
while (help.nachfolger != act) help = help.nachfolger;
help.nachfolger = new Knoten(x,act);
}
}
}
Bei dieser Implementation werden zwei Fälle, streng genommen sogar drei Fälle unterschieden.
Fall 1: Die Liste ist leer
In diesem Fall ist die insert-Methode recht einfach gestrickt: Es wird ein neuer Knoten mit dem übergebenen Objekt x erzeugt, und sowohl der first- wie auch der last-Zeiger werden auf diesen neuen Knoten gesetzt. Der act-Zeiger bleibt weiterhin auf null stehen. Die Anweisung
act = null;
habe ich nur zur Verdeutlichung hier aufgenommen. Eigentlich ist diese Zeile überflüssig, weil ja beim Erzeugen der leeren Liste act bereits auf null gesetzt wurde.
Fall 2a: Die Liste ist nicht leer, aber act zeigt auf das erste Element
Wenn die Bedingung act == first erfüllt ist, wird zunächst ein neuer Knoten erzeugt und in der Hilfsvariable neu gespeichert, einem Objekt der Klasse Knoten. Bei der Erzeugung von neu wird als Nachfolger der bisherige first-Knoten übergeben. Anschließend wird first auf den neuen Knoten gesetzt. Somit wurde der neue Knoten vor dem bisherigen first-Knoten gesetzt.
Fall 2b: Die Liste ist nicht leer, und act zeigt auf irgendein Element
Zunächst wird ein Hilfszeiger auf das erste Listen-Element gesetzt:
Knoten help = first;
In der while-Schleife
while (help.nachfolger != act) help = help.nachfolger;
wird geschaut, ob der Nachfolger von help mit dem Knoten identisch ist, auf den act zeigt. Solange das nicht der Fall ist, solange also die Bedingung help.nachfolger != act true ist, wird help auf eine Position weiter rechts gesetzt. Das untere Bild der Abbildung zeigt die Situation vor dem letzten Durchgang der while-Schleife.
Hier sehen wir die Situation, die zur Beendigung der while-Schleife führt. Der Nachfolger von help und der aktuelle Knoten sind identisch; das heißt: help zeigt offensichtlich auf den Vorgänger von act.
Hätten wir die Knoten der Liste nicht einfach verknüpft, sondern doppelt (Nachfolger und Vorgänger), dann wäre dieses Suchen nach der Einfügestelle deutlich schneller gegangen.
Hier sehen wir nun das eigentliche Einfügen des neuen Knotens. Mit der einen Zeile
help.nachfolger = new Knoten(x,act);
wird der neue Knoten nicht nur erzeugt und mit Inhalt gefüllt, sondern auch gleich mit dem bisherigen aktuellen Knoten verknüpft. Der Hilfszeiger help wird nun eigentlich nicht mehr benötigt, und act zeigt weiterhin auf den bisherigen aktuellen Knoten, ganz so, wie es die Vorgaben verlangen.
- Zurück zum Quelltext...
- Weiter mit den letzten Methoden...