Last Updated on December 14, 2022 by Prepbytes
In this article, we will see another problem of linked list Convert singly linked list into xor linked list. Linked list is a linear data structures. The node in linked list consists of two parts i.e. the data and the pointer of the next node. Let’s see what exactly the XOR linked list is.
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. An 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.
How to convert singly linked list into xor linked list
In this problem, we are given a singly linked list and have to convert it to the XOR linked list.
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 an 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 of Convert singly linked list into xor linked list
In an 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 of Convert singly linked list into xor linked list
- 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.
- 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 the 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 of Convert singly linked list into xor linked list
- Create a previous node, a current node, and a next node.
- Make previous point to NULL and current to the head.
-
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 of Convert singly linked list into xor linked list
// 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 27Time Complexity of Convert singly linked list into xor linked list: O(n), as we are only traversing the list.
Conclusion
So, in this article, we have tried to explain the most effective way to Convert singly linked list into xor linked list. This article taught us how to Convert singly linked list into xor linked list. Also, If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.
FAQs related to Convert singly linked list into xor linked list
1. How will you convert a singly linked list to a circular linked list?
The algorithm is quite simple: Traverse the linked list and find the last node. If the node is the last node and points to NULL, make it point to the head node. The singly linked list has now been converted into the circular linked list.
2. What does a XOR linked list have?
The memory efficient Doubly Linked List is called XOR Linked List or Memory Efficient as the list uses bitwise XOR operation to save space for one address. In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.
3. What is XOR used for?
(eXclusive OR) A Boolean logic operation that is widely used in cryptography as well as in generating parity bits for error checking and fault tolerance. XOR compares two input bits and generates one output bit. The logic is simple. If the bits are the same, the result is 0.