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.
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.
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.