Program is not printing what i need to print

Question

I want to create a sorted linked list, so everytime we insert an element, it's should be sorted (in ascending order). Now I have made a sorted linked list. The program is working fine, but there's an issue. It's not printing the middle and last inserted element in the sorted linked list, even though it's inserted.

My code is

 //Libraries
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>


struct Node{

    int val;
    struct Node  *next;
};

struct LLADT{

    struct Node *head;
};


// Initializing Linked List
void init(struct LLADT *LL){
    LL->head = 0;
}

// Sorted Inserted Linked List Function
void sortInsert(struct LLADT *LL, int num){
    struct Node *temp;
    struct Node *temp2;
    temp = (struct Node*)malloc(sizeof(struct Node));



// If list is Empty
    if(LL->head == 0){
        temp-> val = num;
        temp->next = NULL;
        LL->head = temp;
        return;
    }

// When list is not empty and key is smallest

    if(num < LL->head->val){
        temp-> val = num;
        temp->next = LL->head;
        LL->head = temp;
        return;

    }
// When list is not empty and we have to insert in middle
    temp2 = LL->head;
    temp-> val = num;
    temp->next = NULL;
    while(temp2->next !=0){
        if(num > temp2->next->val){
            temp2 = temp2->next;
        }
        else{

            temp2->next = temp->next;
            temp->next = temp2;
            return;
        }

    }


// When list is not empty and we have to insert at the end
    if(num > temp->val){

        temp->val = num;
        temp->next = NULL;
        temp2->next = temp;
        return;


    }
}

//Printing Linked List
void print_list(struct LLADT *LL){
    struct Node *temp;
    temp = LL-> head;
    while(temp !=0){
        printf("%d\n", temp->val);
        temp = temp -> next;
    }
}

// Main Function
int main(){

    struct LLADT LL;
    init(&LL);

    // inserting
    sortInsert(&LL,17);
    sortInsert(&LL,3);
    sortInsert(&LL,5);
    sortInsert(&LL,2);
    sortInsert(&LL,1);
    sortInsert(&LL,20);

    //Printing
    print_list(&LL);
    getch();
    return 0;
}

Output of this program is:

1
2
3

And I am using Visual Studio 2012 Ultimate.

Answer 1

This is a simplified version. It checks if the new node belongs at the head of the list as a special case at the beginning. The it loops through the list until either the correct position or the end of the list is found.

// Sorted Inserted Linked List Function
void sortInsert(struct LLADT *LL, int num)
{
    struct Node *newNode;
    struct Node *currentNode;
    struct Node *previousNode;

    // Initialise a new node for the new value.
    newNode = malloc(sizeof(struct Node));
    newNode->val = num;

    // If list is Empty or the new node is first in the list.
    if((NULL == LL->head) || (num < LL->head->val))
    {
        newNode->next = LL->head;
        LL->head = newNode;
        return;
    }

    // Iterate until last element or found position
    currentNode = LL->head;
    while((NULL != currentNode)&&(num >= currentNode->val))
    {
        // Move on to the next element
        previousNode = currentNode;
        currentNode = currentNode->next;
    }

    // Insert the new element between the previous and current
    previousNode->next = newNode;
    newNode->next = currentNode;
}

Answer 2

Your logic when inserting the middle of the list is faulty:

temp2->next = temp->next;
temp->next = temp2;

At this point, you want to insert the new node temp right after temp2. But instead, you have temp2 followed by the initial value of temp->next, which is NULL, then you have temp followed by temp2 (the opposite of what you want.

So you have this:

           ----------------
temp -->   | num  |  NULL |
           ----------------

           ----------------     ----------------
temp2 -->  | v1   |   . --|---> | v2   |   . --|--> ...
           ----------------     ----------------

And you want this:

                                temp --|
                                       v
           ----------------     ----------------    ----------------
temp2 -->  | v1   |   . --|---> | num   |   . --|--> | v2   |   . --|--> ...
           ----------------     ----------------    ----------------

So you do it like this:

temp->next = temp2->next;
temp2->next = temp;

On a side note, always use NULL instead of 0 when assigning or checking a NULL pointer. In most cases they're the same, but the standard doesn't say that they have to be.