C++ program for insertion in a Sorted Linked List
How to insert data in a sorted linked list?
In the following article, we will learn to write a C++ program for insertion in a sorted linked list with a condition that list input by user is already sorted. If the list is unsorted then first we need to sort the linked list and later we can perform the steps and algorithm mentioned below. Insertion in a linked can simple be perform in 3 different manners -:
- Insertion at Beginning
- Insertion at end
- Insertion at nth position
This article is almost similar as to insertion at nth position, we will be using the same logic the only main difference is that we will be working on a sorted linked list, so the position of the element will be decided after comparing it with all the smaller elements of the linked list.
Steps to write a C++ program for insertion in a sorted linked list
To insert a node in a sorted linked list in C++ following steps are followed
- Define the linked list.
- In the main method call all the method you have declared with input/output statement you want to use.
- Function named build is used to build the linked list.
- Print will be used to display the list.
- newNode will construct new node for insertion.
- Now in our function named sortedInsert core process of the program take place.
- First if the list is empty or data at previous head is greater then the data we are inserting, we will insert new node as head in the list.
- Else we will traverse through the linked list and insert new node at the required position.
How to construct a linked list ?
class Node
{
int data;
Node *next;
};
Algorithm for insertion in a sorted linked list in C++
- IF (*HEAD==NULL || (*HEAD)->DATA>=NEWNODE->DATA
- NEWNODE->NEXT=*HEAD
- *HEAD=NEWNODE
- RETURN AND END IF
- WHILE(CURRENT->NEXT!=NULL && CURRENT->NEXT->DATADATA)
- CURRENT=CURRENT->NEXT
- NEWNODE->NEXT=CURRENT->NEXT
- CURRENT->NEXT=NEWNODE
Program for insertion in a sorted linked list in C++
Run
#include<iostream>
using namespace std;
struct node
{
int data;
struct node *next;
};
void build (struct node **head, int data);
void display (struct node *head);
void sortedInsert (struct node **head, struct node *newNode);
struct node *newNode (int data);
int main (void) //main method.
{
int n, k;
cout << "Enter size of linked list\n"; cin >> n;
int data[100];
cout << "Enter linked list data in sorted order\n";
struct node *head = NULL;
cout << "Linked list before insertion\nLinked List Data: ";
display (head);
for (int i = 0; i < n; i++)
{
cout << "\nEnter data you want to insert: "; cin >> k;
sortedInsert (&head, newNode (k));
}
cout << "\nLinked list after insertion\nLinked List Data: "; display (head); return 0; } void build (struct node **head, int data) //function to build linked list { struct node *newNode = (struct node *) malloc (sizeof (struct node)); newNode->data = data;
newNode->next = *head;
*head = newNode;
}
void display (struct node *head) //function to print linked list
{
struct node *ptr = head;
while (ptr)
{
cout << ptr->data << " "; ptr = ptr->next;
}
}
struct node *newNode (int data)
{
struct node *newNode = (struct node *) malloc (sizeof (struct node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void sortedInsert (struct node **head, struct node *newNode)
//function to insert data in sorted position
{
//If linked list is empty
if (*head == NULL || (*head)->data >= newNode->data)
{
newNode->next = *head;
*head = newNode;
return;
}
//Locate the node before insertion
struct node *current = *head;
while (current->next != NULL && current->next->data < newNode->data)
current = current->next;
newNode->next = current->next;
current->next = newNode;
}
Output
Enter size of linked list
4
Enter linked list data in sorted order
1
2
4
5
Linked list before insertion
Linked List Data: 1 2 4 5
Enter data you want to insert: 3
Linked list after insertion
Linked List Data: 1 2 3 4 5
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Singly Linked List
- Introduction to Linked List in Data Structure
Click Here - Linked List in –
- Singly Linked List in –
- Insertion in singly Linked List –
- Insertion at beginning in singly Linked List –
- Insertion at nth position in singly Linked List –
- Insertion at end in singly Linked List –
- Deletion in singly Linked List –
- Deletion from beginning in singly linked list :
- Deletion from nth position in singly linked list :
- Deletion from end in singly linked list :
- Linked List Insertion and Deletion –
C | C++ | Java - Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++ | Java - Reverse a linked list by changing links between nodes –
- Print reverse of a linked list without actually reversing –
- Print reverse of a linked list without actually reversing –
- Insertion in the middle Singly Linked List –
- Insertion in a Sorted Linked List –
- Delete alternate nodes of a Linked List –
- Find middle of the linked list –
- Reverse a linked list in groups of given size –
- Find kth node from end of the linked list –
- Append the last n nodes of a linked list to the beginning of the list –
- Check whether linked list is palindrome or not –
- Fold a Linked List –
- Insert at given Position –
- Deletion at given Position –
Singly Linked List
- Introduction to Linked List in Data Structure
- Linked List in – C | C++ | Java
- Singly Linked List in – C | C++ | Java
- Insertion in singly Linked List – C | C++ | Java
- Deletion in singly Linked List – C | C++ | Java
- Reverse a linked list without changing links between nodes (Data reverse only) – C | C++ | Java
- Linked List Insertion and Deletion – C | C++ | Java
- Reverse a linked list by changing links between nodes – C | C++ | Java
- Linked List insertion in the middle – C | C++ | Java
- Print reverse of a linked list without actually reversing – C |C++ | Java
- Search an element in a linked list – C | C++ | Java
- Insertion in a Sorted Linked List – C | C++ | Java
- Delete alternate nodes of a Linked List – C | C++ | Java
- Find middle of the linked list – C | C++ | Java
- Reverse a linked list in groups of given size – C | C++ | Java
- Find kth node from end of the linked list – C | C++ | Java
- Append the last n nodes of a linked list to the beginning of the list – C | C++ | Java
- Check whether linked list is palindrome or not – C | C++ | Java
- Fold a Linked List – C | C++ | Java
- Insert at a given position – C | C++ | Java
- Delete at a given position – C | C++ | Java
Login/Signup to comment