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 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.

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;

}

}

static Node root; // Static root node of the linked list

// Function to print a singly linked list

System.out.print(head.data + " "); // Print the data of the current 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

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

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: ");

System.out.println("After Conversion to XOR Linked List: ");

}

}

Output