Dummy Node

This is a discussion on Dummy Node within the C Programming forums, part of the General Programming Boards category; How do I create a dummy node for a linked list? Thanks!...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    23

    Dummy Node

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

    Thanks!

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Re: 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.
    Hope is the first step on the road to disappointment.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    23
    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?

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Apr 2002
    Posts
    23
    The purpose is place it at the begining of the list, so that there's no need to use pList.

  7. #7
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  8. #8
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145

    Wow

    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?

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  10. #10
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  12. #12
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 02:48 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 02:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21