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