Doppelt Verkettete Liste

[Stillmatic]

Hallo DP'ler

Kann mir einer von euch sagen wie man am schlausten ein Element aus einer Doppelt verketteten Liste löscht(egal an welcher Stelle)!

Delphi-Quellcode:

procedure DeleteElement(Index : Integer);
Begin
  Element := getElement(Index);    //Element = das zu löschende Element
  löschen := first;                //First = Meine Komplette Liste

  //Element suchen
  While löschen^.info.ID <> Element.ID do
   Begin
     löschen       := löschen^.previous;
   end;

   //Vorherige Speichern          //Hier Speicher ich die Elemente vor dem zu löschenden Element in temp2
   temp2 := löschen.previous;
   temp2.next := Nil;

   //Next Speichern              //Hier Speicher ich die Elemente nach dem zu löschenden Element in temp
   temp := löschen.next;
   temp.previous := Nil;


  //Element ausschließen        //Nun will ich einfach das Element auschließen!-->also so zu sagen (temp2 + temp)
                                //So das an das Ende von temp2 temp geschrieben wird und somit das zu löschende
                                //Element einfach ausgeschlossen wird(aber ich weiß net wie ich das am besten umsetze)


end;

Wäre nett wenn mir einer bei dem Problem helfen könnte???

[Apollonius]

Was spricht gegen

Delphi-Quellcode:

Element.previous^.next:=Element.next;
Element.next^.previous:=Element.previous;
dispose(Element);

Wenn dasnicht funktioniert, liegt es wahrscheinlich daran, dass ich nicht weiß, was genau Element := getElement(Index); bedeutet.

Edit: Du musst natürlich prüfen, dass Element weder das erste noch das letzte Element der Liste ist, sonst sind die Zeiger nil.

[Stillmatic]

Also das löschen des letzten Elementes klappt, da es bei mir in der Liste(Temp) das oberste Element ist.
Das heißt das das erste Element also das Element was als erstes angelegt wurde ganz unten in der Liste liegt!

Nun hab ich mir ein Abfrage geschrieben die das erste Element löscht!

Delphi-Quellcode:

if Index = 1 then
   Begin
     while temp.previous <> Nil do
       temp := temp.previous;
     temp := temp.next;
     temp.previous := Nil;
   end;

Nun ist aber das Problem das nach dem löschen des ersten Elementes die Reihenfolge der Element vertauscht wird!!
Das heißt das das vorherige letzte Element(also in der Liste ganz oben) nun ganz unten steht!

Gibt es eine einfache Möglichkeit die Reihenfolge der ListenElemente zu tauschen???
Ich komme einfach auf keine andere Lösung, sodass die Elemente vielleicht die richtige Anordnung beibehalten!!

[Apollonius]

Zitat:

Delphi-Quellcode:

temp := temp.next;
     temp.previous := Nil;

Du magst wohl Speicherlecks, hm? Was hieltest du davon, Temp.previous auch mal zu disposen?
Und die Reihenfolge betreffend: Geh die while Schleife doch noch mal rückwärts durch (temp:=temp.next)

[alzaimar]

Man kann einen Listenanfang und ein Listenende definieren. Das sind zwei Knoten der Liste, die keine Daten enthalten aber eben garantiert immer am Anfang bzw. am Ende der Liste sind. Dann muss man nicht auf NIL prüfen.

Eine andere Möglichkeit besteht darin, das das letzte Element nicht auf NIL zeigt (als Nachfolger), sondern wieder auf die Listen-Wurzel (auch so ein Dummy-Element)

Also:

Delphi-Quellcode:

Procedure InitDList (aRoot : TNode);
Begin
  aRoot.lNext := aRoot;
  aRoot.lPrev := aRoot;
End;

Function FirstElement (aRoot : TNode) : TNode;
Begin
  If aRoot.Lnext = aRoot Then 
    Result :=Nil 
  Else 
    Result := aRoot.lNext;
End;

Function LastElement (aRoot : TNode) : TNode;
Begin
  If aRoot.lPrev = aRoot Then 
    Result := Nil 
  Else 
    Result := aRoot.lPrev;
End;

Procedure DeleteNode (aRoot : TNode; aKey : TKey);
Var
  p : TNode;

Begin
  p := FirstElement (aRoot);
  While (p<>nil) And (p.Key <> aKey) Do p := p.lNext; // Complete
  p.lPrev.lNext := p.lNext;
  p.lNext.lPrev := p.lPrev;
  Dispose (p);
End;
...

Ein Element nach seinem Index zu suchen ist eigentlich Schwachsinn, weil man dafür lieber ein Array nimmt.

[Luk3]

Hi DP'ler
habe das gleiche Problem wie Stillmatic.
ICh habe hier eine Doppelt verkettete Liste und möchte jetzt Ein element mitten aus der Liste Löschen.
Nicht am Anfang oder am Ende!

habe das so probiert und mich dabei ein bisschen an den Posts in diesem Thread gehalten:

Delphi-Quellcode:

if ((Index > 1) and (Index < NumberOfElements)) then
   begin


     temp.previous^.next := temp.next;
     temp.next^.previous := temp.previous;
      
      showmessage('In der Mitte'); // dafür geacht damit ich sehe ob das Element wirklich in der Mitte ist
      end;

eigentlich müsste es doch so gehen oder nicht?
aber ich bekomme immer eine Access Violation an der Stelle:

Delphi-Quellcode:

temp.next^.previous := temp.previous;

Wie kommt das?

MFG
Luke

[alzaimar]

na: temp.next ist nil oder nicht definiert (zeigt irgendwo hin).

[Luk3]

Hi!
Doch temp ist initialisiert worden, weiter oben in der Prozedur.

temp := first;

und First ist meine Liste.

könnte dann wirklich nur noch so sein dass temp.next nil ist..
ich werde mal noch rumprobieren müssen, schreibe dann nochmal wenns geklappt hat ^^.