Einfach verkettete Listen

[Luckie]

So, mein Algorithmen Buch ist da.

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.