### Memory Efficient Doubly Linked List

Memory Efficient Doubly Linked list :-

In doubly Linked list , each node store the address of its successor and predecessor. It is also called a two linked-list . We can navigate in both the directions in doubly linked list.

This make use of pointers and takes extra O(n) space for pointers.

*The Conventional structure of the linked list looks like :-*

*Struct node*

*{*

*Int info;*

*Struct node* next;*

*Struct node *prev;*

*}*

To avoid these , a memory efficient doubly linked list can be created using only one address space for every node. This is also called XOR Linked list.

The Structure of the Memory Efficient Doubly Linked list :-

Struct node { Int info; Struct node *ptr; }

The pointer ‘ptr’ is the difference between the previous pointer and the next pointer. It is calculated by exclusive -or operation.

Let us take an example and understand it.

The pointer_difference is defined as exclusive – OR of pointer to previous node to pointer to next node.

Note:- The pointer_difference of start node is the exclusive-or of Null and next node.

Representation:-

At node 5:- Ptr= 0 XOR address(10); At node 10 Ptr= 5 XOR address(4); At node 4 Ptr= 10 XOR address(8) ; At node 8 Ptr= 4 XOR address(10); At node 10 Ptr= 4 XOR Null;

### Advantage :-

Due to less overhead of pointers ,if we create a linked list of 10,000 nodes, the insertion takes place only in three seconds.

Traversal and deletion from any position takes approximately 1 second.

The memory is saved for these extra pointers.

References:-

https://www.linuxjournal.com/article/6828?page=0,0

https://en.wikipedia.org/wiki/XOR_linked_list

CommentsNo comment yet.