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:
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.
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.
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.
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.
| You must Sign In to use this message board. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
