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) |
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.
leave a comment
0 Comments