12.11 Variations on the List Theme

One of the difficulties in working with the type of list used so far is that a search for one record in the list must begin with the head pointer and then proceed pointer by pointer, item by item, until the desired object is reached (a strict sequential search.) Keeping a tail pointer around (and updated properly) may help, especially if one frequently appends, but there are other minor improvements that can sometimes gain efficiency.

12.11.1 Circular Lists

A list can "swallow its tail" by having the pointer in the tail item contain the location of the first item, instead of NIL. Now, the position of the head is rather arbitrary, for it is possible to get from any item to any other one. If items were frequently added near each other, it might make sense to change the head pointer so that it always pointed to the most recent insertion.

A list in which the last item points to the first item is said to be circular.

In a circular list, there is in a sense no such thing as a last item, but it is still useful to keep a tail pointer to find the last logical item--after all, it can no longer be found by searching for a NIL pointer. It might also be useful to maintain a variable that stores the number of active items in the list, so that a traverse with a high index number does not waste time by going around the circle and examining items more than once. In such a list, inserting before the head changes the head pointer to point to the new item, and inserting after the tail changes the tail pointer to point to the new item, but both place a new item after the old tail and before the old head in the circle.

12.11.2 Two-Way Lists

Still another scheme would have each data item contain two pointers--one to the previous record in the list and a second to the subsequent one. Naturally, this idea could be combined with the one above and the forward pointer of the tail item could point to the head item and vice-versa, although this additional variation to produce a circular two way list is not shown in figure 12.13.

The following example sketches the declarations and provides the procedure for inserting data items into a two way linked list. The list is a collection of records, consisting of student names in alphabetical order by last name and also containing their grades. The test harness does a few inserts and prints out only the first character of each last name so as to verify the inserting.

MODULE TwoWayList;

(* a very simple test harness
  to demonstrate inserting in
  a two-way linked list
  by R. Sutcliffe  1995 05 23 *)

FROM Strings IMPORT
  Compare, CompareResults;
FROM Storage IMPORT
  ALLOCATE, DEALLOCATE;
FROM STextIO IMPORT
  ReadString, WriteString, WriteChar, WriteLn, SkipLine;

TYPE
  Name = ARRAY [0..10] OF CHAR;
  StudentRecPtr = POINTER TO StudentRec;
  StudentRec =
    RECORD
      last, first : Name;
      mark1, mark2 : REAL;
      toPoint, fromPoint : StudentRecPtr;
    END;
VAR
  head : StudentRecPtr;
  student : StudentRec;

PROCEDURE EnterData (VAR student: StudentRec);

BEGIN
  WITH student
     DO
       WriteString ("Enter the last name ");
       ReadString (last);
     SkipLine;
       (* and continue in this vein *)
      END;
END EnterData;

PROCEDURE WriteData (student: StudentRec);
(* just writing one letter - this is only a test *)
BEGIN
  WITH student
     DO
       WriteChar (last[0]);
       (* and continue in this vein *)
      END;
END WriteData;

PROCEDURE WriteList (p : StudentRecPtr);
BEGIN
  WHILE p # NIL
    DO
      WriteData (p^);
      p := p^.toPoint; (* traverse to next item *)
    END;
  WriteLn;
END WriteList;

PROCEDURE Insert (classMember : StudentRec);
VAR
  temp, point : StudentRecPtr;
BEGIN
  (* handle case of first one to do *)
  IF head = NIL
    THEN
      NEW (head);
      head^ := classMember;
      head^.toPoint := NIL;
      head^.fromPoint := NIL;
      RETURN
    END; (* if *)

  (* all subsequent additions come here *)
  point := head;
  WHILE (point^.toPoint # NIL)
      AND (Compare (classMember.last, point^.last) = greater) 
    DO
      point := point^.toPoint;
    END;
  (* found place at point^ *)
  NEW (temp);    (* so get memory for it *)
  temp^ := classMember;  (* put it there *)
     (* and set up the pointers *)
   
  IF (point^.toPoint = NIL) (* at end so check last one *)
      AND (Compare (classMember.last, point^.last) = greater)
    THEN  (* must append *)
      temp^.fromPoint := point;
      point^.toPoint := temp;
      temp^.toPoint := NIL;
    ELSE (* goes before point ^ *)
      IF point = head 
        THEN (* reset head *)
        head := temp
      ELSE
        point^.fromPoint^.toPoint := temp;
      END;
      temp^.fromPoint := point^.fromPoint;
      point^.fromPoint := temp;
      temp^.toPoint := point;
   END;
  
END Insert;

(* other procedures go here *)

VAR
  count : CARDINAL;
  
BEGIN (* main program does a few inserts *)
  head := NIL;
  FOR count := 1 TO 7
    DO
      EnterData (student);
      Insert (student);
      WriteList (head);
  END;
  
END TwoWayList.

One run log for this test program looked like this:

Enter the last name f
f
Enter the last name l
fl
Enter the last name h
fhl
Enter the last name b
bfhl
Enter the last name b
bbfhl
Enter the last name a
abbfhl
Enter the last name m
abbfhlm

Notice that the program did not actually use the two-way feature of the list in the one procedure presented. One possible use, especially if the list became lengthy would be initiate searches for an item in the last half of the list by starting at the tail item (the pointer would have to be stored, and modifications made even to the one procedure presented here) and working backwards. This would shorten the average search time. A circular list with two index pointers, one for the head and one for the "middle" item (halfway along the list), would require even less search time, but one would have to design the code to search forward or backwards starting at the appropriate one of the three indicated points.


Contents