A warm Hello to all the readers!
In the last post, we talked about Doubly linked list. Now there is a variant of doubly linked list. This is originated in order to save the memory resource. A doubly linked list stores three elements. Two are the pointers to previous and next node in the list. Third is the actual value of the element.
A doubly linked list looks like this:
We can see in above doubly linked list structure that each node takes 12 bytes of memory. This is simply because a node has to store pointers or memory addresses of two nodes separately. One previous and one next.
Therefore, in order to save the memory, XOR doubly linked list came into picture. Node still stores pointers of two nodes but inside a single memory location. This means addresses of previous and next nodes are XOR’ed and stored.
This version of the list is also called as memory efficient doubly linked list. Since it saves memory over standard doubly linked list.
