Day #6: XOR Doubly Linked List
1 min read
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
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.
- The main logic behind the question is to understand the properties of XOR.
- Refer wiki.
Nodes: 40 30 20 10
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:)