Linked lists: an example

The easiest way to store data is in a variable. For one single number this is adequate. If you only want to know how many thermometers you want to control, one CARDINAL will suffice to store this data.
Sooner or later, however, you will want to also know what each of these temperatures is, at this moment. Now, the ARRAY comes in handy. For 'n' elements, the ARRAY [0..n-1] OF CARDINAL will tell you the temperature in mK (milli Kelvin) with ease. No need for floating point numbers.
To complicate things further, you may also want to record the RH (relative humidity) for each sensor location. Now you can do things in two easy ways:

you may add a second ARRAY with the RH values in ppm (parts per million) so that you don't need to use floating point numbers either
you can go the structured way:
- make a RECORD definition
  - RECORD
  - temp : CARDINAL;
  - press : CARDINAL;
  - time : CARDINAL;
  - END
- create an ARRAY [0..n-1] OF AtmosphericData

This all is a major improvement over the starting situation. The problem comes the next day: how will we store all of these data for an undefined number of days to come? We cannot use 'open ended arrays'. Or can we?

Yes we can! We can use dynamic allocation. Just prior to each measurement cycle, we can ask the system to give us some amount of memory that we want to fill to our hearts desire. The OS will do that (if there is still available) and we will receive a POINTER to that area in memory. As long as we keep the RECORD short and the number of data points not too big, we can store a lot of data in the 64 MB which is in the system.
The RECORD definition mentioned above would store 4 million data sets in main memory. That's an awful lot. Too much for arrays, especially in the first 2 million measurements, where the arrays are already eating up memory.
To get familiar with the linked list, I read some texts and finally decided it was time to see if I really understood things. The source below is the result.

MODULE lili;

(*     Linked Lists with Mocka		*)

IMPORT InOut, Strings, SYSTEM;

FROM   MemPools		IMPORT	KillPool, MemPool, NewPool, PoolAllocate;


TYPE   Identifier        = ARRAY [0..57] OF CHAR;
       NamePtr	    	 = POINTER TO NameNode;
       NameNode		 = RECORD
       			      Name	: Identifier;
			      next	: NamePtr
       			   END;

VAR    string		 : Identifier;
       allNames	 	 : MemPool;
       FirstName	 : NamePtr;


PROCEDURE StoreName (str   : Identifier) : BOOLEAN;

VAR	  ThisOne, NextOne   	   : NamePtr;

BEGIN
   ThisOne := FirstName;
   LOOP
      IF  Strings.StrEq (ThisOne^.Name, str)  THEN  RETURN FALSE  END;
      IF  ThisOne^.next = NIL  THEN  EXIT  END;
      ThisOne := ThisOne^.next
   END;
   PoolAllocate (allNames, NextOne, SYSTEM.TSIZE (NameNode));
   ThisOne^.next := NextOne;
   WITH  NextOne^  DO
      next := NIL;
      Name := str
   END;
   RETURN TRUE
END StoreName;


PROCEDURE PrintNames;

VAR	  ThisOne    		: NamePtr;

BEGIN
   ThisOne := FirstName;
   IF  Strings.StrEq (ThisOne^.Name, "Guard")  THEN  ThisOne := ThisOne^.next  END;
   LOOP
      InOut.WriteString (ThisOne^.Name);		InOut.WriteLn;
      IF  ThisOne^.next = NIL  THEN
         EXIT
      ELSE
         ThisOne := ThisOne^.next
      END
   END
END PrintNames;


PROCEDURE Init;

BEGIN
   NewPool (allNames);
   PoolAllocate (allNames, FirstName, SYSTEM.TSIZE (NameNode));
   WITH  FirstName^  DO
      Name := "Guard";
      next := NIL
   END
END Init;


BEGIN
   Init;
   LOOP
      InOut.ReadString (string);
      IF  Strings.StrEq (string, "Exit")  THEN  EXIT  END;
      IF  StoreName (string) = FALSE  THEN
         InOut.WriteString (">>> Duplicate name");
	 InOut.WriteLn
      END
   END;
   PrintNames;
   KillPool (allNames)
END lili.

The source is short and demonstrates how the linked list is initialised, checked, filled and read back. This program is non-standard since it relies on a Mocka specific feature: the MemPool (memory pool) which is a very neat way to allocate and control dynamic memory.

It's all quite straighforward:

Import the functions for MemPools
Initialise the pool
Create an initial element
Create a "guard element" (see PIM and Project Oberon)
Make sure the 'next' pointer has the value 'NIL'
For each new element
- allocate it
- fill it
- put it's address in the 'next' field of the previous last record
Check the syntax with respect to caret (^) and dot (.)
When traversing the list, you start at the first element until 'next' has the value 'NIL'

That's all folks! You may download the source through the Download section.

After I made the simple linked list, as a dynamic equivalent of the ARRAY, I wanted to have a sorted list. It's not very appealing to start sorting an already active list. Too much pointer fumbling involved. There's a better way: the list that sorts itself while filling. Here's the source (which can be downloaded from this site as well):

MODULE lili2;

(*     Linked Lists with Mocka		*)

IMPORT InOut, Strings, SYSTEM;

FROM   MemPools		IMPORT	KillPool, MemPool, NewPool, PoolAllocate;


TYPE   Identifier        = ARRAY [0..57] OF CHAR;
       NamePtr	    	 = POINTER TO NameNode;
       NameNode		 = RECORD
       			      Name	: Identifier;
			      next	: NamePtr
       			   END;

VAR    string		 : Identifier;
       allNames	 	 : MemPool;
       FirstName	 : NamePtr;


PROCEDURE StoreName (str   : Identifier) : BOOLEAN;

VAR	  this, prev, new	   : NamePtr;
	  result   	   	   : INTEGER;

BEGIN
   this := FirstName;
   prev := NIL;
   LOOP
      result := Strings.compare (this^.Name, str);
      IF  result = 0  THEN  RETURN FALSE  END;
      IF  result = 1  THEN  EXIT  END;
      prev := this;
      this := this^.next
   END;
   PoolAllocate (allNames, new, SYSTEM.TSIZE (NameNode));
   new^.Name := str;
   new^.next := this;
   IF  prev = NIL  THEN
      FirstName := new
   ELSE
      prev^.next := new
   END;
   RETURN TRUE
END StoreName;


PROCEDURE PrintNames;

VAR	  ThisOne    		: NamePtr;

BEGIN
   ThisOne := FirstName;
   IF  Strings.StrEq (ThisOne^.Name, "Guard")  THEN  ThisOne := ThisOne^.next  END;
   LOOP
      InOut.WriteString (ThisOne^.Name);		InOut.WriteLn;
      IF  ThisOne^.next = NIL  THEN
         EXIT
      ELSE
         ThisOne := ThisOne^.next
      END
   END
END PrintNames;


PROCEDURE Init;

BEGIN
   NewPool (allNames);
   PoolAllocate (allNames, FirstName, SYSTEM.TSIZE (NameNode));
   WITH  FirstName^  DO
      Name := "|";
      next := NIL
   END
END Init;


BEGIN
   Init;
   LOOP
      InOut.ReadString (string);
      IF  Strings.StrEq (string, "Exit")  THEN  EXIT  END;
      IF  StoreName (string) = FALSE  THEN
         InOut.WriteString (">>> Duplicate name");
	 InOut.WriteLn
      END
   END;
   PrintNames;
   KillPool (allNames)
END lili2.

The main differences are in the StoreName procedure. And I add a guard element in the list. The 'Init' section now is:

PROCEDURE Init;

BEGIN
   NewPool (allNames);
   PoolAllocate (allNames, FirstName, SYSTEM.TSIZE (NameNode));
   WITH  FirstName^  DO
      Name := "|";
      next := NIL
   END
END Init;

The first element is not called 'Guard' anymore, but gets a 'name' that is never used in normal life. The name is a single 'pipe' token (ASCII value 124), well beyond the scope of most names. So this means that in the majority of cases, this element will always be the sentinel (thanks to Niklaus Wirth for this wonderful idea). Which leaves us with only one special case to take into account: the first element.

Below is the procedure 'StoreName'. It has been modified as well.

PROCEDURE StoreName (str   : Identifier) : BOOLEAN;

VAR	  this, prev, new	   : NamePtr;
	  result   	   	   : INTEGER;

BEGIN
   this := FirstName;
   prev := NIL;
   LOOP
      result := Strings.compare (this^.Name, str);
      IF  result = 0  THEN  RETURN FALSE  END;
      IF  result = 1  THEN  EXIT  END;
      prev := this;
      this := this^.next
   END;
   PoolAllocate (allNames, new, SYSTEM.TSIZE (NameNode));
   new^.Name := str;
   new^.next := this;
   IF  prev = NIL  THEN
      FirstName := new
   ELSE
      prev^.next := new
   END;
   RETURN TRUE
END StoreName;

We now keep three POINTERS TO NameNode:

Name	Function
this	'this' is the working pointer. It is used to reference the list element we are to investigate. 'this' is initialised to 'FirstName'.
prev	'prev' is an auxilliary pointer and it lags one step behind the 'this' pointer. It always points to the previous element, with trespect to 'this'. It is initialised to 'NIL'.
new	'new' is the pointer that is needed to allocate space for the new element that needs to be inserted in the list. 'new' will end up between 'prev' and 'this'.

Just download and compile lili2.mod and give it a try. Enter some words in random order. They will be listed (after you have entered 'Exit') in alfabetical order. Also spend some time looking at the MHC equivalent in ../mhc/lili.html since it contains some output as well.

Page created 21 September 2006,

Page equipped with FroogleBuster technology