While working on a project recently I found that some quite advanced programmers did not understand my linked list code. This document was my attempt to explain the method behind the madness.

More Information

The linked list code presented is unexceptional except for one fact: Most of the linked list worker functions work with double pointers (to nodes), whereas more conventional code typically uses single pointers. The double pointer system is used as it has the interesting behavior of trivializing a number of cases that usually have to be handled as special cases when dealing with a plain pointer to node.

I present the following "trivial" linked list node:

struct node {
  node* pNext;
}* pRootNode;

The node struct presented is an example of a very simple singly linked list. pRootNode is a node*, pointing to the root of a linked list of nodes. Each node in the linked list contains a pNext member - a pointer to the next element in the list. If pRootNode is NULL the list is empty, and a pNext member being NULL marks the end of the list.

If we were to make a function to add a node to the start of the list, it may look something like this if we used single rather than double pointers:

void AddNodeToStart(node* pNewNode)
  node* pOldStart = pRootNode;
  pRootNode = pNewNode;
  pNewNode->pNext = pOldStart;

Which is quite simple. The moment we need to either insert a node into a sorted list, or even merely at the end the problem becomes less trivial:

void AddNodeToEnd(node* pNewNode)
  if(pRootNode == NULL){
    pRootNode = pNewNode;
  } else {
    node* pScan = pRootNode;
    while(pScan->pNext != NULL) 
      pScan = pScan->pNext;
    pScan->pNext = pNewNode;

A special case had to be inserted to deal with the "empty list" case. In the case of a sorted list, the comparison would be added to the "while" clause. Also, futher special case code would have to be added to deal with the new "sorted" item being inserted at the root.

Now, contrast the above two functions, with the following function that can add a new node anywhere in a linked list. This method uses double pointers:

void AddNodeSorted(node* pNewNode)
  node** ppScan = &pRootNode;
  while(*ppScan != NULL && compare(*ppScan,pNewNode))
    ppScan = &(*ppScan)->pNext;

  pNewNode->pNext = *ppScan;
  *ppScan = pNewNode;

Notice how the while loop does not need to account for the empty list as a special case.

I will explain how the various cases are handled: