I used to write linked list code in recursive form so that I don’t need to use dummy header node or something like that. This gives me a clear linked list with any extra nodes in it. Of cause, it is in recursive form thus there a memory and time overhead associated with it. The following is the example code.

#include <iostream> using namespace std; struct NODE { int value; NODE *next; } *root; void printList (NODE *root) { while (root != NULL) { cout << root->value << ' '; root = root->next; } cout << endl; } void addNode (NODE **root, int value) { if ((*root)!=NULL && (*root)->value < value) { addNode (&((*root)->next), value); } else { NODE *tmp; tmp = new NODE; tmp->value = value; tmp->next = *root; *root = tmp; } } int main() { srand (time(NULL)); for (int i=0; i<500; i++) addNode (&root, rand() % 1000); printList(root); return 0; }

Once you understand what the pointer to pointer **root is about then the whole program is not much special.

Last week, I had a chance to write code which required the use of linked list again. I suddenly about whether it can be converted to a non-recursive form which is something that did not come to my mind before. It turned out that the non-recursive form is actually very easy to write.

// Non recursive version void addNode (NODE **root, int value) { while ((*root)!=NULL && (*root)->value < value) { root = &((*root)->next); } NODE *tmp; tmp = new NODE; tmp->value = value; tmp->next = *root; *root = tmp; }