Insert node in sorted linked list

Insert node in sorted linked list

Today’s problem is to insert node in sorted linked list. Extension to thi statement will be to create linked list in sorted order. Every new node added to linked list should adhere to the fact the resultant linked list is in sorted order. For example,

List : 2->7->8->9->NULL Item to be inserted : 6
Resultant list : 2->6->7->8->9

This is very simple problem to solve. There are three cases below needs to be solved for, rest all is just traversing of linked list.

1. When there is no node in list and first node is added.
2. When new node to be added is less than head of list
3. New node to be added in middle or end of list.

Insert node in sorted linked list

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
 
//Add node to sorted list
void addNode(Node **headRef, int value){
	if(!(*headRef)) {
		*headRef = createNode(value);
		return;
	}
 
	Node *current = *headRef;
	//Special case when data is less than head itself
	if(value < current->data){
		Node *temp = createNode(value);
		temp->next = *headRef;
		*headRef = temp;
		return;
	}
	/*traverse till we find node greater 
         than value to be inserted.*/
	while(current && current->next 
              && current->next->data < value){
		current = current->next;
	}
 
	//Put new node between current and current next
	if(current){
		Node *temp = createNode(value);
		Node *next = current->next;
		current->next = temp;
		temp->next = next;
	}
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
    printf("NULL");
    printf("\n");
}
 
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
 
        addNode(&L1,12);
        addNode(&L1,10);
        addNode(&L1,8);
        addNode(&L1,6);
        addNode(&L1,4);
        addNode(&L1,2);
 
 	printList(L1);
 
        return 0;
}

Complexity of above algorithm to insert node in sorted linked list is O(n) to insert each new node, as entire list might have to be traversed if new node to be added is greater than all nodes already added.

There is a bit tricky implementation of same solution. We have used last pointer reference when we learned how to insert node at the end of list. Maintain a reference of next of current node. Check new node to be inserted using reference. If node being pointed by reference has data greater than value to be inserted, create a new node and point its next to node pointed by reference. Now change the reference itself to point to new node, which in turn changes the next pointer of previous node. (Remember we are modifying reference and not a pointer). Reference starts with pointing to head node.

Node **current = headRef

Insert node in sorted linked list: Implementation

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
 
//Add node to sorted list
void addNodeRef(Node **headRef, int value){
 
	//Start with referencing to head.
	Node **current = headRef;
 
	//Till we find that data of next node is greater than value
	//here current is reference to next node.
	while(*current && (*current)->data < value){
		current = &((*current)->next);
	}
	//Create new node
	Node *newNode = createNode(value);
 
	//New node's next should point to next node. 
	newNode->next = *current;
 
	/*As current is reference to next node, 
        that has to be set to new node.*/
	*current = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    printf("NULL");
    printf("\n");
}
 
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
 
        addNodeRef(&L1,12);
        addNodeRef(&L1,10);
        addNodeRef(&L1,8);
        addNodeRef(&L1,6);
        addNodeRef(&L1,4);
        addNodeRef(&L1,2);
 
 	printList(L1);
 
        return 0;
}

Let us understand what is going on here in code. First currentNext reference is declared which points to head node of list. Situation is something like below:

insert node in sorted linked list

Now we check if pointer being pointed at by currentNext is not null, and if data in that node is less than new node to be inserted. If data is less, we make currentNextRef pointer to point to next of currentNextRef node.

Once value in node pointed by currentNext is higher, we exit the while loop. At this point, currentNextRef is pointing to next node of current node. We make next of new node point to currentNextRef node and change currentNextRef to point to new node.

insert node in sorted linked list example

Complexity will be same but there is no explicit handling of above mentioned cases, they are implicitly handled.

For further problems on linked list, please refer : Linked list problem

Please share if there is something is missing or wrong. If you are interested in contributing to website, please contact us.