Linked List

Various recursive routines to manipulate linked lists written (a long time ago) using ALGOL 68, classic stuff!

The only changes I’m made to my original code before posting it was to add the GNU Licence.  At the time I originally wrote this code the unofficial aim was to do everything using recursion and I remember being rather pleased with the original sort routine, but commented it out and replaced it with an alternative version using insert as it was a dreadfully inefficient implementation (in all sorts of ways).

Even the final versions show that while recursion may be beautiful it isn’t always best!

{ Linked list manipulation program - 25 May 85 - MEJT  

  This program is free software: you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by the Free
  Software Foundation, either version 3 of the License, or (at your option)
  any later version.

  This program is distributed in the hope that it will be useful, but 
  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  for more details. 

  You should have received a copy of the GNU General Public License along
  with this program.  If not, see 
}

PROGRAM list

BEGIN

   MODE LIST = STRUCT (REF LIST link, STRING data);

   REF LIST empty = NIL;  { Define a nil pointer as an empty list. }
   REF LIST list := empty;  { Define a new list, initially empty. }
   REF LIST new := empty;  { Will hold a new copy of the original list. }

   STRING data;  { String to hold data entered by the user. }

   { Recursive procedure to add an element to the end of the list. }

   PROC add = (REF REF LIST list, STRING data)VOID:

   BEGIN
      IF list IS empty THEN
         list := HEAP LIST := (empty, data)
      ELSE
         add (link OF list, data)
      FI
   END;

   { Recursive procedure to remove an element to the list. }

   PROC delete = (REF REF LIST list, STRING data)VOID:

   BEGIN
      IF list ISNT empty THEN
         IF data OF list = data THEN 
            list := link OF list
         ELSE
            delete (link OF list, data)
         FI
      FI
   END;

   { Recursive procedure to insert an element in to the list in
     alphabetical order. }

   PROC insert = (REF REF LIST list, STRING data)VOID:

   BEGIN
      IF list IS empty THEN
         list := HEAP LIST := (empty, data)
      ELSE
         IF data < data OF list THEN 
            list := HEAP LIST := (list, data)
         ELSE
            insert (link OF list, data)
         FI
      FI
   END;

   { Recursive procedure to copy a linked list. }

   PROC copy  = (REF REF LIST list, new)VOID:

   BEGIN
      IF list ISNT empty THEN
         new := HEAP LIST := (empty, data OF list);
         copy (link OF list, link OF new)
      FI
   END;

   { Recursive procedure to produce a reversed list. }

   PROC reverse  = (REF REF LIST list, new)VOID:

   BEGIN
      IF list ISNT empty THEN
         new := HEAP LIST := (new, data OF list);
         reverse (link OF list, new)
      FI
   END;

   { Recursive procedure to display a linked list. }

   PROC show = (REF REF LIST list)VOID:

   BEGIN
      IF list ISNT empty THEN
         print ((data OF list, ", "));
         show (link OF list)
      ELSE
         print (newline)
      FI
   END;

   { Procedure to produce a sorted list - using insert. }

   PROC sort  = (REF REF LIST list, new)VOID:

   BEGIN
      IF list ISNT empty THEN
         insert (new, data OF list);
         sort (link OF list, new)
      FI
   END;

   { Recursive procedure to sort the contents of a linked list. 

   PROC sort = (REF REF LIST list)VOID:

   BEGIN
      STRING data;
      IF list ISNT empty THEN
         IF link OF list ISNT empty THEN 
            IF data OF list > data OF link OF list THEN 
               data := data OF list;
               data OF list := data OF link OF list;
               data OF link OF list := data;
               sort (list)
            ELSE
               sort (link OF list);
               IF data OF list > data OF link OF list THEN 
                  sort (list)
               FI
            FI
         FI   
      FI
   END; }

   { Start by reading a string from the user and add it to the list
     until the user enters a null string. }

   print (("*** Enter data", newline));
   WHILE (read ((data,newline)); data /= "") DO
      add (list, data);
      show (list)
   OD;

   print (("*** Original list", newline)); 
   show (list);

   { Sort the original linked list into a new sorted list. }

   new := empty;
   sort (list, new);
   print (("*** Sorted list", newline)); 
   show (new);                                              

   print (("*** Original list", newline)); 
   show (list);

   { Reverse the original linked list. }

   new := empty;
   reverse (list, new);
   print (("*** Reversed list", newline)); 
   show (new);

   print (("*** Original list", newline)); 
   show (list);

   { Create a copy of the original linked list. }

   new := empty;
   copy (list, new);
   print (("*** Copied list", newline)); 
   show (new);

   print (("*** Insert into list", newline));
   WHILE (read ((data,newline)); data /= "") DO
      insert (list, data);
      show (list)
   OD;

   print (("*** Delete from list", newline));
   WHILE (read ((data,newline)); data /= "") DO
      delete (list, data);
      show (list)
   OD

END

FINISH

$ run list
*** Enter data
>one
one, 
>two
one, two, 
>three
one, two, three, 
>four
one, two, three, four, 
>five
one, two, three, four, five, 
>six
one, two, three, four, five, six, 
>
*** Original list
one, two, three, four, five, six, 
*** Sorted list
five, four, one, six, three, two, 
*** Original list
one, two, three, four, five, six, 
*** Reversed list
six, five, four, three, two, one, 
*** Original list
one, two, three, four, five, six, 
*** Copied list
one, two, three, four, five, six, 
*** Insert into list
>zero
one, two, three, four, five, six, zero, 
>
*** Delete from list
>three
one, two, four, five, six, zero, 
>
$