XOR Linked List
/* Problem Statement :
* -------------------
* Implement a memory efficient Doubly Linked List
* which means you are allowed to use only one pointer
* to indicate both next and the previous pointers
*
* Soultion
* ---------
* The possible solution involves using a XOR Linked list compresses the same
* information in one address field by storing the bitwise XOR of the address
* for the previous and the address for next in one field.
* A B C D E ... <-> A⊕C <-> B⊕D <-> C⊕E <->
* When you traverse the list from left to right: supposing you are at C,
* you can take the address of the previous item, B,
* and XOR it with the value in the link field (B⊕D).
* You will then have the address for D and you can continue traversing the list.
* The same pattern applies in the other direction.
*
* Limitation:
* ------------
* 1. The list cannot be traversed from the middle unless we get the address of the previous element.
* 2. General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult.
* 3. The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive;
* 4. Most garbage collection schemes do not work with data structures that do not contain literal pointers;
* 5.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/* pointer stored the address of the node
* since address is a mere number, we can store it happily
*/
typedef unsigned long pointer;
struct link
{
pointer next_prev;
int payload;
};
typedef struct link link;
link* add_data(int payload, struct link* Prevlist)
{
struct link * new_link = (struct link*)malloc(sizeof(link));
assert(new_link);
/* Assigning the address of the previous element
* in the current NODEs pointer
*/
new_link->next_prev = (pointer)Prevlist;
new_link->payload = payload;
if (Prevlist != NULL)
{
/* If the previous Prevlist is not NULL, which means this is not the head
* then XOR the Prevlist's previous node address with this New NODEs address
* (ie) consider a list A<->B<->C<->D
* we are creating a new node C.
* B's next_prev would have A's address.
* so while creating C, update (B->next_prev = A ^ C)
*/
Prevlist->next_prev = (pointer) list->next_prev ^ (pointer)new_link;
}
return new_link;
}
void walk_list(link *list)
{
struct link* prev = 0;
while (list != NULL)
{
pointer next = ((pointer)prev) ^ list->next_prev;
printf("%d ", list->payload);
prev = (struct link*)list;
list = (link*)next;
}
printf("\n");
}
int main(void)
{
/* Add the elements in the linked list
* Remember you have to give the address of the previous node
* while adding the current node
*/
link *l1 = add_data(1, NULL);
link *l2 = add_data(2, l1);
link *l3 = add_data(3, l2);
link *l4 = add_data(4, l3);
link *l5 = add_data(5, l4);
/* Walk from the head */
walk_list(l1);
/* Walk from the tail */
walk_list(l5);
return 0;
}
Advertisement
