Daily Coding Problem: Problem #6

Problem

This problem was asked by Google.

An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, 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 get_pointer and dereference_pointer functions that converts between nodes and memory addresses.

Solution

Let’s understand the problem. Instead of using our traditional next and prev variables to store the next and previous node’s address, we will use a both pointer which stores the XOR of the next and previous node’s address. Might be a little confusing, let’s visualize with an example

A ←→ B ←→ C ←→ D

A.both contains B
B.both contains A^C
C.both contains B^D
D.both contains C

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.

import ctypes


def _get_obj(id):
return ctypes.cast(id, ctypes.py_object).value


class Node:

def __init__(self, val):
self.val = val
self.both = 0


class XORLinkedList:

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

def add(self, element):
node = Node(element)
if self.head is None:
self.head = self.tail = node
else:
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
if next:
prev = id(head)
head = _get_obj(next)
return head.val


xor_ll = XORLinkedList()
xor_ll.add('1')
xor_ll.add('2')
xor_ll.add('3')

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!.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store