Day #6: XOR Doubly Linked List

Day #6: XOR Doubly Linked List

Hello. Today is the Day 6 of the #100DaysOfCodeChallenge. Received a problem previously asked by Google with a hard tag to it.

The Question On Day #6:

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.

Doing it on C++, since pointer implementation on Python is messy and not efficient.

Algorithm

  • The main logic behind the question is to understand the properties of XOR.
  • Refer wiki.

C++ Code

Output

Nodes: 
40 30 20 10 

Explanation

Not getting much into the details of the logic, the wikipedia reference speaks it all.

You can look into the visualiser to understand the BTS of the logic here.

Feel free to reach out for any query clearance.

Thanks and cheers:)