Sorted insert for circular linked list

Difficulty Level: Rookie
Write a C function to insert a new value in a sorted Circular Linked List (CLL). For example, if the input CLL is following.

Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.

1) Linked List is empty:  
    a)  since new_node is the only node in CLL, make a self loop.      
          new_node->next = new_node;  
    b) change the head pointer to point to new node.
          *head_ref = new_node;
2) New node is to be inserted just before the head node:    
  (a) Find out the last node using a loop.
         while(current->next != *head_ref)
            current = current->next;
  (b) Change the next of last node. 
         current->next = new_node;
  (c) Change next of new node to point to head.
         new_node->next = *head_ref;
  (d) change the head pointer to point to new node.
         *head_ref = new_node;
3) New node is to be  inserted somewhere after the head: 
   (a) Locate the node after which new node is to be inserted.
         while ( current->next!= *head_ref && 
             current->next->data data)
         {   current = current->next;   }
   (b) Make next of new_node as next of the located pointer
         new_node->next = current->next;
   (c) Change the next of the located pointer
         current->next = new_node;

C++

// C++ program for sorted insert 
// in circular linked list 
#include <bits/stdc++.h> 
using namespace std; 
  
/* structure for a node */
class Node  
{  
    public: 
    int data;  
    Node *next;  
};  
  
/* function to insert a new_node in a list in sorted way.  
Note that this function expects a pointer to head node  
as this can modify the head of the input linked list */
void sortedInsert(Node** head_ref, Node* new_node)  
{  
    Node* current = *head_ref;  
      
    // Case 1 of the above algo  
    if (current == NULL)  
    {  
        new_node->next = new_node;  
        *head_ref = new_node;  
    }  
      
    // Case 2 of the above algo  
    else if (current->data >= new_node->data)  
    {  
        /* If value is smaller than head's value then  
        we need to change next of last node */
        while(current->next != *head_ref)  
            current = current->next;  
        current->next = new_node;  
        new_node->next = *head_ref;  
        *head_ref = new_node;  
    }  
      
    // Case 3 of the above algo  
    else
    {  
        /* Locate the node before the point of insertion */
        while (current->next!= *head_ref &&  
            current->next->data < new_node->data)  
        current = current->next;  
      
        new_node->next = current->next;  
        current->next = new_node;  
    }  
}  
  
/* Function to print nodes in a given linked list */
void printList(Node *start)  
{  
    Node *temp;  
      
    if(start != NULL)  
    {  
        temp = start;  
        do {  
        cout<<temp->data<<" ";  
        temp = temp->next;  
        } while(temp != start);  
    }  
}  
  
/* Driver code */
int main()  
{  
    int arr[] = {12, 56, 2, 11, 1, 90};  
    int list_size, i;  
      
    /* start with empty linked list */
    Node *start = NULL;  
    Node *temp;  
      
    /* Create linked list from the array arr[].  
        Created linked list will be 1->2->11->12->56->90 */
    for (i = 0; i< 6; i++)  
    {  
        temp = new Node(); 
        temp->data = arr[i];  
        sortedInsert(&start, temp);  
    }  
      
    printList(start);  
      
    return 0;  
}  
  
// This code is contributed by rathbhupendra. 

C

#include<stdio.h> 
#include<stdlib.h> 
  
/* structure for a node */
struct Node 
{ 
  int data; 
  struct Node *next; 
}; 
  
/* function to insert a new_node in a list in sorted way. 
   Note that this function expects a pointer to head node 
   as this can modify the head of the input linked list */
void sortedInsert(struct Node** head_ref, struct Node* new_node) 
{ 
  struct Node* current = *head_ref; 
  
  // Case 1 of the above algo 
  if (current == NULL) 
  { 
     new_node->next = new_node; 
     *head_ref = new_node; 
  } 
  
  // Case 2 of the above algo 
  else if (current->data >= new_node->data) 
  { 
    /* If value is smaller than head's value then 
      we need to change next of last node */
    while(current->next != *head_ref) 
        current = current->next; 
    current->next = new_node; 
    new_node->next = *head_ref; 
    *head_ref = new_node; 
  } 
  
  // Case 3 of the above algo 
  else
  { 
    /* Locate the node before the point of insertion */
    while (current->next!= *head_ref &&  
           current->next->data < new_node->data) 
      current = current->next; 
  
    new_node->next = current->next; 
    current->next = new_node; 
  } 
} 
  
/* Function to print nodes in a given linked list */
void printList(struct Node *start) 
{ 
  struct Node *temp; 
  
  if(start != NULL) 
  { 
    temp = start; 
    printf("
"); 
    do { 
      printf("%d ", temp->data); 
      temp = temp->next; 
    } while(temp != start); 
  } 
} 
  
/* Driver program to test above functions */
int main() 
{ 
  int arr[] = {12, 56, 2, 11, 1, 90}; 
  int list_size, i; 
  
  /* start with empty linked list */
  struct Node *start = NULL; 
  struct Node *temp; 
  
  /* Create linked list from the array arr[]. 
    Created linked list will be 1->2->11->12->56->90 */
  for (i = 0; i< 6; i++) 
  { 
    temp = (struct Node *)malloc(sizeof(struct Node)); 
    temp->data = arr[i]; 
    sortedInsert(&start, temp); 
  } 
  
  printList(start); 
  
  return 0; 
} 

Java

// Java program for sorted insert in circular linked list 
  
class Node 
{ 
    int data; 
    Node next; 
  
    Node(int d) 
    { 
        data = d; 
        next = null; 
    } 
} 
  
class LinkedList 
{ 
    Node head; 
  
    // Constructor 
    LinkedList()   { head = null; } 
  
    /* function to insert a new_node in a list in sorted way. 
     Note that this function expects a pointer to head node 
     as this can modify the head of the input linked list */
    void sortedInsert(Node new_node) 
    { 
        Node current = head; 
  
        // Case 1 of the above algo 
        if (current == null) 
        { 
            new_node.next = new_node; 
            head = new_node; 
  
        } 
  
        // Case 2 of the above algo 
        else if (current.data >= new_node.data) 
        { 
  
            /* If value is smaller than head's value then 
             we need to change next of last node */
            while (current.next != head) 
                current = current.next; 
  
            current.next = new_node; 
            new_node.next = head; 
            head = new_node; 
        } 
  
        // Case 3 of the above algo 
        else
        { 
  
            /* Locate the node before the point of insertion */
            while (current.next != head && 
                   current.next.data < new_node.data) 
                current = current.next; 
  
            new_node.next = current.next; 
            current.next = new_node; 
        } 
    } 
  
    // Utility method to print a linked list 
    void printList() 
    { 
        if (head != null) 
        { 
            Node temp = head; 
            do
            { 
                System.out.print(temp.data + " "); 
                temp = temp.next; 
            }  while (temp != head); 
        } 
    } 
  
    // Driver code to test above 
    public static void main(String[] args) 
    { 
        LinkedList list = new LinkedList(); 
  
        // Creating the linkedlist 
        int arr[] = new int[] {12, 56, 2, 11, 1, 90}; 
  
        /* start with empty linked list */
        Node temp = null; 
  
        /* Create linked list from the array arr[]. 
         Created linked list will be 1->2->11->12->56->90*/
        for (int i = 0; i < 6; i++) 
        { 
            temp = new Node(arr[i]); 
            list.sortedInsert(temp); 
        } 
  
        list.printList(); 
    } 
} 
  
// This code has been contributed by Mayank Jaiswal 

Python

# Node class  
class Node: 
  
    # Constructor to initialize the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
class LinkedList: 
  
    # Function to initialize head 
    def __init__(self): 
        self.head = None
  
    # Function to insert a new node at the beginning 
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node 
  
    # Utility function to print the linked LinkedList 
    def printList(self): 
        temp = self.head 
        print temp.data, 
        temp = temp.next
        while(temp != self.head): 
            print temp.data, 
            temp = temp.next
  
    """ function to insert a new_node in a list in sorted way. 
       Note that this function expects a pointer to head node 
       as this can modify the head of the input linked list """
    def sortedInsert(self, new_node): 
          
        current = self.head 
  
        # Case 1 of the above algo 
        if current is None: 
            new_node.next = new_node  
            self.head = new_node 
          
        # Case 2 of the above algo 
        elif (current.data >= new_node.data): 
              
            # If value is smaller than head's value then we 
            # need to change next of last node 
            while current.next != self.head : 
                current = current.next
            current.next = new_node 
            new_node.next = self.head 
            self.head = new_node             
  
          
        # Case 3 of the above algo 
        else: 
              
            # Locate the node before the point of insertion 
            while (current.next != self.head  and 
                   current.next.data < new_node.data): 
                current = current.next
  
            new_node.next = current.next
            current.next = new_node 
  
  
# Driver program to test the above function 
#llist = LinkedList() 
arr = [12, 56, 2, 11, 1, 90] 
  
list_size = len(arr) 
  
# start with empty linked list 
start = LinkedList() 
  
# Create linked list from the array arr[] 
# Created linked list will be 1->2->11->12->56->90 
for i in range(list_size): 
    temp = Node(arr[i]) 
    start.sortedInsert(temp) 
  
start.printList() 
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007) 

/div>

C#

// C# program for sorted insert  
// in circular linked list  
using System; 
  
class LinkedList  
{  
    public class Node  
    {  
        public int data;  
        public Node next;  
  
        public Node(int d)  
        {  
            data = d;  
            next = null;  
        }  
    }  
    Node head;  
  
    // Constructor  
    LinkedList()  
    {  
        head = null; 
    }  
  
    /* function to insert a new_node  
      in a list in sorted way. Note that  
      this function expects a pointer 
      to head node as this can modify 
      the head of the input linked list */
    void sortedInsert(Node new_node)  
    {  
        Node current = head;  
  
        // Case 1 of the above algo  
        if (current == null)  
        {  
            new_node.next = new_node;  
            head = new_node;  
  
        }  
  
        // Case 2 of the above algo  
        else if (current.data >= new_node.data)  
        {  
  
            /* If value is smaller than 
                head's value then we need 
                to change next of last node */
            while (current.next != head)  
                current = current.next;  
  
            current.next = new_node;  
            new_node.next = head;  
            head = new_node;  
        }  
  
        // Case 3 of the above algo  
        else
        {  
  
            /* Locate the node before  
            the point of insertion */
            while (current.next != head &&  
                current.next.data < new_node.data)  
                current = current.next;  
  
            new_node.next = current.next;  
            current.next = new_node;  
        }  
    }  
  
    // Utility method to print a linked list  
    void printList()  
    {  
        if (head != null)  
        {  
            Node temp = head;  
            do
            {  
                Console.Write(temp.data + " ");  
                temp = temp.next;  
            }  
            while (temp != head);  
        }  
    }  
  
    // Driver code   
    public static void Main(String []args)  
    {  
        LinkedList list = new LinkedList();  
  
        // Creating the linkedlist  
        int []arr = {12, 56, 2, 11, 1, 90};  
  
        /* start with empty linked list */
        Node temp = null;  
  
        /* Create linked list from the  
          array arr[]. Created linked list 
          will be 1->2->11->12->56->90*/
        for (int i = 0; i < 6; i++)  
        {  
            temp = new Node(arr[i]);  
            list.sortedInsert(temp);  
        }  
        list.printList();  
    }  
}  
  
// This code has been contributed  
// by Arnab Kundu 

Output:

1 2 11 12 56 90

Time Complexity: O(n) where n is the number of nodes in the given linked list.

Case 2 of the above algorithm/code can be optimized. To implement the suggested change we need to modify the case 2 to following.

// Case 2 of the above algo 
else if (current->data >= new_node->data) 
{ 
  // swap the data part of head node and new node 
  // assuming that we have a function swap(int *, int *) 
  swap(&(current->data), &(new_node->data));  
 
  new_node->next = (*head_ref)->next; 
  (*head_ref)->next = new_node; 
} 

Please write comments if you find the above code/algorithm incorrect, or find other ways to solve the same problem.

Sorted insert for circular linked list

C++

C

Java

Python

C#

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books