--

# Problem

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 ctypesdef _get_obj(id):    return ctypes.cast(id, ctypes.py_object).valueclass Node:    def __init__(self, val):        self.val = val        self.both = 0class 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.valxor_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! 😄