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:)