unit LinkedList;

{ Implementiert eine Linked List als abstrakten Datentypen.
 Copyright (c) 10/99 by Sebastian Koppehel, <basti@bastisoft.de> }

interface

type
   PList = ^TList;
   TList = record
	      Data : Pointer;
	      Next : PList;
	   end;

{ Cons fügt ein Element am Anfang der Liste an }
procedure Cons(Elem : Pointer; var List : PList);

{ Concat hängt Liste 2 an Liste 1 an; List1 darf nicht nil sein. }
procedure Concat(List1, List2 : PList);

{ ConcatR tut das gleiche, nur rekursiv }
procedure ConcatR(List1, List2 : PList);

{ Head gibt das erste Element der Liste zurück }
function Head(List : PList) : Pointer;

{ Tail gibt den Rest der Liste zurück }
function Tail(List : PList) : PList;

implementation

procedure Cons(Elem : Pointer; var List : PList);
var
   NewList : PList;
begin
   New(NewList);
   NewList^.Data := Elem;
   NewList^.Next := List;
   List := NewList;
end;

procedure Concat(List1, List2 : PList);
begin
   if List1 = nil then exit;
   while List1^.Next <> nil do List1 := List1^.Next;
   List1^.Next := List2;
end;

procedure ConcatR(List1, List2 : PList);
begin
   if List1 = nil then exit;
   if List1^.Next = nil then List1^.Next := List2
   else Concat(List1^.Next,List2);
end;
      
function Head(List : PList) : Pointer;
begin
   Head := List^.Data;
end;

function Tail(List : PList) : PList;
begin
   Tail := List^.Next;
end;

end.