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.



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
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
        //O(1) constant time
//display linked list
void display(struct LLNode**node)
    struct LLNode *temp= *node;
            temp=temp->next; //move to next node
        //O(number of nodes)

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
        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: ";
    struct LLNode* head1 = NULL;//Initial list has no elements
    insertAtBeginning(&head1, 8);
    cout<<"Node to be inserted: ";
    SortedInsertion(&head, head1);
    cout<<"\nOutput linked list: ";

    return 0;


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions