What is in this article
If you have worked with Doubly Linked List, so you will noticed that it maintains two pointers for forward and backward traversing.

And this is the problem with Doubly Linked List. It is not a space efficient approach.

Because we can traverse both side (forward and backward) using only one pointer, with XOR Linked List.

What is a XOR Linked List
If we discuss about its formal definition then,

A XOR linked list is a memory efficient implementation of Doubly Linked List . As an ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes . XOR Linked List uses bitwise XOR operation to save space for one address . In XOR Linked List, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.

The new thing that you can notice in XOR Linked List , is that it stores XOR of addresses instead of actual address. And How ? will be clear , in a bit of time.

Node Structure in XOR Linked List
Node structure of XOR Linked List , is very similar to Singly Linked List.
It looks like something this :

	// c++
	struct  Node
	{
		data ;                  // to store data
		Node* np_ptr ;          // to store pointer
	    Node(value)             // to initialize node
	   {
		 data = value ;
		 np_ptr = NULL;
	   }
	}

This is almost same as Singly Linked List.

How np_ptr works
The technique through which XOR Linked List saves the space, is achieved through np_ptr.

Suppose we have four nodes A, B, C and D in a list. Then for
Node A :

np_ptr = 0 XOR add(B) // bitwise XOR of zero and address of B

, for Node B :

np_ptr = add(A) XOR add(C) // bitwise XOR of address of A and address of C

, for Node C :

np_ptr = add(B) XOR add(D) // bitwise XOR of address of B and address of D

, And for Node D :

np_ptr = add(C) XOR 0 // bitwise XOR of address of C and 0

will contain. So, it stores the XORed address of next and previous node. Now you may think, that then how we can traverse in both direction ? ,it will be clear when we will discuss traversing in XOR Linked List.

XOR of addresses
Before we start discussing traversing in XOR Linked List. We should discuss that, how we can XORed two address ? As they are not normal integers, so we can not use XOR operator, we have to write our own method for it.

And it will look like this :

	// c++
	Node* XOR(Node* node1, Node* node2)
	{
	  return (Node*)(uintptr_t(node1) ^ uintptr_t(node2)) ;  // uintptr_t in C++
	}

Traversing in XOR Linked List
Till now , we are saying that we can traverse in both direction in XOR Linked List just using one pointer. Let's we discuss now , how we can do that ?

We can traverse the XOR Linked List in both forward and backward direction . But one thing of which we have to care , while traversing the list , is that we need to remember the address of the previously accessed node in order to calculate the next node’s address .

As for Node C, we discussed that :

np_ptr = add(B) XOR add(D) // bitwise XOR of address of B and address of D

So, if we have Node B and we want to go on Node D from Node C, then we can do

add(D) = add(B) XOR np_ptr(C)
As
= add(B) XOR add(B) XOR add(D)
= 0 XOR add(D)
= add(D)

And we will get Node D.

Code for implementing it , can be like :

	// c++
	void traverse()
	{
	   Node* curr = head ;     // in starting curr points(refer) to head
	   Node* prev = NULL ;     // in starting previous is null
	   // for forward travesal
	   while (curr != NULL)    // while not reached end of list
	   {
		  cout << curr->data << ' ';            // print curr data
		  Node *next = XOR(prev, curr->np_ptr); // to get next node
		  prev = curr ;                         // storing curr as prev
		  curr = next ;                         // storing next as curr
	   }
   
	   cout << endl ;         // only for formattig output
	   // for backward traversal
	   // prev is pointing to last node after first while loop and
	   // curr is NULL after first while loop
		while (prev != NULL)   // till we reach before start of list
	   {
		  cout << prev->data << " ";             // print prev data
		  Node *next = XOR(curr, prev->np_ptr);  // to get next node
		  curr = prev ;                          // storing prev as curr
		  prev = next ;                          // storing next as prev
	   }
	}

You've Reached THE END!
we have now reached at the end of this article.

In this article, we have discussed What is XOR Linked List ?, What is the Node structure in it ?, And How we traverse in it ?

Thankyou for reading it till the end 🙂!