Rotate Operation in Linked List

There are a lot of operations that can be performed on a Linked List, like insertion operation where we can add a new node to the already existing linked list, deletion operation where we can delete a node from the linked list, and displaying the data present in all the nodes of the Linked List.

In a singly linked list, the node of the singly linked list points to the address of the memory location where the next node is stored. Similarly, in this way, all the nodes are storing the address of their respective next nodes. Other than the last node, the address in the pointer of the last node is NULL representing it is the last node of the linked list.

There is one more operation that is supported by a Linked List which is the rotate operation. In this operation, the head node of the linked list is moved to the last element of the Linked List, and the first element of the Linked List becomes the last element that is present in the Linked List.

C Code

Now let’s see the code of rotating or reversing a linked list in different programming languages.

  // A sample C program to rotate a given linked list     // stdio library is included to use the input output functionalities in the program  #include   #include       // a struct named node is defined that will represent the node of the Singly Linked List  // the struct object has two variables in it named data and next  struct Node {  // the data variable is of integer type and will be used to store the value associated with that particular node of the Singly Linked List  int data;  // the next variable is of struct node* type and will be used to store the address of the next node of the Singly Linked List  struct Node* next;  };// end of struct node        // A function named rotate is written that will rotate the linked list in a counterclockwise direction and update the head of the Linked List. It doesn’t modify the list if k is greater than or equal to the size  // So the function named rotate having two parameters named head_ref and k will represent the head node of the Linked List and k representing the number of nodes of the Linked List  // The head_ref variable is of struct Node* type and an integer variable named k  void rotate(struct Node** head_ref, int k)  {    // first of all we have to check the value of integer variable named k, if it is zero then we need not proceed further we can simply stop the rotate operation   if (k == 0)  return;    // Let us understand the code written below for example k = 4 and  // list = 25->30->35->40->45->50.  struct Node* current = *head_ref;    // current will either point to kth or NULL after this loop.  // current will point to node 40 in the above example  int count = 1;  while (count < k && current != NULL) {  current = current->next;  count++;  }    // If current is NULL, k is greater than or equal to count  // of nodes in the linked list. Don’t change the list in this case  if (current == NULL)  return;    // current points to kth node. Store it in a variable.  // kthNode points to node 40 in the above example  struct Node* kthNode = current;    // current will point to last node after this loop  // current will point to node 60 in the above example  while (current->next != NULL)  current = current->next;    // Change next of last node to previous head  // Next of 60 is now changed to node 10  current->next = *head_ref;    // Change head to (k+1)th node  // head is now changed to node 50  *head_ref = kthNode->next;    // change next of kth node to NULL  // next of 40 is now NULL  kthNode->next = NULL;  }//end of the rotate function      // A function named push is written to add a new node to the Linked List  // The function named push is written with two input parameters named head_ref and new_data  // The head_ref variable is of struct Node** type is representing the head of the Linked List to which we want to add the new node   // The new_data variable is of integer type that will represent the data the new node that we want to add to the Linked List will be stored in it   void push(struct Node** head_ref, int new_data)  {  // First of all, the new node that we want to add to the Linked List is allocated memory with the use of the malloc function  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));    // Once the memory is allocated to the new node, now the new_data variable holding the data to be stored in that node is linked with the new node that we want to add to the Linked List  new_node->data = new_data;    // The already existing Linked List is appended to the new node making the new node a part of the Linked List  new_node->next = (*head_ref);    // Once the already existing Linked List is appended with the new node now the head pointer is moved to the new node making the new node the head node of the Linked List  (*head_ref) = new_node;  } // end of the push function    // A function named printList is written to print the data in the nodes of the Singly Linked List   // The printList function has one parameter named node of the struct Node* type that will represent the head node of the Linked List   void printList(struct Node* node)  {  // The Linked List is traversed until the last element of the Singly Linked List is encountered  while (node != NULL) {  // while traversing the  Linked List the data present in the each node of the Singly Linked List is printed  printf(“%d “, node->data);  node = node->next;  }  } // end of the printList function          // main function is written to call all the functionalities functions of the Linked List written above that will rotate the Linked List  int main(void)  {  /* Start with the empty list */  struct Node* head = NULL;    // // create a list 10->20->30->40->50->60  // for (int i = 60; i > 0; i -= 10)  // push(&head, i);    // printf(“Given linked list n”);  // printList(head);  // rotate(&head, 4);    // printf(“nRotated Linked list n”);  // printList(head);  int data;  int count = 0;    char ch;                // Do-while loop              // Do part for performing actions              do              // Menu is displayed              // Users enter ‘y’ to continue ‘n’ if              // entered by user , the program terminates                {                    // Menu                    // Display messages                    printf(“Please Choose one of the Operations::n”);                    printf(“1. To Insert Data in the Linked List.n”);                    printf(“2. To Rotate the Linked List.n”);                    printf(“3. To Display Data present in the Linked List.n”);                    printf(“n”);                                          int choice;                    scanf(“%d”,&choice);                      // Switch case                    switch (choice) {                      // Case 1                    case 1:                            printf(“Enter the data that you want to add to the newly added node to the Linked List :n”);                          scanf(“%d”,&data);                          push(&head,data);                          count++;                          // Display message                          printf(“Data Added Successfully.n”);                          // Break statement to terminate a case                          break;                      // Case 2                    case 2:                            // Display message                          rotate(&head,count);                          printf(“Linked List Rotated Successfully.”);                          // Break statement to terminate a case                          break;                        // Case 3                    case 3:                            // Display message                    printf(“Data in the Linked List is:n”);                          printList(head);                          // Break statement to terminate a case                          break;                      default:                          // Print statement                          printf(“Please enter a valid option from the menu to proceed further.n n”);                          // Break statement                          break;                    }                        printf(“nType [N or n] to terminate the program.nType [Y or y] to continue the program.n”);                    scanf(” %c”,&ch);                                  } while (!(ch == ‘N’ || ch == ‘n’));      return (0);  }// end of main function  

Output:

The above code gives the following output:

Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 15 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 13 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 11 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 10 Please enter a valid option from the menu to proceed further. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 5 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 3 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 2 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 1 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 3 Data in the Linked List is: 1 2 3 5 11 13 15 Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 2 Linked List Rotated Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 3 Data in the Linked List is: 15 13 11 5 3 2 1 Type [N or n] to terminate the program. Type [Y or y] to continue the program. N

C++ Code

Now let’s see the C++ code of rotating or reversing a linked list.

  // A sample C++ program to rotate a given linked list     #include   using namespace std;    // a class named node is defined that will represent the node of the Singly Linked List  // the class object has two variables in it named data and next  class Node {  public:  // the data variable is of integer type and will be used to store the value associated with that particular node of the Singly Linked List  int data;  // the next variable is of class node* type and will be used to store the address of the next node of the Singly Linked List  Node* next;  };    // A function named rotate is written that will rotate the linked list in a counter-clockwise direction and update the head of the Linked List. It doesn’t modify the list if k is greater than or equal to the size  // So the function named rotate having two parameters named head_ref and k will represent the head node of the Linked List and k representing the number of nodes of the Linked List  // The head_ref variable is of struct Node* type and an integer variable named k  // The new_data variable is of integer type that will represent the data the new node that we want to add to the Linked List will be stored in it   void push(Node** head_ref, int new_data)  {  // First of all, the new node that we want to add to the Linked List is allocated memory with the use of the malloc function  Node* new_node = new Node();    // Once the memory is allocated to the new node, now the new_data variable holding the data to be stored in that node is linked with the new node that we want to add to the Linked List  new_node->data = new_data;    // The already existing Linked List is appended to the new node making the new node a part of the Linked List  new_node->next = (*head_ref);    // Once the already existing Linked List is appended with the new node now the head pointer is moved to the new node making the new node the head node of the Linked List  (*head_ref) = new_node;  }    // A function named printList is written to print the data in the nodes of the Singly Linked List   // The printList function has one parameter named node of the struct Node* type that will represent the head node of the Linked List   void printList(Node* node)  {  // The Linked List is traversed untill the last element of the Singly Linked List is encountered  while (node != NULL) {  // while traversing the  Linked List the data present in the each node of the Singly Linked List is printed  cout << node->data << ” “;  node = node->next;  }  } // end of the printList function      // main function is written to call all the functionalities functions of the Linked List written above that will rotate the Linked List  int main(void)  {  /* Start with the empty list */  Node* head = NULL;    int data;  int count = 0;    char ch;                // Do-while loop              // Do part for performing actions              do              // Menu is displayed              // Users enter ‘y’ to continue ‘n’ if              // entered by user , the program terminates                {                    // Menu                    // Display messages                    cout<<“Please Choose one of the Operations::n”;                    cout<<“1. To Insert Data in the Linked List.n”;                    cout<<“2. To Rotate the Linked List.n”;                    cout<<“3. To Display Data present in the Linked List.n”;                    cout<<“n”;                                          int choice;                    scanf(“%d”,&choice);                      // Switch case                    switch (choice) {                      // Case 1                    case 1:                            cout<<“Enter the data that you want to add to the newly added node to the Linked List :n”;                          cin>>data;                          push(&head,data);                          count++;                          // Display message                          cout<<“Data Added Successfully.n”;                          // Break statement to terminate a case                          break;                      // Case 2                    case 2:                            // Display message                          rotate(&head,count);                          cout<<“Linked List Rotated Successfully.”;                          // Break statement to terminate a case                          break;                        // Case 3                    case 3:                            // Display message                    cout<<“Data in the Linked List is:n”;                          printList(head);                          // Break statement to terminate a case                          break;                      default:                          // Print statement                          cout<<“Please enter a valid option from the menu to proceed further.n n”;                          // Break statement                          break;                    }                        cout<<“nType [N or n] to terminate the program.nType [Y or y] to continue the program.n”;                    cin>>ch;                                  } while (!(ch == ‘N’ || ch == ‘n’));      return (0);  }// end of main function  

Output:

This C++ code gives the following output,

Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 190 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 70 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 55 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 40 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 30 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 20 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 10 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 3 Data in the Linked List is: 10 20 30 40 55 70 190 Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 2 Linked List Rotated Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 3 Data in the Linked List is: 190 70 55 40 30 20 10 Type [N or n] to terminate the program. Type [Y or y] to continue the program. N

Java Code

Now let’s see the Java code of rotating or reversing a linked list.

  // A sample java program to rotate a given linked list     class LinkedList {  Node head; // head of the list        // a class named node is defined that will represent the node of the Singly Linked List  // the class object has two variables in it named data and next  class Node {    // the data variable is of integer type and will be used to store the value associated with that particular node of the Singly Linked List  int data;    // the next variable is of class node* type and will be used to store the address of the next node of the Singly Linked List  Node next;    Node(int d)  {  data = d;  next = null;  }  }    // A function named rotate is written that will rotate the linked list in a counter-clockwise direction and update the head of the Linked List. It doesn’t modify the list if k is greater than or equal to the size  // So the function named rotate having two parameters named head_ref and k will represent the head node of the Linked List and k representing the number of nodes of the Linked List  // The head_ref variable is of struct Node* type and an integer variable named k  void rotate(int k)  {  if (k == 0)  return;    // Let us understand the below code for example k = 4  // and list = 10->20->30->40->50->60.  Node current = head;    // current will either point to kth or NULL after this  // loop. current will point to node 40 in the above example  int count = 1;  while (count < k && current != null) {  current = current.next;  count++;  }    // If current is NULL, k is greater than or equal to count  // of nodes in linked list. Don’t change the list in this case  if (current == null)  return;    // current points to kth node. Store it in a variable.  // kthNode points to node 40 in the above example  Node kthNode = current;    // current will point to last node after this loop  // current will point to node 60 in the above example  while (current.next != null)  current = current.next;    // Change next of the last node to previous head  // Next of 60 is now changed to node 10    current.next = head;    // Change head to (k+1)th node  // head is now changed to node 50  head = kthNode.next;    // change next of kth node to null  kthNode.next = null;  }      // A function named push is written to add a new node to the Linked List  // The function named push is written with two input parameters named head_ref and new_data  // The head_ref variable is of struct Node** type is representing the head of the Linked List to which we want to add the new node   // The new_data variable is of integer type that will represent the data the new node that we want to add to the Linked List will be stored in it   void push(int new_data)  {    // First of all, the new node that we want to add to the Linked List is linked to an object of the Node class named new_node   Node new_node = new Node(new_data);    // The already existing Linked List is appended to the new node making the new node a part of the Linked List  new_node.next = head;    // Once the already existing Linked List is appended with the new node now the head pointer is moved to the new node making the new node the head node of the Linked List  head = new_node;  }      // A function named printList is written to print the data in the nodes of the Singly Linked List   void printList()  {  Node temp = head;  // The Linked List is traversed untill the last element of the Singly Linked List is encountered  while (temp != null) {  // while traversing the  Linked List the data present in the each node of the Singly Linked List is printed  System.out.print(temp.data + ” “);  temp = temp.next;  }  System.out.println();  }    // main function is written to call all the functionalities functions of the Linked List written above that will rotate the Linked List  public static void main(String args[])  {  LinkedList llist = new LinkedList();  Scanner sc = new Scanner(System.in);    // // create a list 10->20->30->40->50->60  // for (int i = 60; i >= 10; i -= 10)  // llist.push(i);    // System.out.println(“Given list”);  // llist.printList();    // llist.rotate(4);    // System.out.println(“Rotated Linked List”);  // llist.printList();      int data;  int count = 0;    char ch;                // Do-while loop              // Do part for performing actions              do              // Menu is displayed              // Users enter ‘y’ to continue ‘n’ if              // entered by user , the program terminates                {                    // Menu                    // Display messages                    System.out.println(“Please Choose one of the Operations::n”);                    System.out.println(“1. To Insert Data in the Linked List.n”);                    System.out.println(“2. To Rotate the Linked List.n”);                    System.out.println(“3. To Display Data present in the Linked List.n”);                    System.out.println(“n”);                                          int choice;                    choice = sc.nextInt();                      // Switch case                    switch (choice) {                      // Case 1                    case 1:                            System.out.println(“Enter the data that you want to add to the newly added node to the Linked List :n”);                          data = sc.nextInt();                          llist.push(data);                          count++;                          // Display message                          System.out.println(“Data Added Successfully.n”);                          // Break statement to terminate a case                          break;                      // Case 2                    case 2:                            // Display message                          llist.rotate(count);                          System.out.println(“Linked List Rotated Successfully.”);                          // Break statement to terminate a case                          break;                        // Case 3                    case 3:                            // Display message                    System.out.println(“Data in the Linked List is:n”);                          llist.printList();                          // Break statement to terminate a case                          break;                      default:                          // Print statement                          System.out.println(“Please enter a valid option from the menu to System.out.println(“Please enter a valid option from the menu to proceed further.n n”);                          // Break statement                          break;                    }                        System.out.println(“nType [N or n] to terminate the program.nType [Y or y] to continue the program.n”);                    ch = sc.nextLine().charAt(0);                                  } while (!(ch == ‘N’ || ch == ‘n’));  }//end of the main function  }   

Output:

Above java code gives the following output,

Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 1 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 2 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 3 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 4 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 5 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 1 Enter the data that you want to add to the newly added node to the Linked List: 6 Data Added Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 3 Data in the Linked List is: 1 2 3 4 5 6 Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 2 Linked List Rotated Successfully. Type [N or n] to terminate the program. Type [Y or y] to continue the program. y Please Choose one of the Operations:: 1. To Insert Data in the Linked List. 2. To Rotate the Linked List. 3. To Display Data present in the Linked List. 3 Data in the Linked List is: 6 5 4 3 2 1 Type [N or n] to terminate the program. Type [Y or y] to continue the program. N

So, in this article, we got a clear idea about a rotate operation in a linked list. We also saw how to write a code of rotate operation in the linked list in different programming languages like C, C++, and Java.

Next TopicSubarray with given sum

Rotate Operation in Linked List

Rotate Operation in Linked List

C Code

C++ Code

Java Code

Priority Queue using Linked list

Bitmap Indexing

You may also like