C Sorted Linked List

Sorted Linked List

Sorted Linked list stores the element in the linked list as sorted order (ascending order).

Linked list are not stored in adjacent locations and array occupy continuous locations.

C Program to Implement Sorted Linked List and Operations

#include<stdio.h>  

//structure contains data and link
struct node
{
    int data;
    struct node *link;
};

// adding element in the linked list as sorted order
int add(struct node **head, int data)
{
    struct node *temp, *tail;
    temp = *head;
    tail = malloc( sizeof (struct node));                                   
    tail->data = data;  
    tail->link = NULL;
    // if linked list is empty, adding as first node.
    if(*head == NULL || (*head)->data > data)
    {
        *head = tail;
        (*head)->link = temp;
        return 1;
    }
    // search the position and adding the element
    else
    {
        //Move to last node
        while(temp != NULL)
        {
            if(temp->data <= data && (temp->link->data > data || temp->link == NULL))
            {
                tail->link = temp->link;
                temp->link = tail;
                return 1;
            }
            // move to the next node
            temp = temp->link;
        }
    }
    return 0; 
}

// displays the sorted linked list
void display(struct node *head)
{
    printf("\n");
    // traversing entire linked list
    printf("\nhead==>");
    while(head != NULL)
    {
        printf("%d-->", head->data);
        head = head->link;
    }
    printf("tail");
}

// finds the number of elements in the sorted linked list
int count(struct node *head)
{
    int c = 0;
    while(head != NULL)                                                         
    {                                                                           
        head = head->link;          
        c++;
    } 
    return c;
}

// Deletes the any element in the sorted linked list
int delete(struct node **head, int data)
{
    struct node *old, *temp;
    temp = *head;

    while(temp != NULL)
    {
        if(temp->data == data)
        {
            // deleting first node if data matches
            if(temp == *head)
            {
                *head = temp->link;
                free(temp);
                return 1;
            }
            // deleting other nodes except first node
            else
            {
                old->link = temp->link;
                free(temp);
                return 1;
            }
        }
        // old points to the previous node
        old = temp;
        temp = temp->link;
    }
    return 0;
}


void main()                                                                     
{       
    int op, data, loc;                                                                        
    struct node *ptr;                                                           
    // Empty linked list                                                        
    ptr = NULL;                                                                 
                                                                                
    printf("\nNumber of elements in the linked list: %d", count(ptr));          
    add(&ptr, 3);                                                            
    add(&ptr, 2);                                                            
    add(&ptr, 1);                                                            
                                                                                
    display(ptr);       
    printf("\nNumber of elements in the linked list: %d", count(ptr));

    do
    {
        printf("\nLinked List\n---------------\n1.Add element\n2.delete\n3.display\n4.count\n0.exit");
        printf("\nEnter choice: ");
        scanf("%d", &op);
        switch(op)
        {
            case 1:
                printf("\nEnter element: ");                                    
                scanf("%d", &data);                                             
                add(&ptr, data);  
                break;
            case 2:
                printf("\nEnter element: ");                                    
                scanf("%d", &data);                                             
                delete(&ptr, data);  
                break;
            case 3:
                display(ptr);
                break;
            case 4:
                printf("\nNumber of elements in the linked list: %d", count(ptr));
                break;
        }
    }while(op>=1 && op<=4);
}     
                                                                                                                                                                                                                                                                                                                                                                                                           

$ cc sorted-linked-list.c 
sorted-linked-list.c: In function ‘add’:
sorted-linked-list.c:14:12: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration]
     tail = malloc( sizeof (struct node));
            ^~~~~~
sorted-linked-list.c:14:12: warning: incompatible implicit declaration of built-in function ‘malloc’
sorted-linked-list.c:14:12: note: include ‘’ or provide a declaration of ‘malloc’
sorted-linked-list.c: In function ‘delete’:
sorted-linked-list.c:80:17: warning: implicit declaration of function ‘free’ [-Wimplicit-function-declaration]
                 free(temp);
                 ^~~~
sorted-linked-list.c:80:17: warning: incompatible implicit declaration of built-in function ‘free’
sorted-linked-list.c:80:17: note: include ‘’ or provide a declaration of ‘free’
sorted-linked-list.c:87:17: warning: incompatible implicit declaration of built-in function ‘free’
                 free(temp);
                 ^~~~
sorted-linked-list.c:87:17: note: include ‘’ or provide a declaration of ‘free’

$ ./a.out 

Number of elements in the linked list: 0

head==>1-->2-->3-->tail
Number of elements in the linked list: 3
Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 3


head==>1-->2-->3-->tail
Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 1

Enter element: 1

Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 3


head==>1-->1-->2-->3-->tail
Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 2

Enter element: 1

Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 3       


head==>1-->2-->3-->tail
Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 1

Enter element: 1

Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 3


head==>1-->1-->2-->3-->tail
Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 4

Number of elements in the linked list: 4
Linked List
---------------
1.Add element
2.delete
3.display
4.count
0.exit
Enter choice: 0