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.

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