Insertion at Specific Position in a Circular Doubly Linked List in Java
Circular doubly linked lists are data structures that allow traversal in both forward and backward directions, forming a circular structure. They are useful for computational tasks like maintaining ordered sequences, implementing buffers, and managing real-time data updates. Insertion at a specific position in a circular doubly linked list involves linking the new node to its predecessor and successor while ensuring the integrity of the circular connections. Mastering these steps ensures the list maintains its structural properties and performance benefits, making it a powerful tool for developers and computer scientists.
Example:
![Insertion at Specific Position in a Circular Doubly Linked List in Java](https://static.tutorialandexample.com/java/insertion-at-specific-position-in-a-circular-doubly-linked-list-in-java1.png)
Input: elements = {1, 2, 3}, insert position = 2
Output: {1, 2, 4, 3}
Using Naive Approach
Algorithm
Step 1: Create node class with value, next, and previous pointers.
Step 2: Implement a method to print a custom list.
Step 3: Implement a method to count elements in the list.
Step 4: Implement a method to insert a node at the specified position.
Step 5: Initialize the list as an array reference for the start node.
Step 6: Print a custom list before insertion.
Step 7: Insert a new node with a specified value at a given position.
Step 8: Print the custom list after insertion.
Here is an implementation of insertion at a specific position in a circular doubly linked list using a naive approach :
FileName:CustomCircularDoublyLinkedList.java
import java.io.*; class CustomNode { int value; CustomNode next; CustomNode prev; public CustomNode(int value) { this.value = value; this.next = null; this.prev = null; } } public class CustomCircularDoublyLinkedList { // Method to print the custom list static void printCustomList(CustomNode start) { // Check if the list is empty if (start == null) { System.out.println("The list is empty."); return; } System.out.print("The list is: "); CustomNode temp = start; do { System.out.print(temp.value + " "); temp = temp.next; } while (temp != start); System.out.println(); } // Method to count the elements in the custom list static int countCustomList(CustomNode start) { // Check if the list is empty if (start == null) return 0; // Count the elements in the list int count = 0; CustomNode temp = start; do { count++; temp = temp.next; } while (temp != start); return count; } // Method to insert a node at a specified position in the custom list static boolean insertAtPosition(CustomNode[] startRef, int data, int loc) { // Count the elements in the list int count = countCustomList(startRef[0]); // Check if the insertion position is valid if (loc < 1 || loc > count + 1) return false; // Create a new node with the given data CustomNode newNode = new CustomNode(data); // If the list is empty if (startRef[0] == null) { startRef[0] = newNode; newNode.next = newNode; newNode.prev = newNode; } // If the node is to be inserted at the beginning else if (loc == 1) { newNode.next = startRef[0]; newNode.prev = startRef[0].prev; startRef[0].prev.next = newNode; startRef[0].prev = newNode; startRef[0] = newNode; } // If the node is to be inserted at any other position else { CustomNode temp = startRef[0]; int currPos = 1; // Traverse to the node before the desired position while (currPos < loc - 1) { temp = temp.next; currPos++; } // Insert the new node newNode.next = temp.next; newNode.prev = temp; temp.next.prev = newNode; temp.next = newNode; } return true; } public static void main(String[] args) { int[] elements = { 1, 2, 3, 4, 5, 6 }; int length = elements.length; CustomNode[] startRef = new CustomNode[1]; startRef[0] = null; for (int i = 0; i < length; i++) insertAtPosition(startRef, elements[i], i + 1); System.out.println("Before insertion:"); printCustomList(startRef[0]); insertAtPosition(startRef, 8, 3); System.out.println("After insertion:"); printCustomList(startRef[0]); } }
Output:
Before insertion: The list is: 1 2 3 4 5 6 After insertion: The list is: 1 2 8 3 4 5 6
Complexity analysis: The time complexity of creating a custom circular doubly linked list is O(n), as it requires traversing the entire list and traversing the entire list to count elements. The space complexity is O(n), as the space required for storing nodes grows linearly with the number of elements in the list.
Using Optimized Approach
Algorithm
Step 1: Create a node with value, next, and previous pointers.
Step 2: Print a message if the list is empty or traverses the list from the head node.
Step 3: Return a count of 0 if the list is empty.
Step 4: Determine the current size of the list, create a new node with the given value, set the new node's next and previous pointers to itself, and set the head to the new node.
Step 5: If the node is to be inserted at any other position, it's inserted just before the desired position.
Step 6: Initialize the list with given elements, print it before the insertion operation, insert a new node at the specified position, and print it after the insertion operation.
Here is an implementation of insertion at a specific position in a circular doubly linked list using an optimized approach :
FileName:CircularDoublyLinkedList.java
import java.io.*; class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; this.next = null; this.prev = null; } } public class CircularDoublyLinkedList { // Method to display the list static void printList(ListNode head) { if (head == null) { System.out.println("The list is empty."); return; } System.out.print("The list is: "); ListNode temp = head; do { System.out.print(temp.value + " "); temp = temp.next; } while (temp != head); System.out.println(); } // Method to count the elements in the list static int getListSize(ListNode head) { if (head == null) return 0; int count = 0; ListNode temp = head; do { count++; temp = temp.next; } while (temp != head); return count; } // Method to insert a node at a specified position static boolean insertNodeAtPosition(ListNode[] headRef, int value, int position) { int size = getListSize(headRef[0]); if (position < 1 || position > size + 1) return false; ListNode newNode = new ListNode(value); // If the list is empty if (headRef[0] == null) { headRef[0] = newNode; newNode.next = newNode; newNode.prev = newNode; } // If the node is to be inserted at the beginning else if (position == 1) { newNode.next = headRef[0]; newNode.prev = headRef[0].prev; headRef[0].prev.next = newNode; headRef[0].prev = newNode; headRef[0] = newNode; } else { ListNode temp = headRef[0]; int currentPos = 1; // Traverse to the node before the desired position while (currentPos < position - 1) { temp = temp.next; currentPos++; } newNode.next = temp.next; newNode.prev = temp; temp.next.prev = newNode; temp.next = newNode; } return true; } public static void main(String[] args) { int[] elements = { 1, 2, 3, 4, 5, 6 }; int length = elements.length; ListNode[] head = new ListNode[1]; head[0] = null; for (int i = 0; i < length; i++) insertNodeAtPosition(head, elements[i], i + 1); System.out.println("Before insertion:"); printList(head[0]); insertNodeAtPosition(head, 8, 3); System.out.println("After insertion:"); printList(head[0]); } }
Output:
Before insertion: The list is: 1 2 3 4 5 6 After insertion: The list is: 1 2 8 3 4 5 6
Complexity analysis: The above approach's time complexity is O(n) due to traversing all nodes. The space complexity is O(1) due to the constant usage of variables and new nodes.