14.3 Data Structures: Linked Lists with Head and Tail Pointers

The operations AddToFront and AddToEnd are two of the most common and important list operations. We have seen that AddToFront is very simple: A node is allocated and a few values copied. On the other hand, we have seen in the previous section that AddToEnd must search the entire list in order to find the last node.

We can make AddToEnd independent of the list length by making a very simple change to our data structures: Keep track of the last node by building in a pointer to it. All we need to do is change the declarations in the PRIVATE part to

    TYPE ListNode;
    TYPE ListPtr IS ACCESS ListNode;
    TYPE ListNode IS RECORD
      Word: WordType := "###";
      Next: ListPtr;
    END RECORD;
    
    TYPE List IS
      Head: ListPtr;
      Tail: ListPtr;
    END RECORD;

This introduces a new type ListPtr, which serves the role of our former List type, and also changes our List type from a simple pointer into a header record containing two pointers, one to the head of the list and one to the tail. This gives a list like

Linked List

The various operations must be modified to reflect the changed data structures. The key change is to AddToEnd, which is shown as Program 14.9. Note that the WHILE loop or recursive call is gone; there is no search necessary because we know immediately where the last node is.

Program 14.9
AddToEnd with Head and Tail Pointers

SEPARATE (Singly_Linked_Lists)
PROCEDURE AddToEnd (L: IN OUT List; Word: IN WordType) IS
------------------------------------------------------------------------
--| AddToEnd using head and tail pointers
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------

BEGIN -- AddToEnd

  IF L.Head = NULL THEN

    L.Head := NEW ListNode'(Word,NULL);
    L.Tail := L.Head;

  ELSE -- L.Tail points to a node; new node goes after it

    L.Tail.ALL.Next := NEW ListNode'(Word,NULL);
    L.Tail := L.Tail.ALL.Next;

  END IF;

END AddToEnd;

This is a very good example of how a small change to a data structure can result in a large change in performance. Here we have used a bit more space for the extra pointer but have eliminated the list search.

We leave it as an exercise to modify the entire package so that the operations are consistent with the two-pointer header record.

Exercises for Section 14.3

Programming

Modify the list package of Section 14.3 (starting with Program 14.1) to implement a list as a record containing head and tail pointers.