This problem was asked by Google.
An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding
prevfields, it holds a field named
both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an
add(element)which adds the element to the end, and a
get(index)which returns the node at index.
If using a language that has no pointers (such as Python), you can assume you have access to
dereference_pointerfunctions that converts between nodes and memory addresses.
Let’s understand the problem. Instead of using our traditional
prev variables to store the next and previous node’s address, we will use a
both pointer which stores the XOR of the
previous node’s address. Might be a little confusing, let’s visualize with an example
A ←→ B ←→ C ←→ D
Now how do iterate through the list or how do we find the address of the next node since the current node’s both contains the XOR or previous and the next node. It turns out that it is quite simple. If we do XOR of the previous node’s both with the current node, we get the pointer to the next node. We can initialize the previous to be
0 . And XOR or anything with
0 is itself.
return ctypes.cast(id, ctypes.py_object).value
def __init__(self, val):
self.val = val
self.both = 0
self.head = self.tail = None
self.__nodes = 
def add(self, element):
node = Node(element)
if self.head is None:
self.head = self.tail = node
node.both = id(self.tail)
self.tail.both = id(node) ^ self.tail.both
self.tail = node
def get(self, index):
head = self.head
prev = 0
for i in range(index):
next = head.both ^ prev
prev = id(head)
head = _get_obj(next)
xor_ll = XORLinkedList()
assert xor_ll.get(0) == '1'
assert xor_ll.get(1) == '2'
assert xor_ll.get(2) == '3'
Time Complexity for
add : O(1)
Time Complexity for
get : O(n)
I hope you guys enjoyed this post.
If you find it helpful, please share and claps are much appreciated! 😄
Feel to ask your queries in the comments section!.