Convert a Singly LinkedList to XOR LinkedList in C++
In computer science, linked lists are fundamental data structures that are used to store a sequence of elements. A singly linked list consists of nodes where each node contains a data field and a pointer to the next node in the sequence. On the other hand, XOR linked lists employ a bitwise XOR operation to store the addresses of the previous and next nodes in a single pointer field. In this article, we will discuss how to convert a singly linked list into an XOR-linked list using C++.
Singly Linked List: A linear data structure where each element (node) contains data and a reference (next pointer) to the next node in the sequence. It allows efficient insertions and deletions at the beginning (head) but requires traversing the list to reach specific nodes.
XOR Linked List: It is a space-efficient variation of a doubly linked list. Instead of separating the next and previous pointers, each node stores the XOR of the addresses of the previous and next nodes. It reduces memory usage but requires more complex traversal logic.
Conversion Process:
Node Structure: Define a node structure for the XOR linked list with an int data member to store the data and a pointer Node* next to hold the XOR value:
struct Node {
int data;
Node* next;
};
Conversion Function: Create a function convert that takes the head of the singly linked list as input and returns the head of the converted XOR linked list:
Node* convert(Node* head) {
Node* prev = nullptr;
Node* curr = head;
Node* next;
while (curr != nullptr) {
// XOR of prev and next addresses
next = (curr->next) ? (prev ^ curr->next) : nullptr;
// Update pointers for next iteration
curr->next = prev;
prev = curr;
curr = next;
}
// Return the new head (previously the last node)
return prev;
}
Explanation:
- First, initialize three pointers: prev (initially nullptr), curr pointing to the head, and next.
- Next, iterate while curr is not nullptr.
- Calculate the XOR of prev and curr->next (if it exists) to get the address of the next node in the XOR list. Store it in next.
- After that, update curr->next with the XOR of prev (current previous node) to enable traversing back in the XOR list during traversal/printing.
- Update prev to curr and curr to next for the next iteration.
- Due to the pointer updates, the final prev will be pointing to the last node (now the head of the XOR list). Return it.
Example:
Let us take an example to illustrate how to convert a singly linked list to XOR linked list in C++.
#include <iostream>
// Node structure for XOR Linked List
struct Node {
int data;
Node* next;
};
// Function to create a new node
Node* newNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->next = nullptr; // Initialize next to nullptr for new nodes
return temp;
}
// Function to convert a singly linked list to XOR linked list
Node* convertToXORLinkedList(Node* head) {
Node* prev = nullptr;
Node* curr = head;
Node* next;
while (curr != nullptr) {
next = curr->next; // Store the original next pointer
// Update the "next" pointer (XOR value) of the current node
curr->next = (Node*)((uintptr_t)prev ^ (uintptr_t)next);
// Move to the next node
prev = curr;
curr = next;
}
return prev;
}
void printXORLinkedList(Node* head) {
Node* curr = head;
Node* prev = nullptr;
while (curr != nullptr) {
std::cout << curr->data << " ";
Node* next = (Node*)((uintptr_t)prev ^ (uintptr_t)curr->next);
prev = curr;
curr = next;
}
std::cout << std::endl;
}
void deleteXORLinkedList(Node* head) {
Node* curr = head;
Node* prev = nullptr;
Node* next;
while (curr != nullptr) {
next = (Node*)((uintptr_t)prev ^ (uintptr_t)curr->next);
delete prev;
prev = curr;
curr = next;
}
delete prev;
}
int main() {
Node* head = newNode(10);
head->next = newNode(20);
head->next->next = newNode(30);
head = convertToXORLinkedList(head);
std::cout << "XOR Linked List: ";
printXORLinkedList(head);
deleteXORLinkedList(head);
return 0;
}
Output:
XOR Linked List: 30 20 10
Complexity Analysis:
Time Complexity:
1. Converting Singly Linked List to XOR Linked List (convertToXORLinkedList function):
- The function iterates through each node of the singly linked list once.
- Constant-time operations, such as pointer assignments and XOR operations, are performed inside the loop.
- Thus, the time complexity of converting the singly linked list to an XOR-linked list is O(n), where n is the number of nodes in the list.
2. Printing XOR Linked List (printXORLinkedList function):
- Like the conversion function, this function iterates through each node of the XOR linked list once.
- Constant-time operations, such as pointer assignments and XOR operations, are performed inside the loop.
- Therefore, the time complexity of printing the XOR-linked list is also O(n), where n is the number of nodes.
Space Complexity:
1. Converting Singly Linked List to XOR Linked List (convertToXORLinkedList function):
- The function only requires constant extra space for storing pointers and temporary variables.
- Therefore, the space complexity of the conversion function is O(1).
2. Printing XOR Linked List (printXORLinkedList function):
- Similar to the conversion function, this function also requires constant extra space for storing pointers and temporary variables.
- Hence, the space complexity of printing the XOR linked list is also O(1).
Applications:
Several applications of the XOR LinkedList in C++ are as follows:
- Memory-Constrained Environments: XOR-linked lists can benefit embedded systems or situations with limited memory due to their space-efficient design. They offer a compromise between traditional singly linked lists (less memory) and doubly linked lists (forward and backward traversal).
- Memory-Efficient Caches: They can implement caches where forward and backward traversals are necessary while optimizing memory usage.