Löschen eines Elementes in einer einfachen Liste

[sarte]

Hallo Leute,
ich habe eine kleine Frage:
Wenn ein Element am Tailbereich einer einfach verketteten Liste steht und ich es löschen möchte, wie mache ich das am besten?
Die Liste ist im OOP-Stil programmiert, ohne Zeiger.

Delphi-Quellcode:

procedure TElist.delete;
var
  p: TLElement;  // private rechts: TLElement; {Zeigt das nächste Element}  Data  : Integer;  {Dort wird die Information gespeichert}  
   
begin
  if aktuell = head then        // Wenn der Zeiger aktuell sich bei Head befindet, dann ...
  begin
    head := aktuell.GetRechts;     // erhält Head den nächsten Element durch die Methode GetRechts
    aktuell.Free;              // Arbeitsspeicher wird freigegeben
    aktuell:= head;            // Aktuell befindet sich wieder bei Head
  end else
  begin
    if aktuell= tail then      // Wenn der Zeiger aktuell sich bei Tail befindet, dann ...
    begin
      p := head;
      while(p <> NIL) and (p.GetRechts <> aktuell) do //geht man mit Hilfe einer Variable durch die ganze Liste bis man vor Tail steht
        p := p.GetRechts;
      p.setRechts(aktuell.GetRechts);                   //Das Element vor Tail erhält den Wert GetRechts (In dem Fall = NIL)
      aktuell.Free;                                     // Arbeitsspeicher wird freigegeben
      aktuell:= p;                                      // Aktuell befindet sich wieder bei p (das vorletzte Element)
      tail:= p;                                         // tail ist dann p
    end else
    begin                               // Wenn Aktuell zwischen Head und Tail sich befindet
      p := aktuell.GetRechts;           // Wird einfach das Element, welches gelöscht werden soll, mit dem nächsten Element vertauscht
      aktuell.setData(p.GetData);       // aktuell erhält den Wert des nächsten Elementes (vertauscht)
      aktuell.setRechts(p.GetRechts);   // Der Zeiger zeigt auf das übernächste Element  
      p.Free;                           // p wurde deleted ;D
    end;
  end;
  dec(count);
end;

Wie ihr sieht habe ich das Taillöschen programmiert, aber ich bin der Meinung, dass dies überhaupt nicht effizient ist, da man ja durch die Liste durchgehen muss (bis zum vorletzen Element). Bei 100000 Datensätzen kann dies einwenig länger dauern. Wie kann man dies lösen?
Eine Idee hätte ich, man erzeugt eine doppelverkettete Liste, also ein Zeiger der zum vorherigen Element zeigt. Leider darf ich das nicht machen. Es muss eine einfach verkettete Liste sein.
Wenn ihr fragen habt, fragt einfach. Es kann alles verwirrend sein :)
Sarte

[Klaus01]

Hallo,

wie ich gesehen habe, führst Du eine Variable count mit.
Dann müßte das Ende doch:

ende = head + count * sizeOf(pointer) sein.

Wenn ich mich nicht ganz irre.
[edit] wenn denn keine Lücken in der Liste sind [/edit]

Grüße
Klaus

[DeddyH]

Dieses Problem hast Du bei einer einfach verketteten Liste aber immer. Ich wüsste jetzt auch nicht, wie man das anders machen könnte.

[edit] @Klaus: Ich kann mich irren, aber IIRC müssen verkettete Listen nicht unbedingt in einem zusammenhängenden Block im Speicher stehen. [/edit]

[himitsu]

wie ist TElement definiert?

und wie ohne Zeiger? :shock: (bin ich blind, oder denk ich nur welche zu sehn)
[add] OK, sind wohl Objekte, aber kommt auf's Selbe raus


und kannst du die Struktur nicht doch noch etwas ändern?

[sarte]

Zitat:

Zitat von Klaus01

Hallo,

wie ich gesehen habe, führst Du eine Variable count mit.
Dann müßte das Ende doch:

ende = head + count * sizeOf(pointer) sein.

Wenn ich mich nicht ganz irre.
[edit] wenn denn keine Lücken in der Liste sind [/edit]

Grüße
Klaus

kann ich sizeOf überhaupt benutzen? Ich mache das ja ohne Pointer. Mit Create Anweisungen erhalte ich die Adresse (ohne new(pointer).

Ein Beispiel:

Liste: 3 | 4 | 5 | 6 | 9 |

Wenn aktuell sich bei 4 befindet, dann vertausche ich die 4 mit der 5:

3 | 5 | 4 | 6 | 9 |
Und kann dann das Element mit der 4 Löschen, sonst müsste ich zur 3 gehen und dort seinen Zeiger zum nächsten Element ändern.

Wenn aber aktuell bei Tail steht, also die 9

3 | 4 | 5 | 6 | 9 | -> NIL

dann kann ich das nicht so einfach machen, weil da ja NIL steht.

[sarte]

Zitat:

Zitat von himitsu

wie ist TElement definiert?

und wie ohne Zeiger? :shock: (bin ich blind, oder denk ich nur welche zu sehn)
[add] OK, sind wohl Objekte, aber kommt auf's Selbe raus


und kannst du die Struktur nicht doch noch etwas ändern?

Delphi-Quellcode:

type
  TLElement = class
  private
    rechts: TLElement;
    Data  : Integer;
  public
    procedure setData(Daten: Integer);
    procedure setRechts(next: TLElement);
    function GetRechts:TLElement;
    function GetData:Integer;
  end;

Ja ich soll das ohne Zeiger machen -.-

Die Struktur soll leider so bleiben.

[sarte]

Zitat:

Zitat von DeddyH

Dieses Problem hast Du bei einer einfach verketteten Liste aber immer. Ich wüsste jetzt auch nicht, wie man das anders machen könnte.

Wenn das so ist, dann belasse ich das.

Trotzdem danke an euch ;), wenn jemand aber eine Idee hat, bitte melden.

[himitsu]

Wie gesagt, ob Record/Pointer oder Object, ist doch eigentlich egal,

aber wenn du z.B. noch "links" einführst, dann kannst da ganz schnell arbeiten, da von dem Object auf alle nötigen Elemente direkt zugegriffen werden kann.


ansonsten bleibt dir wohl nix anderes übrig, außer (im Notfall) die ganze Liste durchzugehn :?

Delphi-Quellcode:

TComp = Record/Object
  ...
  Owner:      ...;
  Prev, Next: PComp;
End;

If Comp.Owner.FirstComp = Comp Then Comp.Owner.FirstComp := Comp.Next;
If Assigned(Comp.Prev) Then Comp.Prev.Next := Comp.Next;
If Assigned(Comp.Next) Then Comp.Next.Prev := Comp.Prev;
Comp.Free;

head entspricht hier wohl dem Owner

[DeddyH]

head entspricht wahrscheinlich dem ersten Listenelement (irgendwo muss man ja anfangen, sich durchzuhangeln).