Local References Technique

Discover a powerful technique called local references for writing functions on linked lists.

Introduction

We’ve written quite a few functions on linked lists up until this point. A common problem was the need for a special code for the head node of the list. We saw that we need special handling when we try to modify the head or when dealing with an empty list.

For example, insertLast needs special code to handle the case when the list is empty. Only when the list is empty do we have to change the head pointer.

Another example is insertAtPosition, where we need to insert at the beginning of the list, which changes the head pointer.

The technique we’ll see now is called local references and allows us to unify the different cases and treat all nodes in the same way.

Note: The local references technique is never required, as we can write extra code to handle the edge cases. But, since it’s an innovative way of using pointers, we present it here. Mastering this technique will deepen our understanding of pointers.

Local references technique

This technique works by adding another level of indirection.

The different handling of the head comes from the fact that the head node has no predecessor. No next pointer is pointing to it, as is the case for all the other nodes. ...