7.8 Using a Tail Reference

Earlier in the chapter, we saw that new nodes can be easily added to a linked list by prepending them to the linked structure. This is sufficient when the linked list is used to implement a basic container in which a linear order is not needed, such as with the Bag ADT. But a linked list can also be used to implement a container abstract data type that requires a specific linear ordering of its elements, such as with a Vector ADT. In addition, some implementations, such as in the case of the Set ADT, can be improved if we have access to the end of the list or if the nodes are sorted by element value.

The use of a single external reference to point to the head of a linked list is sufficient for many applications. In some instances, however, we may need to append items to the end of the list instead. Appending a new node to the list using only a head reference requires linear time since a complete traversal is required to reach the end of the list. Instead of a single external head reference, we can use two external references, one for the head and one for the tail. Figure 7.8.1 illustrates a sample linked list with both a head and a tail reference.

Figure 7.8.1: Sample linked list using both head and tail external references.

Appending Nodes

Adding the external tail reference to the linked list requires that we manage both references as nodes are added and removed. Consider the process of appending a new node to a non-empty list, as illustrated in Figure 7.8.2 (a). First, a new node is created to store the value to be appended to the list. Then, the node is linked into the list following the last node. The next field of the node referenced by \var{tail} is set to point to the new node. The tail reference has to be adjusted to point to the new node since tail must always point to the last node in the list. The linked list resulting from appending 21 to the list is illustrated in Figure 7.8.2 (b).

Figure 7.8.2: Appending a node to a linked list using a tail reference: (a) the links

required to append the node, and (b) the resulting list after appending 21.

If the list is empty, there is no existing node in which the link field can be adjusted. Instead, both the head and tail references will be null. In this case, the new node is appended to the list by simply adjusting both external references to point to the new node. The code for appending a node to the linked list, which assumes the existence of both the head and tail reference variables, is provided in below:

Removing Nodes

Removing a node from a linked list in which both head and tail references are used requires a simple modification to the code presented earlier in the chapter. Consider the sample list in Figure 7.8.3, in which we want to delete the node containing 21. After unlinking the node to be removed, we must check to see if it was at the end of the list. If it was, we must adjust the tail reference to point to the same node as predNode, which is now the last node in the list. The code for removing an item from a linked list using a tail reference is shown below:

If the list contains a single node, the head reference will be assigned None when it is assigned the contents of the node's next field. The tail reference will also be set to None when it is set to predNode.

Figure 7.8.3: Deleting the last node in a list using a tail reference.