PROGRAM Lists (Input,Output);

TYPE
   RecPtr = ^Rec;
   Rec = Record
       Data : Integer;
       Next : RecPtr;
    End;

VAR
   List, Copy : RecPtr;
   Item : Integer;
   Answer : Char;
   Continue : Boolean;





(*******************************************************************
Insert an item into a linked list. *)

PROCEDURE Insert (Var List : RecPtr; Data : Integer);

Var
   Current, Previous, NewNode : RecPtr;
   Found : Boolean;

Begin
   New(NewNode);
   NewNode^.Data := Data;

   Current := List;
   Found := False;

   WHILE NOT Found AND (Current <> NIL) DO
      IF Data <= Current^.Data THEN
         Found := True
      ELSE
        Begin
          Previous := Current;
          Current := Current^.Next;
        End;

   NewNode^.Next := Current;

   IF List = Current THEN
      List := NewNode
   ELSE
      Previous^.Next := NewNode;
End;





(*****************************************************************
Delete an item from a linked list. *)

PROCEDURE Delete (Var List : RecPtr;  Data : Integer);

Var
   Current, Previous : RecPtr;
   Found : Boolean;

Begin
   Current := List;
   Found := False;

   WHILE NOT Found AND (Current <> NIL) DO
      IF Data = Current^.Data THEN
         Found := True
      ELSE
        Begin
          Previous := Current;
          Current := Current^.Next;
        End;

   IF Found THEN
     Begin
       IF Current = List THEN
          List := List^.Next
       ELSE
          Previous^.Next := Current^.Next;
       Dispose(Current);
     End
   ELSE
      Writeln(Data, ' not in list.');
End;






(*******************************************************************
Display the items in a linked list. *)

PROCEDURE Display (List : RecPtr);

Begin
   WHILE List <> NIL DO
     Begin
       Write(List^.Data:4);
       List := List^.Next;
     End;
   Writeln;
End;




(*******************************************************************
Copy a list. *)

PROCEDURE CopyList (List : RecPtr; Var Copy : RecPtr);

Var
   NewNode, Previous : RecPtr;
   First : Boolean;

Begin
   IF List = NIL THEN
      Copy := NIL
   ELSE
     Begin
       First := True;
       WHILE List <> NIL DO
         Begin
           New(NewNode);
           NewNode^ := List^;
           List := List^.Next;
           IF First THEN
             Begin
               Copy := NewNode;
               First := False;
             End
           ELSE
              Previous^.Next := NewNode;
           Previous := NewNode;
         End
     End;
End;


(*  Test if dipose actually recycles memory. IT DOES.
procedure test;
type
   bigarray = array[1..1000] of integer;
   arrptr = ^bigarray;
var
   p : arrptr;
   i : integer;
begin
   for i := 1 to 1000 do
     begin
       new(p);
       dispose(p);
     End;
   writeln('Must be recycling');
End;
                                *)


BEGIN
   List := NIL;

   Continue := True;

   REPEAT
      Writeln;
      Write('Add, Delete, Print, Copy, or Quit? ');
      Readln(Answer);
      CASE Answer OF
        'A','a' : Begin
                   Write('   Enter item to be inserted: ');
                   Readln(Item);
                   Insert(List,Item);
                  End;
        'D','d' : Begin
                   Write('   Enter item to be deleted: ');
                   Readln(Item);
                   Delete(List,Item);
                  End;

        'P','p' : Display(List);

        'C','c' : Begin
                   CopyList(List,Copy);
                   Display(Copy);
                  End;

        'Q','q' : Continue := False;

         ELSE     Writeln('Invalid option. Again please.');
        End;

   UNTIL NOT Continue;

END.