Exemplarisch soll hier das Löschen des aktuellen Listenelements in einer doppelt verketteten Liste erläutert werden.
Bei der einfach verketteten Liste war das Problem, dass man zum Löschen des aktuellen Elements den Nachfolger des aktuellen Elements als Nachfolger beim Vorgänger eintragen musste. Da der Vorgänger aber nicht direkt zugreifbar war, musste man zunächst die Liste solange durchlaufen, bis der Nachfolger eines temporären Zeigers das aktuelle Element war. Damit war dann der Vorgänger des aktuellen Elements gefunden.
Bei einer doppelt verketteten Liste geht das insofern natürlich einfacher, dass der Vorgänger im aktuellen Listenelement gespeichert ist.
Die Schleife in der Methode
while (temp.next!=entferne)
temp=temp.next;
wird daher nun lediglich durch die Anweisung
temp=entferne.prior;
ersetzt.
Zusätzlich müssen in der Methode allerdings jetzt auch die Vorgängerelemente verwaltet werden, so dass der Code zwar länger wird, der algorithmische Aufwand aber durch den Verzicht auf die Schleife sinkt.
Die Methode sieht dann folgendermaßen aus:
public Object aktuellesEntfernen()
{
if (Kopf==null) //leere Liste
return null;
ListenElement entferne=Aktuell, temp=Kopf;
if (entferne==Kopf) //erstes Element entfernen
{
Kopf=Kopf.next;
if (Kopf!=null)
Kopf.prior=null;
Aktuell=Kopf;
}
else
{
temp=entferne.prior;
//Vörgänger von entferne in temp
temp.next=Aktuell.next;
Aktuell=Aktuell.next;
if (Aktuell!=null)
Aktuell.prior=temp;
Aktuell=temp;
}
return entferne.Inhalt;
}
Handelt es sich um das erste Listenelement, dann ist der Kopf der Liste neu auf das zweite Element zu setzen und dort der Vorgänger auf null zu setzen.
Im Falle des Entfernens eines "mittleren" Listenelements entfällt die Schleife. Dafür muss der Vorgänger des Nachfolger des zu löschenden Elements auf den Vorgänger des zu löschenden Elements gesetzt werden.
© Ralph-Erich Hildebrandt, 25. November 2001