Sorted insert for circular linked list

How to insert circular linked list nodes in Sorted from we are need to consider following points.

1) Initial linked list is empty so insert first node of linked list and assign this address to head pointer of linked list.

2) When linked list is not empty then first it check out first node of linked list are greater than or not of current inserted node. if first node are greater then inserted linked list node at front position. otherwise do step 3.

4) In this case we are confirm that linked list are not empty and new node will not added to front of linked list. In this situation this linked list nodes are iterating one by one. And use one other pointer which are hold the reference of previous iteration nodes. When upcoming nodes are greater then or equal to current inserted nodes. Then add this node to this location. If not found any big node and find last node of linked list. Then do step 5.

5) Note that circular linked list last node hold the reference of first node, then add new node at last position and connect last node to first node.

Suppose we are inserted the following (3, 5, 7, 4, 9, 10, 1, 2) node in a sequence.

Insert node at end

Here given code implementation process.

//C Program Sorted insertion of circular single linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function

//Create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element in sorted order
void insert(struct Node**head,int value){
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    node->data=value;
    node->next=NULL;
    if(*head==NULL){
      //no element of linked list
      *head=node;
      node->next=*head;
    }
    else{
      struct Node*temp=*head,*hold=NULL;
      if(temp->data>=value){
        //insert node at beginning
        //find first last node
        while(temp->next!=*head) temp=temp->next;
        //connect last node to new node
        temp->next=node;
        node->next=*head;
        *head=node;

      }else{
        hold=temp;
        //get inserted  location
        while(temp->next!=*head && value>temp->data){
          hold=temp;
          temp=temp->next;
        }
        if(temp->data>=value){
          //when add element of between two nodes
          node->next=hold->next;
          hold->next=node;
        }else{
          //when add element at last position
          node->next=temp->next;
          temp->next=node;
        }
      }
    }
  }
}
//Display element of Node
void display(struct Node*head){
  
  if(head==NULL){
    printf("Empty linked list");
  }
  else{
    printf("\n Linked List Element :");
    struct Node*temp=head;
    while(temp){
      printf("  %d",temp->data);
      temp=temp->next;
      if(temp==head){
        break; //terminate loop
      }
    }

  }
}
int main(){

  //create node pointer
  struct Node*head=NULL;
  //insert element of linked list
  insert(&head,3);
  insert(&head,5);
  insert(&head,7);
  insert(&head,4);
  insert(&head,9);
  insert(&head,10);
  insert(&head,1);
  insert(&head,2);
  //display all node
  display(head);
}

Output

 Linked List Element :  1  2  3  4  5  7  9  10
//C Program to insert circular linked list element
// in sorted order
#include<iostream>
using namespace std;

//create structure
struct Node{
  int data;
  struct Node*next;
};
class CircularList{
  Node *head;
public:
  CircularList();
  void insert(int);
  void display();
};
CircularList::CircularList(){
  head=NULL;
}

//insert Node in sorted order of linked list 
void CircularList:: insert(int value){
  //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL){
    cout<<"Memory overflow"<<endl;
  }else{
    node->data=value;
    node->next=NULL;
    if(head==NULL){
      //no element of linked list
      head=node;
      node->next=head;
    }
    else{
      Node*temp=head,*hold=NULL;
      if(temp->data>=value){
        //insert node at beginning
        //find first last node
        while(temp->next!=head) temp=temp->next;
        //connect last node to new node
        temp->next=node;
        node->next=head;
        head=node;

      }else{
        hold=temp;
        //get inserted  location
        while(temp->next!=head && value>temp->data){
          hold=temp;
          temp=temp->next;
        }
        if(temp->data>=value){
          //when add element of between two nodes
          node->next=hold->next;
          hold->next=node;
        }else{
          //when add element at last position
          node->next=temp->next;
          temp->next=node;
        }
      }
    }
  }
}
//display element of Node
void CircularList:: display(){
  
  if(head==NULL){
    cout<<"Empty linked list";
  }
  else{
    cout<<"Element of linked list :";
    struct Node*temp=head;
    while(temp){
      cout<<"  "<<temp->data;
      temp=temp->next;
      if(temp==head){
        break; //terminate loop
      }
    }

  }
}
int main(){
  CircularList obj=CircularList();
  //insert element of linked list
  obj.insert(3);
  obj.insert(5);
  obj.insert(7);
  obj.insert(4);
  obj.insert(9);
  obj.insert(10);
  obj.insert(1);
  obj.insert(2);
  //display all node
  obj.display();
}

Output

Element of linked list :  1  2  3  4  5  7  9  10
//Java Program to 
//Insert circular linked list node in sorted order
public class LinkedList{
  static class Node{
    int data;
    Node next;
  }
  static Node head;
  //Class constructors
  LinkedList(){
    head=null;
  } 
  //insert node in sorted order
  static void insert(int value){
    //Create a node
    Node node=new Node();
    node.data=value;
    node.next=head;
    if(head==null){
      //no element of linked list
      head=node;
      node.next=head;
    }
    else{
        Node temp=head,hold=null;
        if(temp.data>=value){
          //insert node at beginning
          //find first last node
          while(temp.next!=head) temp=temp.next;
          //connect last node to new node
          temp.next=node;
          node.next=head;
          head=node;

        }else{
          hold=temp;
        //get inserted  location
          while(temp.next!=head && value>temp.data){
            hold=temp;
            temp=temp.next;
          }
          if(temp.data>=value){
            //when add element of between two nodes
            node.next=hold.next;
            hold.next=node;
          }else{
            //when add element at last position
            node.next=temp.next;
            temp.next=node;
          }
        }
      }
  }
  //Display node element of circular linked list
  public static void display(){
    if(head==null){
      System.out.println("Empty Linked List");
    }else{
      System.out.print("Circular Linked List Element :");
      Node temp=head;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.next;
        if(temp==head) break;
      }
    }
  }


  
  public static void main(String[] args) {
    LinkedList obj=new LinkedList();
    obj.insert(3);
    obj.insert(5);
    obj.insert(7);
    obj.insert(4);
    obj.insert(9);
    obj.insert(10);
    obj.insert(1);
    obj.insert(2);

    obj.display();
    
  }
}

Output

Circular Linked List Element :  1  2  3  4  5  7  9  10
#Python program
#Sorted order insertion of circular linked list
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

#create class CircularList    
class CircularList:
  def __init__(self):
    #Assign default value
    self.head=None
    
  #Insert new node   
  def insert(self,data):
    node=Node(data)
    node.next=self.head
    if(self.head==None):
        #when no element of linked list
        self.head=node
        node.next=node
    else:
        temp=self.head
        hold=None
        if(temp.data>=data):
            #insert node at beginning
            #find first last node
            while(temp.next!=self.head): 
                temp=temp.next
            #connect last node to new node
            temp.next=node
            node.next=self.head
            self.head=node
        else:
            hold=temp
            #get inserted  location
            while(temp.next!=self.head and data>temp.data):
                hold=temp
                temp=temp.next
            if(temp.data>=data):
                #when add element of between two nodes
                node.next=hold.next
                hold.next=node
            else:
                #when add element at last position
                node.next=temp.next
                temp.next=node
          
           
  #display all element of circular linked list      
  def display(self):
    temp=self.head
    print("Linked list Elements : "),
    while(temp!=None):
      print(temp.data),
      temp=temp.next
      #when find first node
      if(temp==self.head):
        break

    print("\n")

def main():
    #Create Object of class CircularList
    obj=CircularList()
    #Insert element
    obj.insert(3);
    obj.insert(5);
    obj.insert(7);
    obj.insert(4);
    obj.insert(9);
    obj.insert(10);
    obj.insert(1);
    obj.insert(2);
    obj.display()    

if __name__ == '__main__':
  main()

Output

Linked list Elements :  1 2 3 4 5 7 9 10 
//C# program to circular linked list
//sorted insertion of elements
using System;
//node class
public class Node{
  public  int data;
  public  Node next;
}
class Program
{
  public Node head;
  public Program(){
    head=null;
  }
  //insert node of sorted order
  public void insert(int data){
    Node node=new Node();
    node.data=data;
    node.next=head;
    if(head==null){
      //when no element of linked list
      head=node;
      node.next=head;
    }
    else{
        Node temp=head,hold=null;
        if(temp.data>=data){
          //insert node at beginning
          //find first last node
          while(temp.next!=head) temp=temp.next;
          //connect last node to new node
          temp.next=node;
          node.next=head;
          head=node;

        }else{
          hold=temp;
        //get inserted  location
          while(temp.next!=head && data>temp.data){
            hold=temp;
            temp=temp.next;
          }
          if(temp.data>=data){
            //when add element of between two nodes
            node.next=hold.next;
            hold.next=node;
          }else{
            //when add element at last position
            node.next=temp.next;
            temp.next=node;
          }
        }
    }
  }
  //Display element of linked list
  public void display(){
    if(head==null){
      Console.Write("Empty Linked List");
    }else{
      Console.Write(" Circular Linke List : ");
      Node temp=head;
      while(temp!=null){
        Console.Write(" {0}",temp.data);
        temp=temp.next;
        //End of Loop iteration 
        if(temp==head) break;
      }
    }
  }

  
  static void Main(){

    Program obj=new Program();
    //Insert element data
    obj.insert(3);
    obj.insert(5);
    obj.insert(7);
    obj.insert(4);
    obj.insert(9);
    obj.insert(10);
    obj.insert(1);
    obj.insert(2);

    obj.display();
  }
}

Output

 Circular Linke List :  1 2 3 4 5 7 9 10


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved