Einfach verkettete Listen

[Luckie]

So, mein Algorithmen Buch ist da. :mrgreen:

Es geht um einfach verkettete Listen. Das Funktionsprinzip hatte ich verstanden und wollte sie jetzt mal selber implementieren. Bin aber nicht sehr weit gekommen, so dass ich mir mit Google etwas Beispielcode gesucht habe. Leider habe ich da noch an ein, zwei Stellen Verständnisprobleme, was da passiert bzw. warum es passiert.

Anbei mein kurzes Demo Programm:

Delphi-Quellcode:

// Einfach verkettete Listen - Beispielprogramm
// Michael Puff  [[url]http://www.michael-puff.de][/url]

program SingleLinkedList;

{$APPTYPE CONSOLE}

type
  PNode = ^TNode;
  TNode = record
    data: Integer;
    next: PNode;
  end;

var
  FirstNode: PNode;  // Pseudoknoten
  LastNode: PNode;  // Pseudoknoten
  CurrentNode: PNode;

procedure Init;
begin
  new(FirstNode);
  FirstNode := nil;
  new(LastNode);
  LastNode := nil;
end;

procedure Add(data: Integer);
begin
  new(CurrentNode);
  CurrentNode.data := data;
  new(CurrentNode.next);
  CurrentNode.next := nil;
  if LastNode = nil then
  begin
    FirstNode := CurrentNode;
    LastNode := CurrentNode;
  end
  else
  begin
    LastNode.next := CurrentNode;
    LastNode := CurrentNode;
  end;
end;

procedure InsertNodeAfter(Node: PNode; data: Integer);
var
  NewNode: PNode;
begin
  new(NewNode);
  NewNode.data := data;
  NewNode.next := Node.next;
  Node.next := NewNode;
end;

procedure DeleteNextNode(Node: PNode);
begin
  Node.next := Node.next.next;
end;

procedure WalkTheList;
begin
  Writeln;
  CurrentNode := FirstNode;
  while CurrentNode <> nil do
  begin
    Writeln(CurrentNode.data);
    CurrentNode := CurrentNode.next;
  end;
end;

var
  i: Integer;
  TempNode: PNode = nil;

begin
  Init;
  for i := 0 to 5 do
  begin
    Add(i);
    if i mod 3 = 0 then
      TempNode := CurrentNode;
  end;
  WalkTheList;

  InsertNodeAfter(TempNode, 9);
  WalkTheList;

  Init;
  for i := 0 to 5 do
  begin
    Add(i);
    if i mod 3 = 0 then
      TempNode := CurrentNode;
  end;
  WalkTheList;

  DeleteNextNode(TempNode);
  WalkTheList;

  Readln;
end.

Verständnisprobleme habe ich mit der Prozedur Add. Da weiß ich nicht genau was und warum es passiert. Und die Funktion von den Pseudoknoten ist mir noch etwas schleierhaft. Käme man nicht auch zumindest ohne LastNode aus?

Ich glaube, ich habe es doch verstanden:

Delphi-Quellcode:

procedure Add(data: Integer);
begin
  new(CurrentNode);
  CurrentNode.data := data;
  new(CurrentNode.next);
  CurrentNode.next := nil;
  // Liste leer
  // Ersten und letzten Knoten auf neuen Knoten zeigen lassen
  if LastNode = nil then
  begin
    FirstNode := CurrentNode;
    LastNode := CurrentNode;
  end
  // Liste nicht leer
  // Letzten Knoten auf neuen Knoten zeigen lassen
  // Letzten Knoten zum aktuellen Knoten machen
  else
  begin
    LastNode.next := CurrentNode;
    LastNode := CurrentNode;
  end;
end;

procedure InsertNodeAfter(AfterNode: PNode; data: Integer);
var
  NewNode: PNode;
begin
  // neuen Knoten erzeugen
  new(NewNode);
  NewNode.data := data;
  // Neuer Knoten übernimmt Nachfolger vom Vorgänger
  NewNode.next := AfterNode.next;
  // Vorgänger zeigt auf neuen Knoten
  AfterNode.next := NewNode;
end;

Sind die Kommentare so korrekt?

Und den ersten Knoten braucht man natürlich, um wieder an den Anfang der Liste springen zu können.

Wenn die Kommentare von mir korrekt sind, denke ich, hab eich es verstanden.

[TBx]

also zuerst mal macht sowas

Delphi-Quellcode:

  new(FirstNode);
  FirstNode := nil;

keinen Sinn. Damit produziert man Memoryleaks, es wird Speicher reserviert und die Referenz zu dem selben verworfen. :-(

Jupp, Deine Kommentare sind korrekt.

Lastnode wird verwendet, da man ja auch Knoten in die Liste einfügen kann. Wäre dies nicht der Fall, wäre Currentnode immer gleich LastNode.

[Luckie]

War so in dem Beispielcode aus dem Internet. Das Löschen fehlen der Liste fehlt ja auch noch. Und beim Löschen eines Knotens entsteht auch noch ein Speicherleck. Das ist mir schon bewusst, aber es ging mir erst mal ums Prinzip und das Verständnis.

Allerdings muss ich die beiden Knoten ja mit nil initialisieren. Oder wie würdest du das machen?

Löschen ohne Speicherleck:

Delphi-Quellcode:

procedure DeleteNextNode(Node: PNode);
var
  TempNode: PNode;
begin
  TempNode := Node.next;
  Node.next := Node.next.next;
  Dispose(TempNode);
end;

[TBx]

ja, so würde ich auch löschen.
Nur noch überprüfen, ob es denn überhaupt einen zu löschenden Node gibt ;-)

Delphi-Quellcode:

program SingleLinkedList;

{$APPTYPE CONSOLE}

type
  PNode = ^TNode;
  TNode = record
    data: Integer;
    next: PNode;
  end;

var
  FirstNode: PNode;  // Pseudoknoten
  LastNode: PNode;  // Pseudoknoten
  CurrentNode: PNode;

procedure Init;
begin
  // new(FirstNode);  --> überflüssig, Memoryleak
  FirstNode := nil;
  //new(LastNode);  --> überflüssig, Memoryleak
  LastNode := nil;
end;

procedure Add(data: Integer);
begin
  new(CurrentNode);
  CurrentNode.data := data;
//  new(CurrentNode.next);  --> überflüssig, Memoryleak
  CurrentNode.next := nil;
  if LastNode = nil then
  begin
    FirstNode := CurrentNode;
    LastNode := CurrentNode;
  end
  else
  begin
    LastNode.next := CurrentNode;
    LastNode := CurrentNode;
  end;
end;

procedure InsertNodeAfter(Node: PNode; data: Integer);
var
  NewNode: PNode;
begin
  new(NewNode);
  NewNode.data := data;
  NewNode.next := Node.next;
  Node.next := NewNode;
end;

procedure DeleteNextNode(Node: PNode);
var
  TempNode: PNode;
begin
  if (Node.next <> nil) then
  begin
    TempNode := Node.next;
    Node.next := TempNode.next;
    Dispose (TempNode);
  end;
end;

procedure ClearList;
var
  TempNode: PNode;
begin
  CurrentNode := FirstNode;
  while (CurrentNode <> nil) do
  begin
    TempNode := CurrentNode.Next;
    Dispose (CurrentNode);
    CurrentNode := TempNode;
  end;
  Init;
end;

procedure WalkTheList;
begin
  Writeln;
  CurrentNode := FirstNode;
  while CurrentNode <> nil do
  begin
    Writeln(CurrentNode.data);
    CurrentNode := CurrentNode.next;
  end;
end;

var
  i: Integer;
  TempNode: PNode = nil;

begin
  Init;
  for i := 0 to 5 do
  begin
    Add(i);
    if i mod 3 = 0 then
      TempNode := CurrentNode;
  end;
  WalkTheList;

  InsertNodeAfter(TempNode, 9);
  WalkTheList;

  Init;
  for i := 0 to 5 do
  begin
    Add(i);
    if i mod 3 = 0 then
      TempNode := CurrentNode;
  end;
  WalkTheList;

  DeleteNextNode(TempNode);
  WalkTheList;

  Readln;
end.

[Luckie]

Delphi-Quellcode:

procedure DeleteNextNode(Node: PNode);
var
  TempNode: PNode;
begin
  if Node.next <> nil then
  begin
    TempNode := Node.next;
    Node.next := Node.next.next;
    Dispose(TempNode);
  end;
end;

Fehlt mir noch das Löschen der ganzen Liste. Da habe ich noch keine rechte Idee.

[TBx]

Zitat:

Zitat von Luckie

Fehlt mir noch das Löschen der ganzen Liste. Da habe ich noch keine rechte Idee.

Habs in meinen vorigen Post hineineditiert ;-)

[Luckie]

Zitat:

Zitat von TBx

Habs in meinen vorigen Post hineineditiert ;-)

Jetzt wo ich es sehe... :wall:

Prima. Danke.

Und was machen wir jetzt damit? Code-Lib, ist aber eigentlich kein fertiger Codeschnippsel. Für die Tutorialsparte fehlt wohl noch etwas erklärender Text.

[TBx]

Zitat:

Zitat von Luckie

Und was machen wir jetzt damit?

Hmm, ich kenn da so einen, der schreibt des öfteren Erklährungen, Zusammenfassungen, Tutorials etc. und veröffentlicht diese dann auf seiner Homepage .... :gruebel:

Vielleicht läßt der sich ja dazu überreden, das Tutorial um den fehlenden Text zu bereichern :-D

[Luckie]

Hm, da ich nicht schlafen kann, werde ich mich mal opfern. ;)

[Luckie]

Done: http://www.michael-puff.de/Artikel/D...kedLists.shtml
Es ist etwas mehr geworden. Ich bin noch auf dynamische Arrays eingegangen und hab eich dazu ein kleines Demoprogramm geschrieben. Und es sind noch doppelt verkettete Listen dazu gekommen. Wenn das so weiter geht bin ich bald bei Bäumen. :?

Wird dann auch als Tutorial in der Tutorialsparte eingetragen.

[Delphi-Laie]

Vielleicht darf ich plakative, anschauliche Beispiele hinzusenfen, die Einsteigern für das Erstverständnis helfen könnten (damit behaupte ich nicht einmal unterschwellig, daß meine Vorredner dazugehören):

1. Doppelt verkettete Listen sind z.B. wie die natürlichen (ganzen) Zahlen: Jede hat einen Nachfolger, und (fast (bei den natürlichen Zahlen) jede hat einen Vorgänger.
2. Einfach verkettete Listen sind hingegen wie das Alphabet, wie man es für gewöhnlich lernt: Man lernt es nur vorwärts aufzusagen, mithin hat man erhebliche Probleme, es rückwärts aufzusagen (auch wenn es genaugenommen natürlich auch (fast) immer einen Vorgänger des jeweiligen Buchstabens gibt, aber der ist nicht abrufbereit). Man lernt eben immer nur den Nachfolger eines Buchstabens auswendig. Oder lernte irgendjemand, es rückwärts aufzusagen?

[Luckie]

Mal sehen, ob ich das noch mit einfließen lassen kann. Aber war es denn ansonsten verständlich?

[paperboy]

Hallo Luckie,

Habs mir grad angesehen und muss sagen: Top! Bin Hobbyprogrammierer und hab keine Probleme gehabt den Artikel zu verstehen. Hab mich vor einer weile mal zu verketteten Listen belesen wollen und musste feststellen das es dazu kaum zusammenhängendes (tutorialähnliches) Material im Netz gibt (zumindest nicht was Delphi angeht).

Also vielen Dank für deine Mühe und ein großes Lob für die Qualität und Verständlichkeit!

lg paperboy

[Luckie]

Ja, das musste ich auch feststellen, dass es zu dem Thema verlinkte Listen irgendwie nichts gescheites gibt - oder ich habe es nicht gefunden. Hoffen wir, dass man meins besser im Internet findet. ;)

Und wenn du es als Anfänger verstanden hast, dann scheint es mir auch ganz gut gelungen zu sein. Danke fürs Lesen.

[Delphi-Laie]

Zitat:

Zitat von Luckie

Mal sehen, ob ich das noch mit einfließen lassen kann. Aber war es denn ansonsten verständlich?

Ich überflog es nur, ich tippe aber vorsichtig auf ja, insbesondere die Graphik zum Schluß.

Einfach/doppelt verkettete Listen kenne ich schon seit Turbo-Pascal-Zeiten. Sie liefen darauf hinaus, ein „gezeigertes“ Record zu definieren, das (bei doppelt verketteten) einen Vorgänger und einen Nachfolger enthielten, die denselben Typ wie das Record selbst enthielten, also das Record enthielt sich selbst in einfacher oder doppelter Ausführung. Sicher läßt sich das in dieser Weise auch heute noch programmieren/implementieren. Ich begriff das jahrelang nie, es interessierte mich, ehrlich gesagt, auch nicht. Es kam mir wie ein Rückbezug vor, der in eine unendliche Schleife mündet (Hofstadter läßt grüßen). Ein wenig schwante mir, wie das funktioniert, erst, als ich in mein(em) Sortierprogramm (Sortierkino) Baumstrukturen implementierte.

[DeddyH]

Ich hab mir das verlinkte Tut nicht angeschaut, aber um das richtig "sauber" zu veranschaulichen sollte man nicht auf die Compilermagic vertrauen und ordentlich dereferenzieren ;)

Delphi-Quellcode:

LastNode.next := CurrentNode;

-->

Delphi-Quellcode:

LastNode^.next := CurrentNode;

[Khabarakh]

Was soll das mit Compiler-Magic zu tun haben? Genauso wie -> in C++ ist das ein spezifizierter Teil der Delphi Language. Und da Pointer-Typen nunmal keine Member besitzen, ist es auch eindeutig. Bei der ersten Benutzung einmal erklären und gut is' ;) .

[himitsu]

Zitat:

LastNode^.next

Ich glaub einige Delphi-Versionen mögen sowas ohne ^ eh viel lieber und sagen irgendwas, wenn man hier das ^ nutzt.

Sobald man .irgendwas nutzt, dann ist eh klar, daß hier auf den dereferenzierten Typen zugegriffen wird.

Einzig bei Mehrfachpointern müß man die Zusätzlichen manuell dereferenzieren, da dieses automatische Dereferenzieren nur bei einer Zeigerebene funktioniert.

[Deep-Sea]

Ich würde sagen, da ist noch ein Speicherleck vorhanden: Beim Test wird nach dem Füllen einfach wieder InitList aufgerufen, ohne das vorher manuell oder in InitList automatisch ClearList aufgerufen wird. Somit bleibt die alte Liste ewig im Speicher liegen, da ja keine Referenz mehr auf diese existiert.

Lösung:

Delphi-Quellcode:

procedure InitList;
begin
  ClearList; // Evtl. existierende, alte Liste löschen
  FirstNode := nil;
  LastNode := nil;
end;

Nachtrag: Da ClearList die beiden Pointer aber schon selbst auf nil setzt, kann man sich das in InitList eig. auch sparen - sprich ClearList und InitList sind somit die gleiche Funktion.
Es muss nur darauf geachtet werden, dass FirstNode am Anfang nil ist, also z.B. in initialization setzen.

[hoedlmoser]

Kleines Beispiel, ist schon 15 Jahre alt, funktioniert noch immer und vielleicht hilfts weiter...

Delphi-Quellcode:

// Einfach verkettete Liste
type
  pDirRec = ^tDirRec;
  tDirRec = record
    Path: shortstring;
    Next: pDirRec
  end;

// Erzeugt eine Liste aller Unterverzeichnisse (ohne Rekursion) eines gegebenen Ordners...
function GetDirList(const path: shortstring): pDirRec;
var
  pCurrent, pNode, pPrev: pDirRec;
  sr:  TSearchRec;
begin
  New(Result);
  Result^.Next:= nil;  //das steht sonst eventuell irgendein Datenmüll drin
  if path[length(path)] = '\' then Result^.Path:= ''
  else Result^.Path:= '\';
  pNode:= Result;
  pPrev:= Result;
  repeat
    if Findfirst(path + pNode^.Path + '*.*', faAnyFile, sr) = 0 then begin
      repeat
        if sr.Name[1] = '.' then continue;
        if (sr.Attr and faDirectory) > 0 then begin
          New(pCurrent);
          pCurrent^.Path:= pNode^.Path + sr.name + '\';
          if pNode = Result then pCurrent^.Next:= nil
          else pCurrent^.Next:= pPrev^.Next;
          pPrev^.Next:= pCurrent;
          pPrev:= pCurrent;
        end;
      until FindNext(sr) <> 0;
      FindClose(sr);
    end;
    pNode:= pNode^.Next;
    pPrev:= pNode;
  until pNode = nil;
end;

// ... die man nach Gebrauch wieder freigeben sollte
procedure FreeDirList(pRoot: pDirRec);
var
  pCurrent: pDirRec;
begin
  pCurrent:= pRoot;
  while pCurrent <> nil do begin
    pRoot:= pCurrent^.Next;
    Dispose(pCurrent);
    pCurrent:= pRoot;
  end;
end;

// Verwendung:
var
  pRoot, pCurrent: pDirRec;
  sr: tSearchRec;

  pRoot:= GetDirList('d:\mssql');
  pCurrent:= pRoot;
  while pCurrent <> nil do begin
      if Findfirst('d:\mssql' + pCurrent^.Path + '*.*', faAnyFile, sr) = 0 then begin
        repeat
          if sr.Name[1] = '.' then continue;
          if (sr.Attr and faDirectory = 0) then
            Memo1.Lines.Add('d:\mssql' + pCurrent^.Path + sr.Name + ': ' + DateTimeToStr(FileDateToDateTime(sr.Time)));
        until FindNext(sr) <> 0;
        FindClose(sr);
      end;
    pCurrent:= pCurrent^.Next;
  end;
  FreeDirList(pRoot);

[p80286]

Ich bin da nicht ganz zufrieden:

Delphi-Quellcode:

procedure ClearList;
var
  TempNode: PNode;
begin
  CurrentNode := FirstNode;
  while (CurrentNode <> nil) do
  begin
    TempNode := CurrentNode.Next;
    Dispose (CurrentNode);
    CurrentNode := TempNode;
  end;
  FirstNode := nil;
  LastNode := nil;
end;

Wenn es den FirstNode und den LastNode gibt sollte mann sie auch nutzen, wobei bei den einfach verketteten Listen der LastNode eigentlich überflüssig ist.

Delphi-Quellcode:

procedure ClearList;
// ---- TempNode ist überflüssig
//var
//  TempNode: PNode;
begin
  CurrentNode := FirstNode;
  repeat
    FirstNode:=FirstNode^.Next;   // FirstNode zeigt immer auf den ersten gültigen... 
    dispose(CurrentNode);         // Freigeben
    CurrentNode:=FirstNode;       // CurrentNode nachziehen   
  until CurrentNode=Nil;  
  //FirstNode := nil;         ----das ist er schon!!
  LastNode := FirstNode;
end;

Mir gefällt hier "Return until" besser, weil es mir logischer erscheint.

Edit:
einfügen von Daten an beliebiger Stelle in eine doppelt verkettete Liste:

Delphi-Quellcode:

{ FirstNode ist wirklich der erste! }
{ CurrentNode enthält Daten und .next und .last sind mit Nil vorbelegt!        }
begin
  LastNode:=FirstNode;
  While (LastNode.next<>Nil) and (LastNode^.data<>MeineBedingung) do LastNode:=LastNode^.next;
  {-- vor LastNode einfügen --}
  CurrentNode^.last:=LastNode^.last;
  CurrentNode^.last^.next:=CurrentNode;
  CurrentNode^.next:=LastNode;
  LastNode^.last:=CurrentNode;
  {-- nach LastNode einfügen --}
  CurrentNode^.last:=LastNode;
  CurentNode^.next:=LastNode^.next;
  LastNode^.next:=CurrentNode;
  if CurrentNode^.next<>Nil then
    currentNode^.next^.last:=CurrentNode;
end;

Gruß
K-H

[TBx]

Zitat:

Zitat von p80286

Mir gefällt hier "Return until" besser, weil es mir logischer erscheint.

Repeat Until ist hier definitiv falsch, Wendet man ClearList nun an, wenn noch kein Node existiert, knallt es!

Klar ist es möglich, den TempNode zu umgehen. Fragt sich nur, was besser zu verstehen ist.

[p80286]

Jo das kommt davon wenn man altes Zeug einfach kopiert!
Die Abfrage

Delphi-Quellcode:

If FirstNode<>nil then

hatte ich geschlabbert.

Nach Meinem Verständnis ist der FirstNode der Anker der Liste, und der CurrentNode ist der "Gleiter".
Darum will ich nicht noch eine weitere Variable einführen, mit der ich an der Liste arbeite.

Gruß
K-H

[Bjoerk]

Ich habe mir das Tutorium von Michael Puff dieser Tage auch mal näher angesehen und daraus nachfolgende unit erstellt. Könnte mal jemand kurz drüber schauen, ob das Ganze soweit okay ist, ob ich nicht irgendwelche Speicherlecks produziere und ob man sich das inherited sparen kann, sofern es sich nur auf TObject bezieht? Danke!

Delphi-Quellcode:

unit EinfachVerketteteListen;

interface

uses
  Classes;

type
  TData = record
    Name: string;
  end;
  PNode = ^TNode;
  TNode = record
    Data: TData;
    Next: PNode;
  end;
  Tliste = class(TObject)
    function Count: integer;
    procedure clearItem(Index: integer);
    procedure AddItem(Data: TData);
    function GetItem(Index: integer): TData;
    procedure SetItem(Index: integer; Data: TData);
    procedure DelItem(Index: integer);
    procedure InsItem(Index: integer; Data: TData);
    procedure Exchange(Index1,Index2: integer);
    procedure SortByName;
    function IndexOfName (Name: string) : integer;
  private
    FirstNode, LastNode, CurrentNode: PNode;
    procedure InitList;
    procedure ClearList;
    procedure AddNode(Data: TData);
    procedure InsertNodeAfter(AfterNode: PNode; Data: TData);
    procedure DeleteNextNode(Node: PNode);
    function GetNode(Index: integer): PNode;
    Procedure Null(var Data: TData);
  public
    constructor Create;
    destructor Destroy; override;
  end;

implementation

procedure TListe.InitList;
begin
  FirstNode := nil;
  LastNode := nil;
end;

constructor TListe.Create;
begin
  inherited Create;
  InitList;
end;

procedure TListe.ClearList;
var
  Node: PNode;
begin
  CurrentNode := FirstNode;
  while (CurrentNode <> nil) do
  begin
    Node := CurrentNode.Next;
    Dispose (CurrentNode);
    CurrentNode := Node;
  end;
  InitList;
end;

destructor TListe.Destroy;
begin
  ClearList;
  inherited;
end;

procedure TListe.AddNode(Data: TData);
begin
  New(CurrentNode);
  CurrentNode.Data := Data;
  CurrentNode.Next := nil;
  if LastNode = nil then
  begin
    FirstNode := CurrentNode;
    LastNode := CurrentNode;
  end
  else
  begin
    LastNode.Next := CurrentNode;
    LastNode := CurrentNode;
  end;
end;

procedure TListe.InsertNodeAfter(AfterNode: PNode; Data: TData);
var
  Node: PNode;
begin
  New(Node);
  Node.Data := Data;
  Node.Next := AfterNode.Next;
  AfterNode.Next := Node;
end;

procedure TListe.DeleteNextNode(Node: PNode);
var
  TempNode: PNode;
begin
  if Count>1 then
  begin
    if Node.Next <> nil then
    begin
      TempNode := Node.Next;
      Node.Next := Node.Next.Next;
      Dispose(TempNode);
    end
  end
  else
    ClearList;
end;

function TListe.Count: integer;
begin
  Result := 0;
  CurrentNode := FirstNode;
  while CurrentNode <> nil do
  begin
    CurrentNode := CurrentNode.Next;
    Result := Result + 1;
  end;
end;

function TListe.GetNode(Index: integer): PNode;
var
  i: integer;
begin
  i:=0;
  CurrentNode := FirstNode;
  while ((CurrentNode <> nil) and (i < Index)) do
  begin
    i:= i+1;
    CurrentNode := CurrentNode.Next;
  end;
  Result:=CurrentNode;
end;

procedure TListe.Null(var Data: TData);
begin
  with Data do
  begin
    Name := '';
  end;
end;

procedure TListe.ClearItem(Index: integer);
var
  Node: PNode;
begin
  Node := GetNode(Index);
  Null(Node.Data);
end;

procedure TListe.AddItem(Data: TData);
begin
  AddNode(Data);
end;

function TListe.GetItem(Index: integer): TData;
var
  Node: PNode;
begin
  Null(Result);
  Node := GetNode(Index);
  Result := Node.Data;
end;

procedure TListe.SetItem(Index: integer; Data: TData);
var
  Node: PNode;
begin
  Node := GetNode(Index);
  Node.Data := Data;
end;

procedure TListe.DelItem(Index: integer);
var
  Node: PNode;
begin
  Node := GetNode(Index-1);
  DeleteNextNode(Node);
  FirstNode := GetNode(0);
  LastNode := GetNode(Count-1);
end;

procedure TListe.InsItem(Index: integer; Data: TData);
var
  Node: PNode;
begin
  Node := GetNode(Index);
  InsertNodeAfter(Node,Data);
  FirstNode := GetNode(0);
  LastNode := GetNode(Count-1);
end;

procedure TListe.Exchange(Index1,Index2: integer);
var
  Data1,Data2: TData;
begin
  Data1 := GetItem(Index1);
  Data2 := GetItem(Index2);
  SetItem(Index1,Data2);
  SetItem(Index2,Data1);
end;

procedure TListe.SortByName;
var
  i,j: integer;
begin
  for i := 0 to Count - 2 do
    for j := i+1 to Count - 1 do
      if GetItem(i).Name > GetItem(j).Name then Exchange(i,j);
end;

function TListe.IndexOfName (Name: string): integer;
var
  i: integer;
begin
  result := -1;
  for i := 0 to Count - 1 do
    if GetItem(i).Name = Name then
    begin
      result := i;
      break;
    end;
end;

end.

[p80286]

Hallo Bjoerk,

mir ist da nichts aufgefallen. Allerdings hätte ich an Deiner Stelle eine doppelt verkettete Liste genommen, das erspart den immer wiederkehrenden Einstieg über Firstnode.

Das hier solltest Du einmal überdenken, da meiner Meinung nach FirstNode FirstNode bleibt, bist FirstNode=NIL!

Delphi-Quellcode:

procedure TListe.DelItem(Index: integer);
var
  Node: PNode;
begin
  Node := GetNode(Index-1);
  DeleteNextNode(Node);
  FirstNode := GetNode(0);
  LastNode := GetNode(Count-1);
end;

Und die Definition von TData ist irgendwie doppelt gemoppelt.

Gruß
K-H

[Bjoerk]

thanx!

Wie ist das mit dem inherited (Siehe letzten Teil der Frage)? Ist das erforderlich?

[p80286]

Mit Gewissheit kann ich es Dir nicht beantworten, Zu dem Thema gab es hier schon einmal eine Diskussion, aber es ist eigentlich nicht falsch.

Gruß
K-H

Edith:
War da nicht etwas mit Free und Destroy?

Zitat:

Beschreibung

Mit Free wird ein Objekt freigegeben. Wenn die Objektreferenz nicht nil ist, wird Destroy aufgerufen. Alle zur Laufzeit instantiierten Objekte, die keinen Eigentümer besitzen, sollten mit Free aufgelöst werden, damit sowohl das Objekt als auch der zugehörige Speicher korrekt freigegeben wird. Im Gegensatz zu Destroy funktioniert Free auch dann, wenn das Objekt nil ist. Es ist also kein Fehler, die Methode für ein Objekt aufzurufen, das niemals initialisiert wurde.

Wenn Sie Free für eine Komponente aufrufen, werden alle untergeordneten Objekte (die Einträge in ihrer Komponentenliste) automatisch freigegeben. Da ein Formular der Eigentümer aller Steuerelemente und anderer Komponenten ist, die Sie im Entwurfsmodus hinzugefügt haben, werden diese Komponenten automatisch mit dem Formular freigegeben. Alle Formulare gehören standardmäßig zum Anwendungsobjekt (TApplication) und werden daher zusammen mit diesem aus dem Speicher entfernt. Bei Objekten, die keine Komponenten sind, oder bei mit dem Eigentümer nil erstellten Komponenten muss Free explizit aufgerufen werden, wenn das betreffende Objekt nicht mehr benötigt wird. Der zugewiesene Speicher kann sonst erst nach dem Beenden der Anwendung wieder verwendet werden.

[mleyen]

Indexe sind aber nicht der Sinn von verketteten Listen. Dabei besser zu TList greifen.

[Bjoerk]

wird bezüglich inherited dort fortgesetzt:

http://forum.delphi-treff.de/showthr...170#post218170