Ticker

6/recent/ticker-posts

XOR Linked List

 



XOR linked list is basically a memory efficient doubly linked list. in doubly linked list a node was containing 3 values that is pointer to previous node, actual value, pointer to next node.

In XOR linked list, a node is containing just 2 values that is actual value and address of previous and next node, seems same as DLL but its not, lets see-

NULL <-- [prev],actual_value,[next] <--> [prev],next_value,[next] --> NULL

this is the example of DLL, in this one node would contain 3 values, so for integer values it would require 12 bytes to store 1 node which is basically its not a memory efficient way.

This storage problem is solved by XOR linked list as it would store the address of previous                     and next node in a single block like this-


actual_value,[address(prev) XOR address(next)] <--> next_value,[address(prev) XOR    address(next)]


So this type of linked list would be more memory efficient and we also travel both forward and backward. in this type a node contains 2 values, so the size of the block is 8 bytes. for a large batch of data, this type of linked list is more preferred. for example- lets have a list of 3 elements - {2,3,5}

in XOR linked list- 

2,0 XOR 108   <-->   5,100 XOR 116   <-->   3,108 XOR 0

(address-   100                             108                                116  )


Here 100 is the address of the head node, 0 is the address of previous node as its the head node and 108 is the address of the next node. the rest of the nodes are just link the first one.


So this is all about the XOR linked list you all have to know.  Make sure to follow our Blog.   

Post a Comment

0 Comments