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.