# Memory Efficient Doubly Linked List – Explanation and Implementation

The memory efficient doubly linked list, also known as XOR linked list is a modification of doubly linked list where each node is same as the node of a singly linked list.

Nodes of a doubly linked list contain an additional pointer overhead against a singly linked list. That’s the single most disadvantage of using doubly linked list.  Interestingly, even with the modification time efficiency is not compromised. This was presented by Prokash Sinha in a Linux Journal(2004).

### Node structure and Declaration

```struct node{
int data;
};
```

This xorLink represents both the previous and next node, computed by taking XOR.
XorLink is calculated as a Pointer to prev node ⊕ Pointer to next node.

### Implementation

So why XOR, as A ⊕ (A ⊕ B ) = 0 ⊕ B, in turns give B. This will help with finding the next of the current node. See the picture shown above, assuming the current node is at address 2000, to compute next node address the xorLink is XORed with previous node address.

(3000 ⊕ 2000) ⊕ 3000 = 0 ⊕ 2000 = 2000

which is the address of next node.

In the following implementation,

• a node is inserted at the beginning by calling the function insert(head) and
• deleted from the beginning by calling the function the delete(head).
• Function display(head) is for printing the list.
Since xor operation to the pointer is not allowed in c language, hence it is typecasted to unsigned int first and then, xor is taken.
See the code, details of working is mentioned in the comment section.
```#include<stdio.h>
#include<stdlib.h>

typedef struct node{
int data;
}Node;

Node *createNode(int data){
Node *p = (Node *)malloc(sizeof(Node));
p->data = data;
return p;
}

/* nodes are inserted at the beginning of linked list*/
Node * insert(Node *p, int data){

Node *nNode = createNode(data);

/* if this is the first node*/
if(!p){
p = nNode;
}
/* if this one is the second node*/
/* the new node added as beginning node will have no prev node, hence
* its link contain XORing of 0 with next node*/
nNode->xorLink = 0 ^ (unsigned int)p;
p->xorLink = (unsigned int)nNode ^ 0;
}
/* if this one is neither second or first node*/
else{
nNode->xorLink = 0 ^ (unsigned int)p;
/* every intermediate node will contain link as XORing of nodes prev
* and next to it*/
}

return nNode;
}

/* this will delete the node at the beginning of list*/
Node * delete(Node *p){

Node *temp;

if(!p)
printf("\nList underflow");

/* if there is only one node*/
free(p);
p = NULL;
}

else{
/* if the list contain two nodes only*/
temp = p;
}
/* list contain more than two nodes*/
else{
temp = p;
}
free(temp);
}

return p;
}

void display(Node *p){

struct node *temp = p, *prev = NULL, *next;

printf ("\nNodes of Linked List: ");

while (temp != NULL){
printf ("%d ", temp->data);

/* A XOR (A XOR B) gives B, this is used to compute next node address*/
next = (unsigned int)prev ^ (unsigned int)temp->xorLink;

prev = temp;
temp = next;
}
}
int main(void){

return 0;
}

```
```Output:-
Nodes of Linked List: 3 2 1
Nodes of Linked List: 2 1

```

It possesses running time complexity of doubly linked list and space complexity of singly linked list.