XOR linked list

XOR Linked Lists are Memory Efficient execution of Doubly Linked Lists. A common Doubly Linked List requires space for two location fields to store the addresses of past and next nodes. A memory effective rendition of Doubly Linked List can be made utilizing just one space for address field with each node. This memory Efficient Doubly Linked List is called XOR Linked List or Memory Efficient as the rundown utilizes bitwise XOR operation to spare space for one location.

          

In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.


in double linked list:

Node A: prev = NULL, next = add(B) // previous is NULL and next is address of B

Node B: prev = add(A), next = add(C) // previous is address of A and next is address of C

Node C: prev = add(B), next = add(D) // previous is address of B and next is address of D

Node D: prev = add(C), next = NULL // previous is address of C and next is NULL


in XOR List:

Node A:

0 XOR add(B) // bitwise XOR of zero and address of B

Node B:

add(A) XOR add(C) // bitwise XOR of address of A and address of C

Node C:

 add(B) XOR add(D) // bitwise XOR of address of B and address of D

Node D:

add(C) XOR 0 // bitwise XOR of address of C and 0


 XOR List traversal:

XOR Linked List can be traversed in both forward and reverse direction. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node’s address. For example, when we are at node C, we must have the address of B. The reason is simple: the address stored at C is “add(B) XOR add(D)”. If we do xor of “add(B) XOR add(D)” with add(B), we get the result as “add(B) XOR add(D) XOR add(B)” which is “add(D) XOR 0” which is “add(D)”. So we have the address of the next node. Similarly, we can traverse the list in a backward direction.



darkmode