Click here to Skip to main content
Email Password   helpLost your password?

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:

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.
 
 
Per page   
 FirstPrevNext
GeneralGood article
padpub
10:27 31 Dec '05  
cool article!!!

padpub
----------------
ClickTry
GeneralWhy 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!
Generalcopied
Anonymous
4:37 5 Jul '04  
copied from http://www.mvps.org/user32/linkedlist.html
GeneralRe: 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.
GeneralWhy 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

GeneralRe: 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.




GeneralRe: 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.
GeneralRe: 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
General'**' 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

Wink
Generalcircular 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
GeneralRe: 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.
GeneralRe: 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.
GeneralRe: circular link lists
Anonymous
23:54 4 Jul '01  
u dont sunshine
General** ?
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
GeneralRe: ** ?
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


Last Updated 4 Mar 2000 | Advertise | Privacy | Terms of Use | Copyright © CodeProject, 1999-2010