What are XOR Linked Lists in Data Structure?

An XOR linked list is a data structure that uses the bitwise XOR operation to store the memory addresses of the next and previous nodes in a doubly linked list. This allows for efficient traversal of the list in both directions without the need for additional memory to store the previous node pointers. The XOR operation is used to encode and decode the memory addresses of the next and previous nodes. The XOR linked list is useful in certain memory-constrained environments where traditional doubly linked lists would consume too much memory.

How Does XOR Linked List Works in Data Structure?

An XOR linked list works by using the XOR (exclusive or) operation to encode and decode the memory addresses of the next and previous nodes in the list. The XOR operation compares the bits of two input values and returns a new value where each bit is the result of the XOR operation on the corresponding bits of the input values.

For example, suppose we have two memory addresses A and B, and we want to encode them in a single memory location. We can use the XOR operation to combine the addresses, resulting in a new value C = A XOR B. To later retrieve the original addresses, we can use the XOR operation again with C and one of the original addresses, say A. This will give us B = C XOR A.

In an XOR linked list, each node stores the XOR of the memory addresses of the next and previous nodes, allowing for efficient traversal of the list in both directions without the need for additional memory to store the previous node pointers.

For example, if the current node has address A, the next node has address B and the previous node has address C, the current node will store the XOR of B and C. To go to the next node, the address of the current node is XORed with the stored value to get the address of the next node. When we move back to the previous node, we can use the same technique to find the address of the previous node.

It is worth noting that XOR linked list is a memory efficient data structure when memory is a constraint but it is not cache-friendly as it requires random access to memory which can slow down the performance.

Types of XOR Linked List

There are two main types of XOR linked list:

  1. Singly XOR linked list: A singly XOR linked list is a variation of the XOR linked list that uses the XOR operation to store the memory address of the next node in a singly linked list. In this type of list, each node stores the XOR of the memory address of the next node and the memory address of the current node. To traverse the list in the forward direction, the current node's stored value is XORed with the current node's memory address to get the memory address of the next node.

  2. Doubly XOR linked list: A doubly XOR linked list is a variation of the XOR linked list that uses the XOR operation to store the memory addresses of the next and previous nodes in a doubly linked list. In this type of list, each node stores the XOR of the memory addresses of the next and previous nodes. To traverse the list in the forward direction, the current node's stored value is XORed with the current node's memory address to get the memory address of the next node. To traverse the list in the reverse direction, the current node's stored value is XORed with the next node's memory address to get the memory address of the previous node.

It is also worth noting that there are other variations of XOR linked list such as circular XOR linked list and multi-list XOR linked list.

Example of XOR Linked List

#include <iostream>
#include <cstdint> // for uintptr_t

struct Node {
    int data;
    Node* both; // XOR of next and prev
};

class XORLinkedList {
private:
    Node* head;
    Node* tail;
    Node* XOR(Node* a, Node* b);

public:
    XORLinkedList();
    void insert_at_head(int data);
    void insert_at_tail(int data);
    void delete_from_head();
    void delete_from_tail();
    void print_list();
};

XORLinkedList::XORLinkedList() {
    head = tail = nullptr;
}

Node* XORLinkedList::XOR(Node* a, Node* b) {
    return (Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}

void XORLinkedList::insert_at_head(int data) {
    Node* new_node = new Node();
    new_node->data = data;
    new_node->both = XOR(nullptr, head);
    if (head) {
        head->both = XOR(new_node, XOR(head->both, nullptr));
    } else {
        tail = new_node;
    }
    head = new_node;
}

void XORLinkedList::insert_at_tail(int data) {
    Node* new_node = new Node();
    new_node->data = data;
    new_node->both = XOR(tail, nullptr);
    if (tail) {
        tail->both = XOR(XOR(tail->both, nullptr), new_node);
    } else {
        head = new_node;
    }
    tail = new_node;
}

void XORLinkedList::delete_from_head() {
    if (head) {
        Node* next = XOR(head->both, nullptr);
        delete head;
        head = next;
        if (next) {
            next->both = XOR(next->both, head);
        } else {
            tail = nullptr;
        }
    }
}

void XORLinkedList::delete_from_tail() {
    if (tail) {
        Node* prev = XOR(tail->both, nullptr);
        delete tail;
        tail = prev;
        if (prev) {
            prev->both = XOR(prev->both, tail);
        } else {
            head = nullptr;
        }
    }
}

void XORLinkedList::print_list() {
    Node* current = head;
    Node* prev = nullptr;
    while (current) {
        std::cout << current->data << " ";
        Node* next = XOR(prev, current->both);
        prev = current;
        current = next;
    }
    std::cout << std::endl;
}

int main() {
    XORLinkedList list;
    list.insert_at_head(1);
    list.insert_at_head(2);
    list.insert_at_tail(3);
    list.insert_at_tail(4);
    list.print_list(); // prints 2 1 3 4
    list.delete_from_head();
    list.print_list(); // prints 1 3 4
    list.delete_from_tail();
    list.print_list(); // prints 1 3
    return 0;
}
// This example demonstrates how to use the XORLinkedList class to create a doubly linked list and perform various operations on it such as inserting elements at the head or tail, deleting elements from the head or tail, and printing the contents of the list.

It is worth noting that the examples I provided are simple and can be used as a reference to understand the basic idea behind XOR linked list but in real-world scenarios, the implementation may be more complex and may include additional features such as error handling, performance optimization.

Applications of XOR Linked List

XOR linked lists have a few specific use cases because of their unique properties:

  1. Memory-constrained environments: As XOR linked lists use the XOR operation to store the memory addresses of the next and previous nodes, they do not require additional memory to store the previous node pointers, making them a good choice for memory-constrained environments where traditional doubly linked lists would consume too much memory.

  2. Cache-oblivious algorithms: In cache-oblivious algorithms, memory access patterns are not known a priori and can change dynamically. Because XOR linked lists allow traversal of the list in both directions without additional memory, they can be used to implement cache-oblivious algorithms that need to access data in a random order.

  3. Graph traversal: XOR linked lists can be used to implement graph traversal algorithms, such as depth-first search, that need to traverse the graph in both directions.

  4. Cryptography: The XOR operation is used in many cryptographic algorithms, such as the one-time pad and stream ciphers, and XOR linked lists can be used to implement them in a more memory-efficient way.

  5. Some specific uses cases like LRU cache, Memory-efficient data structures, etc.

It's worth noting that, XOR linked list is not as widely used as other data structures like arrays, linked lists, and trees. The main reason is that it has a number of restrictions and drawbacks such as poor cache performance, complexity of implementation, and limited use cases.

Time and Space Complexity of XOR Linked List

The time complexity of operations on an XOR linked list depends on the specific operation being performed.

  1. Insertion at the head: O(1)
  2. Insertion at the tail: O(1)
  3. Deletion from the head: O(1)
  4. Deletion from the tail: O(1)
  5. Traversal: O(n)

The space complexity of an XOR linked list is O(n) where n is the number of elements in the list. Each element in the list requires a single memory location to store the data and the XOR value of the next and previous elements. Therefore, the total memory usage of an XOR linked list is O(n).

It's worth noting that XOR linked list is memory efficient but it is not cache-friendly as it requires random access to memory which can slow down the performance.

In general, the time complexity of an XOR linked list is similar to that of a traditional linked list, but the space complexity is lower, as it does not require additional memory to store previous node pointers. However, the implementation of XOR linked list is more complex, and it has poor cache performance, which can lead to slower performance in certain scenarios.

Advantages and Disadvantages of XOR Linked List

Advantages of XOR linked list:

  1. Memory efficient: XOR linked lists use the XOR operation to store the memory addresses of the next and previous nodes in a doubly linked list, which allows them to use less memory than traditional doubly linked lists.

  2. Cache-oblivious algorithms: They can be used to implement cache-oblivious algorithms that need to access data in a random order.

  3. Graph traversal: They can be used to implement graph traversal algorithms, such as depth-first search, that need to traverse the graph in both directions.

  4. Cryptography: The XOR operation is used in many cryptographic algorithms and XOR linked lists can be used to implement them in a more memory-efficient way.

Disadvantages of XOR linked list:

  1. Complex implementation: The implementation of XOR linked lists is more complex than traditional linked lists, as it requires the use of the XOR operation and bit manipulation.

  2. Poor cache performance: XOR linked lists require random access to memory, which can slow down performance in certain scenarios.

  3. Limited use cases: XOR linked lists have limited use cases due to their poor cache performance and complex implementation.

  4. It is not widely used as other data structures like arrays, linked lists, and trees.

  5. It is not as flexible as other data structures.

Overall, XOR linked lists are a specialized data structure that can be useful in certain memory-constrained environments and for specific use cases such as graph traversal and cryptography, but their complex implementation and poor cache performance make them less suitable for general-purpose use.