inserting a node in the middle of a linked list failed

Question

I'm trying to implement an insertion function to insert nodes in a linked list.(using the code written in study 50) the program appends and prepend nodes successfully but when it comes to inserting a node in the middle, it goes wrong.the program doesn't insert them at all. i am sure that the mistake is in my insertion sort.thats my code.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

typedef struct node
{
    // the value to store in this node
    int n;

    // the link to the next node in the list
    struct node* next;
} node;

node* head = NULL;
node* last = NULL;
void insert_sorted(int i)
{
    node* new_node = malloc(sizeof(node));
    new_node->n = i;
    new_node->next = NULL;

    //if it's the first element,make the head and the last pointer point to it
    if( head == NULL)
    {
        head = new_node;
        last = new_node;
        return;
    }
    //if it's  the smallest element in the list.prepend to head;
    if(head->n >= i)
    {
        new_node->next = head;
        head = new_node;
        return;
    }
    // if it's the largest element,append
    else if(last->n <= i)
    {
        last->next = new_node;
        last = new_node;
        return;
    }
    // inserting an node in the middle by keeping track of each two adjacent elements;
    node* ptr2;
    for(node* ptr = head; ptr != NULL; ptr = ptr->next)
    {
        ptr2 = ptr->next;
        if( ptr->n <=i && ptr2->n >= i )
        {
            new_node->next = ptr2;
            ptr2 = new_node;
            return;
        }
    }
}

int main(int argc, char* argv[])
{
    int n;
    printf("Inserting %i random ints to the list...\n", SIZE);
    for (int i = 0; i < SIZE; i++)
    {
        n = rand() % SIZE;
        insert_sorted(n);
    }
    printf("done!\n");

    // printing out list
    printf("Your list now contains ");
    for (node*  ptr = head; ptr != NULL; ptr = ptr->next)
    {
        printf("%i ", ptr->n);
    }
    printf("\n");

    return 0;
}

Answer 1

although this could have been accomplished in a much more elegant way, I think the problem is in this part

if( ptr->n <=i && ptr2->n >= i )
{
    new_node->next = ptr2;
    ptr2 = new_node;
    return;
}

so here you're trying to insert new_node between ptr and ptr2. what you're doing is setting new_node->next to ptr2 which is correct, then setting ptr2 to new_node which doesn't really have any use. let's see why!

as you know, ptr->next stores an address, let's call x.

1. you created a pointer, namely ptr2 and set it to store the same address x.
2. then you set new_node->next to store x as well.
3. and lastly you set ptr2 to store another address y (which is presumably the address of new_node) assuming that this changes what's stored in ptr->next, but does it?

Answer 2

First of all let's clear something. head and last should be just pointers to nodes, not nodes themselves. So your linked list should look like that:

[head]
   |
   v
[value1, link1]
           |
           v
        [value2, link2]
                   |
                   v
                [valuen, linkn] <- [tail]

If you want to add to the beginning of the list

1. Create a new node (let's call it node k).
2. Give a value to value k.
3. Make link k point to head.
4. Make head point to node k.

If you want to add to the end of the list

1. Create a new node (let's call it node k).
2. Give a value to value k.
3. Make tail's link point to node k.
4. Make tail point to node k.

If you want to add somewhere in the middle of the list

1. Make a node* tmp.
2. Start from tmp = head and while tmp -> link -> n > i make tmp = tmp -> link
3. When above is no longer true, make link k point to ptr -> link.
4. Make ptr -> link point to node k.

Sidenote

If head points to node1, then head->link is the same as link1.

---

I know this may confuse you a little, but it's the best pseudocode I can give you without solving it for you. If you need more help understanding something ask in the comments and I'll try to elaborate.

---

If this answers your question please accept it by clicking the gray check-mark to the left, so that it becomes green. You can also vote it up by pressing the up arrow above the check-mark. And don't forget to keep coding!