c - Adding new item to a list

Question

This function get a pointer to the "Dummy" item of the list (1st item) and a struct typed "Node" to add...

But it goes into an infinite loop... whats wrong???

void listAdd(Node* dummy, Node tmpNode) {

    Node* toAdd = (Node*)malloc(sizeof(Node));
    *toAdd = tmpNode;
    Node *tmp1,*tmp2;
    tmp1 = dummy;
    tmp2 = (*dummy).next;

    while (tmp1 != NULL){

            if ( ((*tmp1).info.id < (*toAdd).info.id && (*tmp2).info.id > (*toAdd).info.id ) || (tmp2==NULL) ) {
                    (*toAdd).next = (*tmp1).next;
                    (*tmp1).next = toAdd;
                    return;
            }

            tmp1 = (*tmp1).next;
            tmp2 = (*tmp2).next;   
    }
}

Why are you iterating through the entire list to add `tmpNode` to the list? Typically, when you have a linked list and you want to add a node to it, you add it at the front. It's more efficient that way. By the way, `dummy` isn't a great name. Something like `head` would be better. — Eric Jablow, Jun 04 '13 at 12:29
Thenx for your answer. i m adding the node to his place by its ID field - it need to be sorted that way. — user2451694, Jun 04 '13 at 12:39
Are you only using `listAdd` to add elements to the list? And if so, how you do create the initial empty list? — Bryan Olivier, Jun 04 '13 at 12:54
I am. the empty list is created with this function: http://pastebin.com/xGUCV9Bs — user2451694, Jun 04 '13 at 13:04
I've reconstructed your code adding a 1000 random elements with an id between 0 and 9 (inclusive) and it never hangs. I did move the test on `tmp2 == NULL` to the front of the `if`, otherwise you should run into a segmentation fault. I also changed the first `<` to `<=` to support adding an `id` already in the list. My conclusion is (still) that the problem is likely to be in some other code. I'd advise to use the debugger and see how it exactly loops infinitely. — Bryan Olivier, Jun 04 '13 at 13:27
[Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). — unwind, Jun 04 '13 at 14:47
See related question http://stackoverflow.com/questions/12674616/c-adding-node-to-head-of-linked-list or tutorial like http://datastructures.itgo.com/lists/dynamic/addel.htm — Mihai8, Jun 05 '13 at 01:35

score 2 · Answer 1 · edited May 23 '17 at 11:43

EDIT: I got a bit carried away with this (it's a slow day at work) so I rewrote the function to use (IMHO) clearer variable names, fewer redundant variables, and added basic error handling. The example below supports insertion whereas the previous example assumed simple appending to the end of a list which was the result of not reading the question properly (see edits if you're curious).

void listAdd(Node* currentNode, Node toAdd)
{
    Node * newNode = malloc(sizeof(Node));
    if(!newNode){
        //ERROR HANDLING
    }
    * newNode = toAdd;
    newNode->next = NULL;
    while (currentNode)
    {
        if(!currentNode->next) 
        //We've got to the end of the list without finding a place to insert the node.
        //NULL pointer always evaluates to false in C regardless of the underlying value.
        {
            currentNode->next = newNode;
            return;
        }
        //Test each member of the list to find out whether to insert or skip.
        if((newNode->info.id > currentNode->info.id) && (newNode->info.id <= currentNode->next->info.id) ){
            newNode->next = currentNode->next;
            currentNode->next = newNode; 
            return;
        }
        else currentNode = currentNode->next;
    }
}

As has been mentioned in previous posts. dereferencing a pointer to a struct member uses the rather pretty -> notation which has a rather good imagery to it. Note also, that NULL will always evaluate as false, and that unless you want some bad things to happen (at best a segfault, at worst some takes over your machine) you need to make sure you're writing into proper memory areas, so you must always check that malloc returns !NULL.

note: In C, never cast the return value of a malloc() call as this can mask strange and dangerous behaviours. In C++, you must cast the result, so you need to think about who you're going to offend if you expect your program to compile as valid C and C++. See Do I cast the result of malloc? for details.

Better move the test on `tmp2 == NULL` to the start of the `if` and make it a separate case with your fix. If the element is inserted in the middle, then his assignment to `toAdd->next` is correct. I'm actually not sure of your fix. Note that `tmp2 == tmp1->next`. — Bryan Olivier, Jun 04 '13 at 12:50
@BryanOlivier good point. I wasn't thinking of adding in the middle of the list, only the end. Will fix that now. — , Jun 04 '13 at 12:52
thenx for your answer - but the code suppose to add the item in the middel of the list, so the "next" field of "toAdd" suppose to be the "next" field of the item below him. Let me know if my comment is not clear enough. — user2451694, Jun 04 '13 at 13:03

c - Adding new item to a list

1 Answers1