Convert Singly Linked List To Xor Linked List In C++

In this tutorial, we will explore the process of transforming a Singly Linked List into an XOR Linked List using C++. Prior to delving into the implementation details, let's first gain an understanding of both the Singly Linked List and XOR Linked List data structures.

What are Singly Linked Lists?

Singly linked lists are a type of linked list where each node points to the next node in the sequence. Unlike in a doubly linked list, there is no pointer referencing the previous node in this structure. Consequently, traversal of the list is limited to only moving forward.

A pointer referred to as head directs to the initial item in the list, while a tail pointer directs to the final item in the list.

Operations on Singly Listed Lists are:

• ✅ Items can be added to the head.
• ✅ Items can be inserted at the end.
• ✅ Searching for an element in the list.
• ✅ Insert one element after another element.
• ✅ Delete the item at the end.
• ✅ Delete the item anywhere in the list.
• ✅ Items can be removed from the head.

What are XOR Linked Lists?

The more memory-conscious version of the doubly linked list is referred to as an XOR linked list, where each node's pointer contains the XOR of its address from the preceding and succeeding nodes. In an XOR linked list, the addresses of the previous and next nodes are combined and stored in a single address space per node, unlike a doubly linked list that maintains separate address spaces for the previous and next list nodes (prev, next).

Method for Creating an XOR linked list from a singly linked list:

• ✅ An XOR linked list contains the XOR of the previous and next node addresses in each pointer.
• ✅ Initially, we iterate through the singly linked list, which maintains a pointer to the preceding node.
• ✅ We will modify each node's nexcpp tutorialer as we traverse the list by using next = XOR(prev, next).

Algorithm for creating a XOR linked list from a Singly Linked List

• ✅ First, we need to create 3 nodes.
• ✅ A curr node that first directs towards the head.
• ✅ A prev node thacpp tutorialed to the null at first.
• ✅ The next node pointed to the curr at first.
• ✅ Repeat as long as the curr is not null:
• ✅ Update next to curr.next.
• ✅ Update curr.next to XOR(prev, next).
• ✅ Update the prev to the curr.
• ✅ Update curr to the next.
• ✅ displayingXOR

Printing XOR:

• ✅ We will begin the PrintingXOR function with a node prev thacpp tutorials to NULL and a node curr thacpp tutorials to the head.
• ✅ We are about to print the curr data.
• ✅ Now, we need the address of the subsequent node for the traversal.
• ✅ The calculation is as follows: address (prev node) XOR address (curr.next).
• ✅ We will update our curr to the next node address and our prev to the curr after obtaining the next node address.
• ✅ This whole process continues until the end of the list.

Example:

Let's consider a scenario where we convert a Singly Linked List to an XOR Linked List using C++.

#include <iostream>
#include <cstdint>
using namespace std;
// Node structure for the XOR linked list
struct Node {
    int data;
    uintptr_t xorPtr; // Pointer that holds XOR of next and previous node addresses
};
class XORLinkedList {
private:
    Node *head;
public:
    XORLinkedList() : head(nullptr) {}
    void insert(int data) {
        Node *newNode = new Node;
        newNode->data = data;
        newNode->xorPtr = reinterpret_cast<uintptr_t>(nullptr);
        if (head == nullptr) {
            head = newNode;
        } else {
            newNode->xorPtr = reinterpret_cast<uintptr_t>(head);
            head->xorPtr ^= reinterpret_cast<uintptr_t>(newNode);
            head = newNode;
        }
    }
    // Function to traverse the XOR linked list in the forward direction
    void traverseForward() {
        Node *prev = nullptr;
        Node *current = head;
        Node *next;
        while (current != nullptr) {
            cout << current->data << " ";
            // Move to the next node
            next = reinterpret_cast<Node *>(reinterpret_cast<uintptr_t>(prev) ^ current->xorPtr);
            // Update prev and currencpp tutorialers
            prev = current;
            current = next;
        }
        cout << endl;
    }
};
int main() {
    XORLinkedList xorList;
    // Insert elements into the list until the user decides to stop
    int data;
    char choice;
    do {
        cout << "Enter data to insert: ";
        cin >> data;
        xorList.insert(data);
        cout << "If you want to insert element press 'y' else 'n' ";
        cin >> choice;
    } while (choice == 'y' || choice == 'Y');
    // Traverse the list
    cout << "XOR Linked List: ";
    xorList.traverseForward();
    return 0;
}

Output:

Explanation:

• ✅ In this example, the data and an XOR of the addresses of the previous and next nodes are stored in the Node structure.
• ✅ After that, the XORLinkedList class has methods for traversing the list forward and inserting nodes at the start.
• ✅ In order to preserve the XOR property, the insert method uses the XOR operation.
• ✅ In order to get the next node address, the traverseForward method iterates across the list using XOR logic.

Time Complexity:

• ✅ The time complexity is O(n) as we are iterating through the entire list.