Tag Archives: Efficient linked list. Efficient Doubly Linked list

Memory Efficient doubly linked list in C

So far we have seen doubly linked list which have two pointers next and previous. but in efficient doubly linked list we will use only one pointer to move at next and previous nodes.

We know XOR  is used for bit recovery the same concept we will use here to store both the ptr (next and previous) information in single variable.

structure for efficient doubly linked list :

struct ednode{
int val;
struct ednode *ptr;

Suppose we have linked list of 4 nodes [ W | X | Y | Z ]

W->ptr= NULL ^ X

X->ptr= W ^ Y

Y->ptr= X ^ Z

Z->ptr= Y->NULL

To move at W from X 

(W^Y)^Y ==> which is (X->ptr^Y) ==> which is W

similar way to move at Y from X

(W^Y)^W ==> which is (X->ptr^W) ==> which is Y