Search code examples
cinsertlinked-listbinary-tree

C linked list inserting node at the end


I'm having some trouble with my insertion method for a linked list in C. It seems to only add at the beginning of the list. Any other insertion I make fail. And this CodeBlocks debugger is so hard to understand I still don't get it. It never gives me value, just addresses in memory. Anyway this is my function. Do you see any reason why it's failing?

/* function to add a new node at the end of the list */
int addNodeBottom(int val, node *head){

    //create new node
    node *newNode = (node*)malloc(sizeof(node));

    if(newNode == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }

    newNode->value = val;

    //check for first insertion
    if(head->next == NULL){
        head->next = newNode;
        printf("added at beginning\n");
    }

    else
    {
        //else loop through the list and find the last
        //node, insert next to it
        node *current = head;
        while(current->next != NULL)
        {
            if(current->next == NULL)
            {
                current->next = newNode;
                printf("added later\n");
            }
            current = current->next;
        }
    }
    return 0;
}

Then in main, only 929 is added.

   //testing addNodeBottom function
    addNodeBottom(929, head);
    addNodeBottom(98, head);
    addNodeBottom(122, head);
    addNodeBottom(11, head);
    addNodeBottom(1034, head);

Solution

  • This code will work. The answer from samplebias is almost correct, but you need a third change:

    int addNodeBottom(int val, node *head){
    
        //create new node
        node *newNode = (node*)malloc(sizeof(node));
    
        if(newNode == NULL){
            fprintf(stderr, "Unable to allocate memory for new node\n");
            exit(-1);
        }
    
        newNode->value = val;
        newNode->next = NULL;  // Change 1
    
        //check for first insertion
        if(head->next == NULL){
            head->next = newNode;
            printf("added at beginning\n");
        }
    
        else
        {
            //else loop through the list and find the last
            //node, insert next to it
            node *current = head;
            while (true) { // Change 2
                if(current->next == NULL)
                {
                    current->next = newNode;
                    printf("added later\n");
                    break; // Change 3
                }
                current = current->next;
            };
        }
        return 0;
    }
    

    Change 1: newNode->next must be set to NULL so we don't insert invalid pointers at the end of the list.

    Change 2/3: The loop is changed to an endless loop that will be jumped out with break; when we found the last element. Note how while(current->next != NULL) contradicted if(current->next == NULL) before.

    EDIT: Regarding the while loop, this way it is much better:

      node *current = head;
      while (current->next != NULL) {
        current = current->next;
      }
      current->next = newNode;
      printf("added later\n");