Question

How to build sorted linear (singly) linked list and insert new items in sorted order with C

Answer 1

// A c program that insert an items into a linked list in a sorted order

#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
    int n;
    struct Node* next;
};
 
void insert_sorted(struct Node** head, struct Node* new_node)
{
    struct Node* current;
    
    if (*head == NULL || (*head)->n >= new_node->n)
    {
        new_node->next = *head;
        *head = new_node;
    }
    else
    {
        current = *head;
        while (current->next != NULL && current->next->n < new_node->n)
            current = current->next;
        
        new_node->next = current->next;
        current->next = new_node;
    }
}
 
struct Node *create_node(int n)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
 
    new_node->n  = n;
    new_node->next =  NULL;
 
    return new_node;
}
 
void print_linked_list(struct Node *head)
{
    struct Node *tmp = head;
    
    while(tmp != NULL)
    {
        printf("%3d", tmp->n);
        tmp = tmp->next;
    }
}

void free_linked_list(struct Node *head)
{
    struct Node *current = head;
     
    while (current) 
    {
        current = current->next;
        free(head);
        head = current;
    }
}
 
int main(void)
{
    struct Node* head = NULL;
    struct Node *new_node = create_node(13);
    
    insert_sorted(&head, new_node);
    new_node = create_node(2);
    
    insert_sorted(&head, new_node);
    new_node = create_node(9);
    
    insert_sorted(&head, new_node);
    new_node = create_node(7);
    
    insert_sorted(&head, new_node);
    new_node = create_node(5);
    
    insert_sorted(&head, new_node);
    new_node = create_node(4);
    
    insert_sorted(&head, new_node);
    new_node = create_node(3);
    
    insert_sorted(&head, new_node);
    
    print_linked_list(head);
    
    free_linked_list(head);
 
    return 0;
}

  
/*
run:
  
  2  3  4  5  7  9 13

*/

 

70+ SQL courses for beginners and professionals