Given a Linked List which is sorted, how to insert in a sorted way

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list. We are also given an element that is to be inserted into the list. But, the given list is sorted. So, the insertion should be done in such a way that the sorted order of the linked list is not disturbed.

Problem Statement Understanding

Suppose the given linked list is 1 -> 5 -> 9 -> 11 -> 20, and the element to be inserted is 15.

So, according to the problem, 15 should be inserted between 11 and 20, as we also have to maintain the sorted order of the list.
So, the final list is 1 -> 5 -> 9 -> 11 -> 15 -> 20.

Input:

Element to be inserted - 15.

Output:

Explanation: As the given list is sorted in ascending order, we have inserted 15 in an appropriate position, which maintains the sorted order of the list.

As we know, insertion and deletion in a singly linked list are very efficient, but list traversal takes O(n) time. We are going to use the list traversal, but with a few tweaks. Let us have a glance at the approach.

Approach

The approach is going to be pretty simple. We know the given linked list is already sorted. So, to insert a new element in a sorted way, we have to find an appropriate position for the new element, such that the order is not disturbed.

We are going to traverse through the list and look for the appropriate position to insert the element. To find the position, we are going to run the loop till will find a node, say, temp, whose value is greater than the new node. The node just before temp is the appropriate node.

In the end, we are going to insert the new node just after the appropriate node.

Algorithm

  • Base Case 1 - If the list is empty, then make the new node as head.
  • Base Case 2 - If the new node value is lesser than the head node, then insert it at the start, make it the head.
  • Traverse through the list until the data of the next of current is less than the data of the new node. By doing this, we are looking for an appropriate position to insert the new node.
  • When the loop breaks, insert the new node just after the current node:
    1) New_node - > next = current - > next
    2) current - > next = New_node

Dry Run

Code Implementation


#include 
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void sortedInsert(Node** head_ref,
                  Node* new_node)
{
    Node* current;

    if (*head_ref == NULL
        || (*head_ref)->data
               >= new_node->data) {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else {
     
        current = *head_ref;
        while (current->next != NULL
&& current->next->data
< new_node->data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

Node* newNode(int new_data)
{

    Node* new_node = new Node();

    new_node->data = new_data;
    new_node->next = NULL;
 
    return new_node;
}

void printList(Node* head)
{
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

int main()
{
   
    Node* head = NULL;
    Node* new_node = newNode(5);
    sortedInsert(&head, new_node);
    new_node = newNode(1);
    sortedInsert(&head, new_node);
    new_node = newNode(11);
    sortedInsert(&head, new_node);
    new_node = newNode(9);
    sortedInsert(&head, new_node);
    new_node = newNode(20);
    sortedInsert(&head, new_node);
    new_node = newNode(15);
    sortedInsert(&head, new_node);
    cout << "Created Linked List\n";
    printList(head);
    return 0;
}


public class LinkedList {
    Node head; 


    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    void sortedInsert(Node new_node)
    {
        Node current;

        if (head == null || head.data
>= new_node.data) {
            new_node.next = head;
            head = new_node;
        }
        else {

            current = head;

            while (current.next != null
&& current.next.data < new_node.data)
                current = current.next;

            new_node.next = current.next;
            current.next = new_node;
        }
    }

    Node newNode(int data)
    {
        Node x = new Node(data);
        return x;
    }

    void printList()
    {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    public static void main(String args[])
    {
        LinkedList llist = new LinkedList();
        Node new_node;
        new_node = llist.newNode(5);
        llist.sortedInsert(new_node);
        new_node = llist.newNode(9);
        llist.sortedInsert(new_node);
        new_node = llist.newNode(11);
        llist.sortedInsert(new_node);
        new_node = llist.newNode(1);
        llist.sortedInsert(new_node);
        new_node = llist.newNode(20);
        llist.sortedInsert(new_node);
        new_node = llist.newNode(15);
        llist.sortedInsert(new_node);
        System.out.println("Created Linked List");
        llist.printList();
    }
}

Output

Created Linked List: 1 5 9 11 15 20

Space Complexity: O(1), as only temporary variables are being created.

So, in this article, we have tried to explain the most efficient approach to insert an element in a sorted way, in a sorted linked list. This is an important question when it comes to coding interviews, as there are many applications of sorted insertion in linked list problems.If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Construct a Complete Binary Tree from its Linked List Representation
Next post Student Record Management System Using Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *