Table of Contents

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)) addr(next) = 0^(addr(B)) addr(next) = 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)) addr(next) = (addr(A)^ addr(A))^addr(C) addr(next) = 0^addr(C) addr(next) = 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) addr(next) = addr(B)^addr(B) Addr(next) = 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.

### Insert

It adds a node at the start of the **XOR linked list**. If the list is empty, it just creates a node with the given value, and the xor address value (**xadd**) is set to 0 since it is the only node. Otherwise, it creates a node with **xadd** value equal to the **XOR of 0 (NULL)** and the current head’s address. **xadd** value of the current head gets updated to the **XOR** of the address of the new node and the node’s address after the current head. Moreover, the new node becomes the head now.

### 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: def __init__(self, value, xadd=0): self.value = value #data self.xadd = xadd # XOR of the address of the previous node and address of the next node class XORLinkedlList: def __init__(self): self.head=None 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 self.head = Node(value) self.tail = self.head else: new_node = Node(value, 0^id(self.head)) #create new node with xadd value equal to address of the next node self.head.xadd = id(new_node)^self.head.xadd #update the xadd value of the current head to the XOR of addresses of previous and next nodes self.head = new_node #update the head self.nodes.append(self.head) #deletes an item from the beginning of the list def delete(self): if self.head: del_val = self.head.value next_node = 0^self.head.xadd #find the address of the next node if next_node: next_node = _ctypes.PyObj_FromPtr(next_node) #get the node placed at the given address next_node.xadd = id(self.head)^(next_node.xadd) #update the next node xadd value to the address of the node after that self.head = next_node #change the head else: self.head = None self.tail = None self.nodes.pop().value return del_val #print list items in the forward direction def LR_traversal(self): if self.head: curr_node = id(self.head) #get the address of the first 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 next = prev_node^(curr_node.xadd) #get the address of the next 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): if self.head: 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 next = prev_node^(curr_node.xadd) #get the address of the next node #update the current and previous nodes prev_node = id(curr_node) curr_node = next ll = XORLinkedlList() 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

Blog Hero