Doubly-linked list: remove, wenn nur 1 Listenelement

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Doubly-linked list: remove, wenn nur 1 Listenelement

Beitrag von robertH »

Hallo zusammen,

ich denke, dass der Algorithmus von doubly-linked list: remove http://wiki.algo.informatik.tu-darmstad ... st:_remove
einen Fehler wirft, falls wir versuchen das letzte Listenelement zu löschen. Denn in diesem Fall ist wird unter Punkt 3.1 festgestellt, dass es sich um den Kopf der Liste handel (p.previous = void) und first := p.next gesetzt. Dies ist aber ebenfalls void, wenn es auch das letzte Listenelement ist. Das Problem tritt nun auf wenn first.previous auf void gesetzt werden soll, da auf first.previous nicht zugegriffen werden kann (=void). Vermutlich müsste man diesen Fall vorher abfangen und first und last := void setzen und somit eine leere Liste erzeugen.

Zudem wird unter Punkt 3.3. nicht true zurückgeliefert was aber nach dem linear sequence Artikel machen soll und die Überprüfung in der Induktionsbasis ob first = void ist, kann man sich auch sparen, da es im Induktionsschritt als erstes gemacht wird und p laut Invariante auch void sein darf.

RalfKundel
Erstie
Erstie
Beiträge: 11
Registriert: 17. Apr 2013 15:16
Wohnort: Darmstadt

Re: Doubly-linked list: remove, wenn nur 1 Listenelement

Beitrag von RalfKundel »

Hi,
außerdem werden meiner Ansicht nach nur die Fälle: "K ist das erste element" und "K ist das letzte Element" behandelt.
Der Fall, dass K irgendwo in der Liste ist (ist ja nicht ganz unrealistisch) wird nicht betrachtet. oder ich bin blind.

Der müsste ja irgendwie so aussehen:
p.previous.next := p.next;
p.next.previous := p.previous;

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Doubly-linked list: remove, wenn nur 1 Listenelement

Beitrag von robertH »

In diesem Fall bist du blind. :-)
In 3.1 und 3.2 stehen genau deine geposteten Befehle im otherwise Bereich, also wenn es gerade nicht das erste oder letzte Element ist.

RalfKundel
Erstie
Erstie
Beiträge: 11
Registriert: 17. Apr 2013 15:16
Wohnort: Darmstadt

Re: Doubly-linked list: remove, wenn nur 1 Listenelement

Beitrag von RalfKundel »

danke ;-)

Antworten

Zurück zu „Archiv“