Introduction

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:

• When the list is empty, pRootNode will be NULL. ppScan however will be valid, pointing to pRootNode. *ppScan is thus NULL, the while loop will exit, and the node will be added. As ppScan points to pRootNode, the line "*ppScan = pNewNode;" will set pRootNode to be the new node, and pNewNode->pNext willb e set to NULL.
• When the list is not empty, and the new node must be added to the root of the sorted list, ppScan will be pointing to pRootNode. The compare function takes two node*'s, the node to add (pNewNode), and the node to compare against (*ppScan). "compare" determines that pNewNode should be inserted before *ppScan, so terminates the while loop. ppScan of course points to pRootNode, so the new node is added to the root successfully.
• When the list is not empty, and the new node must be added to the middle of the list, a similar situation to the previous case exists. compare will terminate the while loop, this time with ppScan pointing to the pNext member of the previous element of the linked list. This is overwritten, inserting the new node into the list, and the new nodes next pointer is set to the next element to complete the insertion.
• When the list is not empty and the new node must be added to the end of the list, the compare function will not terminate the loop. *ppScan will become NULL, when the end of the list is reached and the while loop will exit. ppScan however is still valid, pointing to the pNext member of the last node in the linked list. It is simple to set *ppNext (pointer to the pNext member of the last node) to the new node, thus successfully adding the new node to the end of the list.