As we all can depict from the below figure that doubly LinkedList requires two link fields in order to store the address of the next node and the address of the right node Right? So XOR Linked list Typically acts as Doubly LinkedList. Each node of XOR Linked List requires only a single pointer field which doesn’t actually store the actual memory address but stores the Bitwise XOR of the address of its next and previous nodes. This leads to memory saving.
Read this first – XOR Linked List – A Memory Efficient Doubly Linked List. Now wondering about how the node of XOR LinkedList looks like. Below is the image of how it looks like:
Now we are done with the representation of doubly Linked List. You would be wondering whether it is possible to implement in java ?.
The answer to this is very simple and conclusive that one can not implement XOR linked list in a programming language such as java because of the presence of pointers in C++ and absence here in java language. In Java XOR doubly linked list is not possible because what happens is you don’t have access to the actual memory address of any object and the Garbage collector will remove such nodes if there is no variable referring to them. This is also the same in the case of C#.
Your doubly linked list class which uses this node class will keep track of the last node when iterating through the list. Similarly, you can also traverse backwards by doing an XOR of the next node’s address and the current node’s XOR Pointer. While we store only one previous node at a time instead of the previous node for every node, we save a considerable amount of memory. As we all know the memory is cheap nowadays so the concept of XOR doubly LinkedList is just theoretical, and it has no practical application.
If we need to take the XOR of two addresses we need to cast the memory address into integers which is not possible in java. But in C++ we can typecast any pointer that is (Node*), (int *) to any data type, depending on your machine that is (4 for 32 bit) and (8 for 64 bit). long is used to handle pointers in C++ also uintptr_t is available. Since we cannot Implement this in java, but wait can we be not able to do this in any language? Yes we can in C/C++.
Conclusion: The answer to this query is cold frozen NO as we can implement XOR Linked List in C/C++ because of its amazing feature i.e pointers with which we can also implement in language such as C#.
