Convert Singly Linked List to XOR Linked List in Java
A linked list with an extra field on each node that holds the XOR of the addresses of the node before and after it is called an XOR Linked List. This allows for memory-efficient storage and enables traversal in both directions without using extra space for pointers.
Approach 1: Using XOR Approach
The approach used for converting a Singly Linked List to an XOR Linked List. This approach involves updating the next pointer of each node in the Singly Linked List to store the XOR of the addresses of its previous and next nodes. This approach simplifies the XOR Linked List conversion by directly updating pointers without using a separate XORPointer class or complex XOR operations.
Algorithm
Step 1: Start with the root node of the Singly Linked List.
Step 2: Iterate through the linked list nodes.
Step 3: For each node:
Step 3.1: Store the next node in a temporary variable.
Step 3.2: Update the next pointer of the current node to store the XOR of the addresses of its previous and next nodes.
Step 3.3: Update the previous node to be the current node.
Step 3.4: Move to the next node.
FileName: XORLinkedListConversion.java
// Linked list node class class Node { int data; // Data stored in the node Node next; // Pointer to the next node in the list // Constructor to initialize a node with given data Node(int item) { data = item; next = null; } } public class XORLinkedListConversion { static Node root; // Static root node of the linked list // Function to print a singly linked list static void printLinkedList(Node head) { while (head != null) { System.out.print(head.data + " "); // Print the data of the current node head = head.next; // Move to the next node } System.out.println(); // Print a new line after printing the list } // XOR function to simulate XOR operation (not used in this example) static Node XOR(Node a, Node b) { return b; // For simplicity, return the second node } // Function to convert a singly linked list to an XOR linked list static void convertToXORLinkedList(Node head) { Node current = head; // Start from the head of the linked list Node prev = null; // Initialize previous node as null Node next; // Temporary variable to store the next node while (current != null) { // Iterate until the end of the list next = current.next; // Store the next node in 'next' // Update the 'next' pointer of the current node to store the XOR of 'prev' and 'next' current.next = XOR(prev, next); prev = current; // Update 'prev' to be the current node current = next; // Move to the next node } } // Function to print the converted XOR linked list static void printXORLinkedList(Node head) { Node curr = head; // Start from the head of the XOR linked list Node prev = null; // Initialize previous node as null Node next; // Temporary variable to store the next node while (curr != null) { // Iterate until the end of the list // Print the data of the current node System.out.print(curr.data + " "); next = XOR(prev, curr.next); // Calculate the next node using XOR prev = curr; // Update 'prev' to be the current node curr = next; // Move to the next node } System.out.println(); // Print a new line after printing the list } public static void main(String[] args) { XORLinkedListConversion xorr = new XORLinkedListConversion(); // Create an instance of the class // Create a singly linked list with nodes containing data xorr.root = new Node(2); xorr.root.next = new Node(4); xorr.root.next.next = new Node(6); xorr.root.next.next.next = new Node(8); System.out.println("Singly Linked List Before Conversion: "); printLinkedList(root); // Print the original linked list convertToXORLinkedList(root); // Convert the linked list to XOR linked list System.out.println("After Conversion to XOR Linked List: "); printXORLinkedList(root); // Print the converted XOR linked list } }
Output
Singly Linked List Before Conversion: 2 4 6 8 After Conversion to XOR Linked List: 2 4 6 8
Time Complexity: An algorithm's time complexity is O(n), where n is the number of nodes in the linked list. This is because we need to iterate through each node once to update the XOR pointers.
Space Complexity: The space complexity of an algorithm is O(1) because we are not using any additional data structures that grow with the input size. We only use a few pointers and temporary variables, which are constant in size regardless of the input size.