Back to: Data Structures and Algorithms Tutorials

**Inserting in a Sorted Linked List:**

In this article, I am going to discuss **Inserting in a Sorted Linked List** using C Language with Examples. Please read our previous article, where we discussed **Creating a Linked list using Insert** using C Language with Examples.

**Inserting in a Sorted Linked List:**

Here, we will see how to insert a new node in a sorted linked list at a sorted position.

This is a sorted linked list. All these keys or elements are sorted. Suppose we want to insert a new element that is â€˜11â€™ then where should come this? â€˜11â€™ should come after â€˜7â€™ or before â€˜12â€™. If we want to insert â€˜4â€™ then where should we insert it? Between â€˜3â€™ and â€˜5â€™. Let us see how to do this. What should be the procedure? So let us take an example of â€˜6â€™ and try to insert it into this sorted list.

**Steps for Insertion in a Sorted Linked List:**

The first thing we will try to find out the position where this â€˜6â€™ should be inserted. For that, we will take the help of a pointer. Letâ€™s take a pointer â€˜pâ€™ on the first node and start finding the position for this particular element.

We will check for if (p->data < key), if yes then move â€˜pâ€™ to the next node. Here 2 is less than 6, so move â€˜pâ€™ to the next node.

Here we will check again for if (p->data < key). Now â€˜3â€™ is less than â€˜6â€™ so move pointer â€˜pâ€™ to the next node.

â€˜5â€™ is also smaller than â€˜6â€™ again move â€˜pâ€™ to the next node.

Now here â€˜7â€™ is not less than â€˜6â€™ so we have to insert â€˜6â€™ before â€˜7â€™. So, for that, we want a pointer on the previous node also i.e. â€˜5â€™. So, we have to create a tailing pointer let’s say â€˜qâ€™ and we have to move â€˜pâ€™ and â€˜qâ€™ at the same time.

Initially, â€˜qâ€™ will point to null and â€˜pâ€™ will point to the first node. So â€˜qâ€™ will point to one node previous to the â€˜pâ€™ node. We will move both the pointer until pâ€™s data will greater than the key value.

It can be done with a single pointer also but we are doing it with 2 pointers that are â€˜qâ€™ and â€˜pâ€™. Following are the step to insert a new node:

- Create a new node i.e. â€˜tâ€™ and store the data.
- â€˜tâ€™ next should point on â€˜qâ€™ next.
- â€˜qâ€™ next should point on â€˜tâ€™.

Now let us write a full program to insert a node at a sorted position.

**Program for inserting a node at a sorted position:**

#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; } *first = NULL, *second = NULL; void Display(struct Node *p) { while (p != NULL) { printf ("%d ", p->data); p = p->next; } } void Create(int A[], int n) { int i; struct Node *t, *last; first = (struct Node *) malloc(sizeof (struct Node)); first->data = A[0]; first->next = NULL; last = first; for (i = 1; i < n; i++) { t = (struct Node *) malloc(sizeof (struct Node)); t->data = A[i]; t->next = NULL; last->next = t; last = t; } } void SortedInsert(struct Node *p, int x) { struct Node *t, *q = NULL; t = (struct Node *) malloc (sizeof (struct Node)); t->data = x; t->next = NULL; if (first == NULL) first = t; else { while(p && p->data < x) { q = p; p = p->next; } if(p == first) { t->next = first; first = t; } else { t->next = q->next; q->next = t; } } } int main() { int A[] = { 2, 3, 5, 7, 12 }; Create (A, 5); SortedInsert (first, 6); Display (first); return 0; }

**Output:**

In the next article, I am going to discuss **Deleting from Linked List in C** Language with Examples. Here, in this article, I try to explain **Inserting in a Sorted Linked List** using C Language with Examples and I hope you enjoy this Inserting in a Sorted Linked List using C Language with Examples article.

**About the Author: Pranaya Rout**

Pranaya Rout has published more than 3,000 articles in his 11-year career. Pranaya Rout has very good experience with Microsoft Technologies, Including C#, VB, ASP.NET MVC, ASP.NET Web API, EF, EF Core, ADO.NET, LINQ, SQL Server, MYSQL, Oracle, ASP.NET Core, Cloud Computing, Microservices, Design Patterns and still learning new technologies.