### Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

### XOR Linked List

XOR linked list is the memory-efficient version of the doubly linked list, in which the next pointer of every node stores the XOR of the previous and next nodeâ€™s address. A XOR linked list uses only one address space per node to store the address of the previous and next node, while a doubly linked list uses two address spaces per node to store the address of the previous and next list node (prev, next).

To learn more about XOR linked list, please visit this article Memory Efficient Doubly Linked List.

### Problem Statement

In this problem, we are given a singly linked list and have to convert it to the XOR linked list.

### Problem Statement Understanding

In this problem, we will be discussing how we can convert a singly linked list to XOR linked list. We will be provided with a singly linked list as the input, and our task will be to somehow convert this singly linked list to a XOR linked list.

**Given singly linked list**

**Converted XOR linked list**

**An important XOR property:**

- If
**A XOR B = C**, then**A XOR C = B**, as well as**B XOR C = A**.

### Approach

In a XOR linked list, each pointer stores the XOR of prev and next node address, so the approach is:

- First, we traverse the singly linked list and keep track of the previous node in a pointer.
- While we are traversing the list, we will change the next pointer of every node as
**curr.next = XOR(prev, next)**.

### Algorithm

1) Create three nodes:

- A
**current node**, initially**pointing to the head**. - A
**previous node**, initially**pointing to the null**. - A
**next node**, initially**pointing to the current.next**.

2) Iterate while**current is not null**: - Update
**next to current.next**. - Update
**current.next to XOR(prev, next)**. - Update
**previous to current**. - Update
**current to next**.

#### printingXOR()

- In the
**PrintingXOR function**, we will start with a node previous, which will point to NULL, and a node current, which will point to the head. - Now, we will print current.data.
- For the traversal, we will now need the address of the next node. We can get that by calculating
**address(previous node) XOR address(current.next)**. - After getting the next node address, we will update our previous to current and current to the next node address.
- This process will go on till we reach the end of the list.

### Algorithm

1) Create a **previous node**, a **current node**, and a **next node**.

2) Make **previous point to NULL** and **current to the head**.

3) Iterate while **current** is not null:

- Print current.data.
- Store the address of the next node as
**address(previous) XOR address(current.next)**. - Update the
**previous to current**and the**current to the next node address**.

### Code Implementation

// Linked list node class Node { int data; Node next; Node(int item) { data = item; next = null; } } public class PrepBytes { static Node root; // Printing singly linked list static void printing(Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } System.out.println(); } static Node XOR(Node a, Node b) { return b; } // This function will convert singly linked list // to XOR linked list static void convertToXOR(Node head) { Node current = head; Node prev = null; Node next = current.next; while (current != null) { next = current.next; current.next = XOR(prev, next); prev = current; current = next; } } // This function will print the converted XOR linked list static void printingXOR(Node head) { Node curr = head; Node prev = null; Node next; while (curr != null) { // print current node System.out.print(curr.data + " "); next = XOR(prev, curr.next); prev = curr; curr = next; } System.out.println(); } public static void main(String[] args) { PrepBytes prep = new PrepBytes(); prep.root = new Node(53); prep.root.next = new Node(69); prep.root.next.next = new Node(96); prep.root.next.next.next = new Node(27); System.out.println("Singly Linked List Before Conversion: "); printing(root); convertToXOR(root); System.out.println("After Conversion to XOR Linked List: "); printingXOR(root); } }

### Output

Singly Linked List Before Conversion:

53 69 96 27

After Conversion to XOR Linked List:

53 69 96 27

**Time Complexity**: O(n), as we are only traversing the list.

So, in this article, we have tried to explain the most effective way to convert singly linked list to XOR linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.