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
will be 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.
Please send any comments or bug reports to me via
email. For any updates to this article, check my site
here.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.