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).

Read More – Doubly Linked List – Explanation and Implementation

Node structure and Declaration

struct node{
int data;
struct node xorLink;
};

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;
	struct node *xorLink;
}Node;

Node *createNode(int data){
	Node *p = (Node *)malloc(sizeof(Node));
	p->data = data;
	p->xorLink = NULL;
	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*/		
	else if(!p->xorLink){
	/* 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*/
		p->xorLink = (unsigned int)nNode ^ (unsigned int)(p->xorLink);
	}
		
	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*/
	else if(!p->xorLink){
		free(p);
		p = NULL;
	}
		
	else{
		/* if the list contain two nodes only*/
		if(p == p->xorLink->xorLink){
			temp = p;
			p = p->xorLink;
			p->xorLink = NULL;
		}
		/* list contain more than two nodes*/	
		else{
			temp = p;
			p = p->xorLink;
			p->xorLink = (unsigned int)p->xorLink ^ (unsigned int)temp;
		}
	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){
	
	Node *head = NULL;
	
	head = insert(head, 1);
	head = insert(head, 2);
	head = insert(head, 3);
	
	display(head);
	head = delete(head);
	display(head);
	
	return 0;
}

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

Advantages:

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

Disadvantages:

Even though, it’s memory consuming is optimized, but it has many disadvantages as well.

• A variable is maintained every time to remember the prev node(or next node) as computing from xorLink needs either of Prev or Next node address. That’s like an overhead.
• Maintenance is expensive, as it has complex code.
• XORing of pointers are not supported directly in some language.
• Debugging such program is difficult.
• Only few operation could be carried out with the same time efficiency that of doubly linked list.

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂

Recommended -