Einfach verkettete Listen

[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 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 LastNode.next := CurrentNode; -->
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);