# Performing XOR Operation on Linked List

While a singly linked list stores data and the pointer to the next node, a doubly-linked list, on the other hand, has slots to store data, address of the previous node, and address of the next node. A doubly linked list allows us to perform operations like deletion and insertion more efficiently. We can also traverse the list in both directions. However, it takes more space than the singly linked list.

We can make it more memory efficient by using the XOR linked list. It works the same as the doubly linked list, but it uses a single slot to store addresses for the next and previous nodes. It does that by taking the bitwise XOR (^) of both addresses. It is also known as a memory-efficient doubly linked list.

To understand how this is possible, let’s look at the properties of XOR first.

 A^B B^A A^(B^C) (A^B)^C 0^A A A^A 0

## Traversal in XOR Linked List

Since it works like a doubly-linked list, we can traverse the list in both directions. First, let’s consider traversal from left to right. One thing to note here is that, at some node N, we have access to its previous node since we are going from left to right. Moreover, we have three types of nodes to consider, i.e., the first node, middle, and the last node.

The formula to get the next node is as follows:

`addr (next) = addr(prev)^addr(XOR value at current node)`

When we are at the first node A, it contains the XOR of NULL (previous node) and B (next node), i.e., 0^addr(B). The address of the next node can be found as follows:

```addr(next) = 0^(0^addr(B))

When we are at some middle node B, it contains the XOR of A(previous node) and C (next node), i.e., addr(A)^addr(C).

```addr(next) = addr(A)^(addr(A)^addr(C))

The last node C contains the XOR of B(previous node) and NULL (next node), i.e., addr(B)^0.

```addr(next) = addr(B)^(addr(B)^0)

We can perform the traversal from right to left in a similar manner, except we start from the tail, i.e., node C.

## Implementation

The following implementation of the XOR Linked List contains the following functionalities.

### Delete

It removes the first item from the list and returns the deleted data. First, it checks if the list is empty or not. If it is not, then it finds the next node. If the next node does not exist, then it sets the head and tail pointer to NULL. Otherwise, its xadd value gets updated to the address of the node after that, i.e., addr(current head)^(xadd value of the next node). The next node becomes the head now.

### LR_traversal

It traverses the list in the forward direction.

### RL_traversal

It traverses the list in the backward direction.

The code is given below.

```import _ctypes
class Node:
self.value = value #data

def __init__(self):
self.tail = None
self.nodes = []

#adds an item at the beginning of the list
def insert(self, value):
if self.head == None: #node to be inserted is the first node
else:
new_node = Node(value, 0^id(self.head)) #create new node with xadd value equal to address of the next node

#deletes an item from the beginning of the list
def delete(self):
if next_node:
next_node = _ctypes.PyObj_FromPtr(next_node) #get the node placed at the given address
else:
self.tail = None
self.nodes.pop().value
return del_val

#print list items in the forward direction
def LR_traversal(self):
prev_node = 0
while curr_node:
curr_node = _ctypes.PyObj_FromPtr(curr_node) #get the node placed at the given address
print(curr_node.value, end=" ") #display the value of the current node
#update the current and previous nodes
prev_node = id(curr_node)
curr_node = next

#print list items in the backward direction
def RL_traversal(self):
curr_node = id(self.tail) #get the address of the last node
prev_node = 0
while curr_node:
curr_node = _ctypes.PyObj_FromPtr(curr_node) #get the node placed at the given address
print(curr_node.value, end=" ") #display the value of the current node
#update the current and previous nodes
prev_node = id(curr_node)
curr_node = next

ll.insert(2)
ll.insert(3)
ll.insert(1)
ll.insert(5)

print("Left to Right Traversal of the XOR Linked List")
ll.LR_traversal()

print("\nRight to Left Traversal of the XOR Linked List")
ll.RL_traversal()

print("\nDeleted Value:",ll.delete())
print("Deleted Value:",ll.delete())

print("Left to Right Traversal of the XOR Linked List")
ll.LR_traversal()

print("\nRight to Left Traversal of the XOR Linked List")
ll.RL_traversal()
```

Output

```Left to Right Traversal of the XOR Linked List
5 1 3 2
Right to Left Traversal of the XOR Linked List
2 3 1 5
Deleted Value: 5
Deleted Value: 1
Left to Right Traversal of the XOR Linked List
3 2
Right to Left Traversal of the XOR Linked List
2 3
```

Back to: Data Structure > Data Structure - Linked List