XOR Linked list

You may have heard about singly, doubly and circular linked list.

But what exactly is XOR Linked list?

You got it right! It involves XOR Operation and Linked list

If you are not familiar with XOR Operations, I advice you to learn Basic Bit Manipulation first or read below.

Bit Manipulation involves manipulating bits(ofcourse binary values) so that we get our results without wasting time on writing logics, also called as bit magic.

These are the tables of bitwise operations

How this XOR works?

Look at this table

If you still can't understand, read here

Code and Approach

Why XOR Linked List?

It is memory efficient ( Doubly linked list is helpful than singly linked list because every node has previous node's address, but it acquires extra space, what if we implement a doubly linked list in singly linked list! XOR Linked list can do it magic)
You can travel in any direction with XOR Linked list
Every node has two parts atleast, one for data, other for address of next node. XOR Linked list stores XOR of address of previous node and its next node.

Still cant understand... right?

Imagine a node (Okay, I am lazy to draw, upload and paste a node here). It has two parts, one for data, other for address. In singly linked list it stores address of next node, in doubly linked list it stores address of previous and next node in the sequence. In this node (XOR Linked list's node), it stores address by doing an XOR Operation. And it does XOR Operation on what 2 values, these are previos node's address and next node's address.

Now what if its the first node, it will store addres as NULL XOR NULL, as its previous and next both are NULL.

Now how to move backward and forward with just one section to store address.

To move forward - XOR of address section of current node and previous node

To move backward - XOR of address section of current node with next element

Suppose we have this list

NULL <-> 1 <-> 2 <-> 3 <->NULL

Here 1 is pointing to both NULL and 2, and 2 is pointing to both 2 1 and 3, likewise 3 is pointing to 2 and NULL

Let head = 1

Lets check whats in the address part of node 1...

The address section of node, can be names as npx, instead of saying address section again and again

So the data in head is 1 and npx is XOR of previous node and next node
So the npx = XOR(NULL,2) where NULL is previous and 2 is next node in sequence

Similarly for node 2, the npx = XOR(1, 3) where 1 is previous and 3 is next node

Lets check how to determine next node in sequence while making an XOR linked list from scratch

Assume we made a node, head, inserted data and marked its npx as NULL

for convenience read the code below


struct Node
{
    int data;
    struct Node* npx;

    Node(int x){
        data = x;
        npx = NULL;
    }
};

So the node 1 has data 1 and npx = XOR of previous and next, i.e, XOR of NULL and NULL, since it is the first node in our list, so its npx = NULL as XOR of (NULL, NULL) is NULL.

Insert a node with value 2 in this list

Create a node, add value 2
For npx, we know it will XOR of previous and next node You will think now we have to keep track of its previous every time list is updated. But we are not going to use any extra space for this purpose, instead, we will update head each time we insert new node, so after insertion of 2nd node, head will move to this node and no more point to first one.

So the npx for node 2 is XOR of (head->npx,NULL), so now it points to head->npx as previous node and its next node does not exist hence NULL for next node.

But here is a twist once again, now head should point this new node and in the head node(which is still node 1 here), should have node 2 in its npx instead of having NULL XOR NULL.

So update npx of head, by putting XOR of node 2 and XOR of head->npx and NULL which evaluated to head->npx, and in the end we are left with head->npx XOR node 2, and we have successfully updated npx of node 1.

Now make head = node 2

And yes we are done with it, likewise we'll add node 3

Let me discuss it more clearly

npx of node 1 - NULL XOR NULL
npx of node 2 - 1 XOR NULL, update for node1 npx = NULL XOR 2
npx of node 3 - 2 XOR NULL, update for node2 npx = node 2 XOR NULL

How to move forward and backward

Moving forward

XOR of npx of current node and previous node

Suppose you are at node 1, want to move to node2 so take XOR like this
npx of current node -> NULL XOR 2 = 2
2 XOR NULL = 2, and the next node in sequence is 2

Move to node 3 from node 2

XOR of npx of node 2 and node 1
npx of Node 1 = NULL XOR 2 = 2
npx of Node 2 = 1 XOR 2 = 3

How 1 XOR 2 = 3 and NULL XOR 2 = 2

1 = 0001
2 = 0010

0001 ^ 0010 = 0011

and what 0011 is in decimals, its 3

NULL = 0000
2 = 0010

0000 ^ 0010 = 0010, which is 2 in decimal

Hope you got good idea of how we traverse and insert nodes in this list

See the code for better understanding
This code is solution for problem at GFG

struct Node
{
    int data;
    struct Node* npx;

    Node(int x){
        data = x;
        npx = NULL;
    }
};

Utility function to get XOR of two Struct Node pointer
use this function to get XOR of two pointers
struct Node* XOR (struct Node *a, struct Node *b)
{
    return (struct Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
*/

// function should insert the data to the front of the list



struct Node* insert(struct Node *head, int data)
{
   struct Node *new_node = new Node(data);
   new_node->npx = XOR(head,NULL);
   if (head!= NULL)
   {
   struct Node *next = XOR(head->npx, NULL);
   head->npx = XOR(new_node, next);
   }
   head = new_node;
}

vector<int> printList (struct Node *head)
{
   struct Node *curr = head;
   struct Node *prev = NULL;
   struct Node *next;

   vector<int> res;
   while (curr != NULL)
   {
   res.push_back(curr->data);
   next = XOR(prev, curr->npx);
   prev = curr;
   curr = next;
   }
   return res;
}

Blog

Sakshi