Dummy Node

How do I create a dummy node for a linked list?

Thanks!

Quote:

---

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

Thanks...I have another question for you guys...

How would I insert or add that dummy node in the linked list? My program has another function called insertNode that inserts a node when called. Should I create the dummy node in the insertNode function or make a new function to make and add the dummy node?

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.

The purpose is place it at the begining of the list, so that there's no need to use pList.

The whole purpose of the dummy node is that so you don't
have to handle special cases durring insertion etc when the
list is empty.
You probably don't want to malloc it. I would do something like
this

struct Node
{
int data;
struct Node* next;
};

struct Node list;
list.data = 0;
list.next = 0;

Then handle the input functions from there.

I had the same problem, where I had to use special cases when adding/deleteing items from a list. I also found that using a dummy node as the "starting pointer" solved it (though it's a little waste of memory, not a good thing in a programmers view :)).
Is this the best way to do it?

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.