To insert the elements in a singly linked list in ascending order.

Question

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

typedef struct node
{
    int data;
    struct node *link;
}list;

list *header =NULL;

void insert(int num)
{
    printf("num:%d ", num);
    struct node *temp, *r;
    temp = header;

    r = malloc(sizeof(struct node));
    r -> data = num;

    if(temp == NULL ||temp-> data > num )
    {
        r-> link = temp ;
        header = r;
    }
    else 
    {
        while(temp !=NULL)
        {
            if(temp -> data <= num && (temp->link->data > num));
            {
                r -> link = temp -> link;
                temp->link=r;
                return;
            }
            temp = temp -> link;
        }           
    }
}

void display()
{
    struct node *temp;
    temp = header;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->link;
    }
}

void main( )
{
    insert(10);
    insert(5);
    insert(17);
    insert(8);
    insert(23);
    insert(78);

    display();
}

Here I am trying to insert the elements in a ascending order. To my surprise, the ouput I got is 5 78 23 8 17 10, which is incorrect, could anyone please have a look on this? Any help would be appreciated..

Answer 1

In order to insert nodes in ascending order in a linked list, you'll have to address following scenarios -
1. List is empty: When there are no elements in the list
2. Insert at begin: When r->data < header->data, it needs to be inserted at the very beginning of the list.
3. Insert at end: When r->data is greater than the node with largest value in the list, it needs to be inserted at the very end (assuming we're doing sorted insert here), as user @keltar has already pointed out.
4. Insert in the middle: When r->data > header->data but smaller than the largest element in the list, it needs to be inserted somewhere in between header and last node.

Simple implementation of sorted insert is as below -

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

#define LEN 13

struct node {
    int data;
    struct node *next;
};
/*
 * print_list() - To print the state of the list
 */
void print_list(struct node *head)
{
    struct node *tmp = head;
    while (tmp) {
        printf(" %d ", tmp->data);
        tmp = tmp->next;
    }
    printf("\n\n");
}
/*
 * insert_node_sorted() - To insert nodes into the list
 * in sorted order
 */
struct node *insert_node_sorted(struct node *head, int data)
{
    struct node *tmp;
    struct node *e_ptr;
    struct node *new_node = malloc(sizeof(struct node));
    if (!new_node)
        exit(0);
    new_node->data = data;
    new_node->next = NULL;
    /* When the list is empty */
    if (!head)
        return new_node;
    else {
        /* Initialize tmp & e_ptr */
        tmp = head;
        e_ptr = head;
        /* Make e_ptr point to the largest element of the list, i.e. last element */
        while (e_ptr->next)
            e_ptr = e_ptr->next;
        /* If the element to be inserted is smaller than the head node */
        if (head->data > new_node->data) {
            new_node->next = head;
            head = new_node;
        } else if (new_node->data > e_ptr->data){ /* Data to be inserted is larger than the largest element in the list */
            e_ptr->next = new_node;
        } else { /* New node should be placed somewhere in between head and e_ptr */
            while (tmp->next && tmp->next->data < new_node->data) 
                tmp = tmp->next;
            new_node->next = tmp->next;
            tmp->next = new_node;
        }
    }
    return head;
}
/*
 * Driver function
 */
int main(int argc, char **argv)
{
    struct node *head = NULL;
    int i;
    /* Populate the list */
    for (i = 0; i < LEN; i++)
        head = insert_node_sorted(head, rand() % 1000);
    /* Print the state of the list */
    printf("State of the list -\n\n");
    print_list(head);
    return 0;
}