Thread: 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.

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.