Implementing Linked Lists with Double Pointers

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.

You must Sign In to use this message board.

FAQ    Noise Tolerance Very HighHighMediumLowVery Low   Layout Expand Posts & RepliesThread ViewNo JavascriptNo JS + Preview   Per page 102550

Msgs 1 to 15 of 15 (Total in Forum: 15) (Refresh) FirstPrevNext

Good article padpub 10:27 31 Dec '05   cool article!!! padpub ---------------- ClickTry Sign In·View Thread·PermaLink 1.00/5 (1 vote) Why Comlicated the base things???? istynet 2:25 19 Oct '04   Your node functions are comlicated...why complicated it???This things are simple.. Ex:AddNodeToStart.... Simple version:(if you know the head like your ex.) AddNodeToStart( node *NewNode) { Head->next=NewNode; NewNode->next=NULL; } And thats all...we make a linked list... I don't have time to explain the others function... All the best! Istvan All the best! Sign In·View Thread·PermaLink 3.00/5 (2 votes) copied Anonymous 4:37 5 Jul '04   copied from http://www.mvps.org/user32/linkedlist.html Sign In·View Thread·PermaLink Re: copied (not really) Niall Barr 5:09 5 Jul '04   If you's checked http://www.mvps.org/user32/ you would notice that it's the article author's own web pages, so fully legitimate duplication. Sign In·View Thread·PermaLink Why write your own ? Christian Graus 15:57 9 Dec '02   I appreciate the article on **, but why did you need to write your own list ? What's wrong with std::list ? Christian No offense, but I don't really want to encourage the creation of another VB developer. - Larry Antram 22 Oct 2002 C# will attract all comers, where VB is for IT Journalists and managers - Michael P Butler 05-12-2002 Again, you can screw up a C/C++ program just as easily as a VB program. OK, maybe not as easily, but it's certainly doable. - Jamie Nordmeyer - 15-Nov-2002 Sign In·View Thread·PermaLink Re: Why write your own ? Matt Gullett 17:18 9 Dec '02   Not trying to support this particular implementation, but I have needed to write my own linked list classes from time-to-time. The STL list (and other containers) have problems when trying to export them from DLLs particularly when exporting them from 2 or more DLLs which are then used together in an app. (I use STLPort and this problem has not gone away.) Usually, though, if I do implement my own linked list I implement the simplest singly-linked form as not to re-invent the wheel too much. Sign In·View Thread·PermaLink Re: Why write your own ? Fayez Asar 14:29 15 Dec '02   Your question is pretty much like a freshman in Computer Science asking why do I need to write a "Hello World" program. The purpose of this article is not to provide you with a better version for Linked List. The author is simply explaining how using double pointers can come in handy in some cases. Sign In·View Thread·PermaLink Re: Why write your own ? Christian Graus 15:52 15 Dec '02   To quote the article: 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. Therefore he wrote his own list for production purposes, hence my asking why. Christian No offense, but I don't really want to encourage the creation of another VB developer. - Larry Antram 22 Oct 2002 C# will attract all comers, where VB is for IT Journalists and managers - Michael P Butler 05-12-2002 Again, you can screw up a C/C++ program just as easily as a VB program. OK, maybe not as easily, but it's certainly doable. - Jamie Nordmeyer - 15-Nov-2002 Sign In·View Thread·PermaLink '**' use for change '*' sayhappy 15:32 9 Dec '02   Pointer's 'hello world' example is 'swap'program. it 'swap' two int variable's value. so you use pointer and learn why use pointer. In this article, 'pRootNode' variable is pointer. so if you like to change pointer's value you have to use pointer's pointer. That's the reason why using pointer's pointer Sign In·View Thread·PermaLink circular link lists Jon 0:10 26 Sep '00   Hi! could any explain or give me some links to go to for circular link lists. How do you go through the list if no pointer in the list is equal to null. Thanks Jo Sign In·View Thread·PermaLink Re: circular link lists Anonymous 10:26 26 Jan '01   All linked list have a pointer to the begining of the list and the end of a list. However, in a circular list, you are merely creating an "illution" of having a "cicular list". In fact there is no such thing!! Here is a hint at what you can do to travers the circular list. If you have a pointer for the begining of the list, and a pointer pointing to the end of the list, then you can use a third pointer to traverse the list as normal. However, when you reach the end of the list (you do this by setting up a condition to let you know that you are at the end of the list), you set the end pointer to point to the begining pointer of the list. Ans so, you have a circular list. Sign In·View Thread·PermaLink 1.20/5 (2 votes) Re: circular link lists Nynaeve 6:38 18 Apr '07   A circular linked list is an "illusion" only as much as a normal linked list is also an "illusion". Both are just pointers that may go all over the available memory space. When the end pointer points back to the beginning, it makes a circle just as much as it would be a straight line if it pointed to NULL. Both are ways of making the human mind conceptualize the data storage. Sign In·View Thread·PermaLink Re: circular link lists Anonymous 23:54 4 Jul '01   u dont sunshine Sign In·View Thread·PermaLink 1.00/5 (1 vote) ** ? mimilafleur 10:09 11 Jun '00   hi this is the first time that i see this kind of notation "**" like in node**. could you please explain what it means thanks mim Sign In·View Thread·PermaLink Re: ** ? Wes Jones 13:15 18 Aug '00   It means that it is a pointer to a pointer. Ie: node** p; is a pointer that points to a node Sign In·View Thread·PermaLink 2.00/5 (2 votes)

Last Visit: 16:44 9 Jul '09     Last Update: 16:44 9 Jul '09 1