Adding nodes to a list

This is a discussion on Adding nodes to a list within the C Programming forums, part of the General Programming Boards category; I have two functions that should be doing the same thing, and I can't quite figure out why the first ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174

    Adding nodes to a list

    I have two functions that should be doing the same thing, and I can't quite figure out why the first works but the second doesn't.

    1)

    Code:
    NodeT *addNode(NodeT *list) {
        NodeT *new = NULL;
        NodeT *cur = NULL;
        
        new = malloc(sizeof(NodeT));
        if (new == NULL) {
            fprintf(stderr, "Out of memory\n");
            exit(1);
        }
        
        if (list == NULL) {
            list = new;
        } else {
            cur = list; 
            while (cur->next != NULL) {
                cur=cur->next;
            }
            cur->next = new;
        }
        
        new->next = NULL;
        
        return list;
    }

    2)

    Code:
    NodeT *addNode(NodeT *head) {
        NodeT *cur = NULL;
        NodeT *new = NULL;
        
        new = malloc(sizeof(NodeT));
        if (new == NULL) {
            fprintf(stderr, "Out of memory\n");
            exit(1);
        }
        
        if (head == NULL) {
            head = new;
        } else {
            cur = head;
            while (cur != NULL) {
                cur = cur->next;
            }
            cur = new;
        }
        
        new->next = NULL;
        
        return head;
    }

    What's going on here? There are only a couple of lines that differ, and to me it seems like they should be doing the same thing.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,667
    Ah, I see the difference. The nodes could be anywhere in memory and the data structure is glued by pointers inside of nodes. There is nothing inside of NULL, so it really isn't a part of the list - it functions as a sentinel value for the end. That is why it makes sense to find the node that points to NULL instead. Not to say that the function that doesn't work, couldn't work. It is just a different type of list that has sentinel nodes.

    When you find a tail-end sentinel node, then you have to remember to insert before it. Voila. It's really easy with doubly linked lists.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Lines 14-18 in your second example are like doing:
    Code:
    int x;
    x = 7;
    while (x < 99)
        x++;
    x = 42;
    All of which has the same effect as:
    Code:
    int x = 42;
    The first example however is very much not doing that.
    Last edited by iMalc; 09-06-2012 at 12:31 AM.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. What are the ways of adding nodes in a linked list
    By kyel_dai92 in forum C Programming
    Replies: 8
    Last Post: 03-22-2011, 03:50 AM
  2. Adding several nodes to a linked list using a loop
    By budala in forum C Programming
    Replies: 3
    Last Post: 09-11-2009, 06:05 AM
  3. adding new nodes to linked list
    By roaan in forum C Programming
    Replies: 8
    Last Post: 07-15-2009, 12:55 PM
  4. Adding nodes into linked list
    By Suchy in forum C++ Programming
    Replies: 1
    Last Post: 04-29-2007, 04:03 PM
  5. Adding nodes to a linked list
    By bluescreen in forum C Programming
    Replies: 4
    Last Post: 11-09-2006, 12:59 AM

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