doppelt verkettete Listen

[Mariexshhx]

1 class DoppeltLinkedList :
2 ...
3 function delete ( e ) :
4 if e == head or e == tail :
5 error " Cannot delete head / tail . "
6
7 # Schritt 1 mit p = e . prev
8 e . prev . next = e . next
9
10 # Schritt 2 mit s = e . next
11 e . next . prev = e . prev

Hey ich habe folgenden Pseudocode zum Löschen eines Elements in einer doppelt verkettete Liste doch hier wird doch nicht der Fall berücksicht, falls e gar nicht in der Liste enthalten ist oder sehe ich das falsch ? e wird doch auch gesetzt, wenn es nicht in der Liste enthalten ist?

 

[KonradN]

Der Code ist ja nicht komplett. Das ist nur das Löschen des Elements e (das ein Listenelement ist, das es ja dann geben muss). Das ist aber doch vorher gesucht und gefunden worden. Die Suche dürfte so gebaut worden sein, dass es bei einem nicht finden dann den head oder tail zurück gibt. Und das ist ja die Fehlersituation, die ausgewertet wird.

 

[osion]

1 class DoppeltLinkedList :
2 ...
3 function delete ( e ) :
4 if e == head or e == tail :
5 error " Cannot delete head / tail . "
6
7 # Schritt 1 mit p = e . prev
8 e . prev . next = e . next
9
10 # Schritt 2 mit s = e . next
11 e . next . prev = e . prev

Hey ich habe folgenden Pseudocode zum Löschen eines Elements in einer doppelt verkettete Liste doch hier wird doch nicht der Fall berücksicht, falls e gar nicht in der Liste enthalten ist oder sehe ich das falsch ? e wird doch auch gesetzt, wenn es nicht in der Liste enthalten ist?

Ja, du hast recht. Der Pseudocode berücksichtigt nicht den Fall, dass das Element e gar nicht in der Liste enthalten ist. Wenn e nicht in der Liste enthalten ist, würden Zeile 8 und 11 zu Fehlern führen, da e.prev und e.next dann nicht definiert sind.

Um diesen Fall zu berücksichtigen, könntest du z.B. vor den Schritten 1 und 2 überprüfen, ob e tatsächlich in der Liste enthalten ist. Dazu könntest du z.B. eine boolesche Variable found einführen, die du auf True setzt, sobald du das Element in der Liste gefunden hast. Am Ende der Suche könntest du dann überprüfen, ob found True ist. Wenn ja, könntest du die Schritte 1 und 2 ausführen, andernfalls eine Fehlermeldung ausgeben.

Eine andere Möglichkeit wäre, eine Funktion find(x) zu implementieren, die das Element mit dem Wert x in der Liste sucht und entweder das Element zurückgibt oder None, wenn das Element nicht gefunden wurde. Dann könntest du vor den Schritten 1 und 2 überprüfen, ob find(e) nicht None ist. Wenn ja, könntest du die Schritte 1 und 2 ausführen, andernfalls eine Fehlermeldung ausgeben.