Insert Node in the Sorted Linked List

Insert a new node in the sorted linked list in sorted way

After inserting a node in sorted linked list the final linked list should be the sorted linked list.

Example

Algorithm

a. If linked list is empty linked list, then make the node as head and return it.

b. If value of node to be inserted is smaller than or equal to the head, then insert the node at start and make it head.

c. Traverse the linked list, find the node after which the input node to be inserted.

d. To find the node, keep track of previous and move forward in linked list.

e. If current node is greater than input, then previous is the node to be found.

f. Insert the node after it.

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

void SortedInsertion(struct LLNode** head, struct LLNode* ToBeInserted)
{
    struct LLNode* curr;
    //Base cases
    if (*head == NULL || (*head)->data >= ToBeInserted->data)
    {
        ToBeInserted->next = *head;
        *head = ToBeInserted;
    }
    //Find insertion point and insert the node after it
    else
    {
        curr = *head;
        while (curr->next!=NULL && curr->next->data < ToBeInserted->data)
        {
            curr = curr->next;
        }
        ToBeInserted->next = curr->next;
        curr->next = ToBeInserted;
    }
}
//Main function
int main()
{
    struct LLNode* head = NULL;//Initial list has no elements
    
    insertAtBeginning(&head, 21);
    insertAtBeginning(&head, 17);
    insertAtBeginning(&head, 15);
    insertAtBeginning(&head, 11);
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 2);           
    
    cout<<"Input linked list is: ";
    display(&head);
    
    struct LLNode* head1 = NULL;//Initial list has no elements
    insertAtBeginning(&head1, 8);
    cout<<"Node to be inserted: ";
    display(&head1);
    //insering
    SortedInsertion(&head, head1);
    
    cout<<"\nOutput linked list: ";
    display(&head);

    return 0;
}
Try It

 


< Prev
Scroll to Top