sorted doubly linked list

This is a discussion on sorted doubly linked list within the C Programming forums, part of the General Programming Boards category; We have got this code in order to insert a value into a list sorted Code: void insertValue(node *newNode) { ...

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    63

    sorted doubly linked list-why this code work

    We have got this code in order to insert a value into a list sorted
    Code:
    void insertValue(node *newNode)
    {
       node *curr, *prev;
    
       curr = nodeHead;  // nodeHead is a global
       prev = NULL;
       
       // Scan for place to insert (sorted numerically)
       while (curr && curr->data < newNode->data)
         {
    	prev = curr;
    	curr = curr->next;
         }
       
       // Update pointers
       newNode->next = curr;
       newNode->prev = prev;
       
       if (prev == NULL)
         nodeHead = newNode;
       else
         prev->next = newNode;
       
       if (curr == NULL)
         nodeTail = newNode;
       else
         curr->prev = newNode;
    }

    Why the code works also without the last if statement?
    can anyone tell me what is nodetail(probably is the last node of the list)
    in the main program there is no where decleration of nodetail.
    Thanks
    Last edited by alzar; 01-01-2008 at 09:43 AM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by alzar View Post
    Why the code works also without the last if statement?
    It doesn't. The "true" part triggers when the list is empty, or the new element sorts to the back of the list (to set nodeTail to the last (or maybe, only) member of the list).
    can anyone tell me what is nodetail(probably is the last node of the list)
    in the main program there is no where decleration of nodetail.
    Thanks
    I would guess that nodeTail is declared on the same line as nodeHead (or maybe one line after it). If you didn't find it, check your capitalization (if the code compiled, the variable was declared!).

  3. #3
    Registered User
    Join Date
    Aug 2007
    Posts
    63
    will the code work if i put
    current = newNode; instead of
    nodeTail = newNode;

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by alzar View Post
    will the code work if i put
    current = newNode; instead of
    nodeTail = newNode;
    Well, but what is current supposed to be? That's not defined anywhere.

    You'll need nodeTail if you ever plan to walk the list backwards (i.e., starting at the end of the list and working your way back home). If you do plan to do that, then you need to keep nodeTail set correctly in this manner. If you don't ever plan to do that (and your code doesn't ever plan to do that, either) then you can get away without having nodeTail around. However, you still need that if statement with the else part, because that's what sets the backward link to the new element.

  5. #5
    Registered User
    Join Date
    Aug 2007
    Posts
    63
    so can anyone correct the code to work good?
    I also need to walk the list backwards
    Thanks
    Last edited by alzar; 01-01-2008 at 11:45 AM.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    What was wrong with the code you originally posted?

  7. #7
    Registered User
    Join Date
    Aug 2007
    Posts
    63
    Quote Originally Posted by tabstop View Post
    What was wrong with the code you originally posted?
    we didn't know what nodetail was? So as i asked if we put current you said that it will not work.What must we put in nodetail or how should i declare it(or what nodetail is: maybe the last node) in order to work the code as i want?Thanks

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Quote Originally Posted by alzar View Post
    so can anyone correct the code to work good?
    I also need to walk the list backwards
    Thanks
    There isn't really anything wrong with the original code you posted.
    Any time you said that the code would work if you did XXXXX, you were wrong and the original code is right.

    You need to show effort if you want us to help you make it work backwards.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    nodeTail is the end of the list, just as nodeHead is the beginning. They should be declared and initialized together, wherever that is in your program.

  10. #10
    Registered User
    Join Date
    Aug 2007
    Posts
    63
    Quote Originally Posted by tabstop View Post
    nodeTail is the end of the list, just as nodeHead is the beginning. They should be declared and initialized together, wherever that is in your program.

    so i declare it initial in the programm like as struct node *nodetail=NULL;
    and then in a while loop and something like :
    curr = curr->next;
    i will find the last node(which is nodetail).Am i correct?

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by alzar View Post
    so i declare it initial in the programm like as struct node *nodetail=NULL;
    Sounds fine.
    Quote Originally Posted by alzar View Post
    and then in a while loop and something like :
    curr = curr->next;
    i will find the last node(which is nodetail).Am i correct?
    Well, why would you need to find it? As you meddle with the list (inserting or deleting elements), you update nodeTail (and nodeHead, for that matter) as necessary. If you add an element at the back of the list, you make sure nodeTail points there now. (That's what we were doing originally.) If you delete an element from the back of the list, you make sure nodeTail points to the previous node that is now the end of the list.

  12. #12
    Registered User
    Join Date
    Aug 2007
    Posts
    63

    Smile

    Thanks I understand it

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  2. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  3. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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