{"id":3681,"date":"2021-08-07T10:02:52","date_gmt":"2021-08-07T10:02:52","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3681"},"modified":"2022-11-25T09:47:53","modified_gmt":"2022-11-25T09:47:53","slug":"given-a-linked-list-which-is-sorted-how-to-insert-in-a-sorted-way","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/given-a-linked-list-which-is-sorted-how-to-insert-in-a-sorted-way\/","title":{"rendered":"Given a Linked List which is sorted, how to insert in a sorted way"},"content":{"rendered":"

\"\"<\/p>\n

In this article , will learn how to write a program to insert a new node into a sorted linked list without disturbing the order.As we know in linked list is a sequence of data structures that are connected through links and each node contains the address of the next node.Now let\u2019s try to understand to insert a new node into a sorted linked list without disturbing the order. <\/p>\n

How to insert a new node into a sorted linked list without disturbing the order. <\/h2>\n

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.<\/p>\n

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

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.
\nSo, the final list is 1 -> 5 -> 9 -> 11 -> 15 -> 20.<\/p>\n

Input:<\/strong> <\/p>\n

\"\"<\/p>\n

Element to be inserted – 15.<\/p>\n

Output:<\/strong> <\/p>\n

\"\"<\/p>\n

Explanation:<\/strong> 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.<\/p>\n

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.<\/p>\n

Approach to insert a new node into a sorted linked list without disturbing the order. <\/h2>\n

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.<\/p>\n

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. <\/p>\n

In the end, we are going to insert the new node just after the appropriate node.<\/p>\n

Algorithm to insert a new node into a sorted linked list without disturbing the order. <\/h2>\n
    \n
  • Base Case 1 – If the list is empty, then make the new node as head.<\/li>\n
  • Base Case 2 – If the new node value is lesser than the head node, then insert it at the start, make it the head.<\/li>\n
  • 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.<\/li>\n
  • When the loop breaks, insert the new node just after the current node:
    \n1) New_node – > next = current – > next
    \n2) current – > next = New_node<\/li>\n<\/ul>\n

    Dry Run to insert a new node into a sorted linked list without disturbing the order. <\/h3>\n

    \"\"<\/p>\n

    Code Implementation to insert a new node into a sorted linked list without disturbing the order. <\/h2>\n\t\t\t\t\t\t