Thread: Dummy Node

Originally posted by NavyBlue
How do I create a dummy node for a linked list?

Thanks!

Node *n;
n = malloc( sizeof( Node ) );

Vola!

Quzah.

>How do I create a dummy node for a linked list?
The same way you create any other node, just place a value in it that you can easily test and tell that it is a dummy node.

-Prelude

What's the purpose of your dummy node? Is it a placeholder for the beginning or end of the list? What exactly? Depending on your use for it, you'll want to change how it gets inserted or checked for.

Quzah.

Originally posted by Salem
> Is this the best way to do it?
No

All you do is move the problem around, it doesn't actually solve anything. Sure insert is now dead easy, but search all of a sudden has a special case (skip the dummy).

I was going to comment on this earlier but didn't. I've never ever found need to use a dummy node. So it takes a few more seconds more to write a line to check for a null list. Gee, that's tough. I donno. I've just never found the need for them.

Quzah.

Originally posted by Salem
> Is this the best way to do it?
No

All you do is move the problem around, it doesn't actually solve anything. Sure insert is now dead easy, but search all of a sudden has a special case (skip the dummy).

Eh, not in my case. Actually, I look one step ahead when doing something in my list. So if I (technically speaking) stand on the first node in my list, I do the operations on the second list.
Do I ever encounter NULL pointer exceptions? No, since I always check if NextNode differs from NULL when I "move on" to the next node.

This is good, since you don't have to use temporary pointers if you're gonna delete a node (you need them to rearrange the previous node's NextNode pointer), and you will never have to deal with the dummy node's data, since you awlays look one step ahead.
To access that data, you have to have a node at locateion -1, and that doesn't exist.

Originally posted by Magos
So if I (technically speaking) stand on the first node in my list, I do the operations on the second list.
Do I ever encounter NULL pointer exceptions? No, since I always check if NextNode differs from NULL when I "move on" to the next node.

I don't see how this differs then from not using one.

Code:

Node *list = NULL;

Node *newNode( type data )
{
    Node *n = malloc( sizeof( Node ) );
    n->prev = n->next = NULL;
    n->data = data;
}

void nukeList( Node *n )
{
    if ( n ) nukeList( n->next );
    free( n );
}

void addNode( Node *n  )
{
    if( list != NULL )
        list->prev = n;
    n->next = list;
    list = n; 
}

Node *getNode( type data )
{
    Node *n;
    for( n = list; n; n = n->next )
        if( n->data == data )
            break;
    if( n )
    {
        if ( n == list )
            list = n->next;
        if( n->next )
            n->next->prev = n->prev;
        if( n->prev )
            n->prev->next = n->next;
        n->prev =  n->next = NULL;
    }
    return n;
}

How does this benifit from having a dummy node?

Quzah.

Silly me, I didn't see this was the C forum. My nodes are classes, thus having their own Add/Delete methods, and since they can't add nor delete themselves, they have to Add/Delete the next object in the list.
True, in C where you have "outer" functions to do the operations, that works better.