# 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 <stdio.h>
#include <stdlib.h>

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

struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
>= new_node->data) {
}
else {
while (current->next != NULL
&& current->next->data < new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}

struct Node* newNode(int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(
sizeof(struct Node));

/* put in the data  */
new_node->data = new_data;
new_node->next = NULL;

return new_node;
}

/* Function to print linked list */
{
while (temp != NULL) {
printf("%d  ", temp->data);
temp = temp->next;
}
}

/* Driver program to test count function*/
int main()
{
struct Node* new_node = newNode(5);
new_node = newNode(10);
new_node = newNode(7);
new_node = newNode(3);
new_node = newNode(1);
new_node = newNode(9);

return 0;
}
```
```#include <bits stdc++.h="">
using namespace std;

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

Node* new_node)
{
Node* current;

>= new_node->data) {
}
else {

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;
}

{
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}

int main()
{

Node* new_node = newNode(5);
new_node = newNode(1);
new_node = newNode(11);
new_node = newNode(9);
new_node = newNode(20);
new_node = newNode(15);
return 0;
}
```
```public class LinkedList {

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

void sortedInsert(Node new_node)
{
Node current;

>= new_node.data) {
}
else {

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()
{
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}

public static void main(String args[])
{
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);
llist.printList();
}
}
```
```class Node:

def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def sortedInsert(self, new_node):

else :

while(current.next is not None and
current.next.data < new_node.data):
current = current.next

new_node.next = current.next
current.next = new_node

def printList(self):
while(temp):
print(temp.data, end = " ")
temp = temp.next

new_node = Node(5)
llist.sortedInsert(new_node)
new_node = Node(1)
llist.sortedInsert(new_node)
new_node = Node(11)
llist.sortedInsert(new_node)
new_node = Node(9)
llist.sortedInsert(new_node)
new_node = Node(20)
llist.sortedInsert(new_node)
new_node = Node(15)
llist.sortedInsert(new_node)
llist.printList()

```

#### Output

Created Linked List: 1 5 9 11 15 20

[forminator_quiz id="3682"]

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.