In this post, we will discuss about XOR linked list which is used to reduce memory requirements of a doubly linked lists using bitwise XOR operator.

We know that each node of a doubly linked list requires *two* pointer fields to store the addresses of its previous and next node. On the other hand, each node of XOR linked list requires only *single* pointer field which doesn’t store the actual memory addresses but stores the bitwise XOR of address for its previous and next node.

To illustrate, let’s consider the following doubly linked list.

Here the *link* field for equivalent XOR linked list stores the below values:

link(A) = NULL ^ addr(B) // bitwise XOR of NULL with address of node B

link(B) = addr(A) ^ addr(C) // bitwise XOR between address of node A and C

link(C) = addr(B) ^ addr(D) // bitwise XOR between address of node B and D

link(D) = addr(C) ^ NULL // bitwise XOR of address of node A with NULL

#### How this helps?

We know that XOR has below properties:

X^X = 0

X^0 = X

X^Y = Y^X

We can easily traverse the XOR linked list in either direction using above properties:

###### 1. Traversing the list from left to right:

For example, suppose we’re at node C, we can get address of node D as shown below.

= addr(B) ^ (addr(B) ^ addr(D))

= 0 ^ addr(D)

= addr(D)

The XOR operation cancels `addr(B)` appearing twice in the equation and all we are left with is the `addr(D)`. Similarly, to get address of first node A in the list, we can XOR the value in the link field with NULL.

= NULL ^ (NULL ^ addr(B))

= 0 ^ addr(B)

= addr(B)

###### 2. Traversing the list from right to left:

= NULL ^ (addr(C) ^ NULL)

= 0 ^ addr(C)

= addr(C)

For any middle node, say node C, we can get address of previous node B as

= addr(D) ^ (addr(B) ^ addr(D))

= 0 ^ addr(B)

= addr(B)

Consider below program which constructs a XOR linked list and traverses it in forward direction using properties of bitwise XOR operator. To traverse the complete list, we maintain three pointers prev, curr, and next to store the current node address, the previous node address and next node address respectively. Each iteration of the loop moves these pointers one position forward or backwards depending upon which direction we’re traversing the list.

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <stdio.h> #include <stdlib.h> #include <stdint.h> // Data structure for node of a XOR linked list struct Node { int data; struct Node* link; }; // Helper function to return XOR of x and y struct Node* XOR(struct Node *x, struct Node *y) { return (struct Node*)((uintptr_t)(x) ^ (uintptr_t)(y)); } // Helper function to traverse the list in forward direction void traverse(struct Node *head) { struct Node *curr = head; struct Node *prev = NULL; struct Node *next; while (curr != NULL) { printf("%d -> ", curr->data); // next node would be xor of address of previous node // and current node link next = XOR(prev, curr->link); // update prev and curr pointers for next iteration of the loop prev = curr; curr = next; } printf("NULL"); } // Helper function to insert a node in the beginning of the XOR linked list void push(struct Node **head, int data) { // allocate a new list node and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // The link field of the new node is XOR of current head and NULL // since new node is being inserted at the beginning newNode->link = XOR(*head, NULL); // update link value of current head node if linked list is not empty if (*head) { // *(head)->link is XOR of NULL and address of the next node // To get the address of next node, we XOR it with NULL (*head)->link = XOR(newNode, XOR((*head)->link, NULL)); } // update the head pointer *head = newNode; } // main function int main(void) { // input keys int keys[] = { 1, 2, 3, 4, 5 }; int n = sizeof(keys)/sizeof(keys[0]); struct Node *head = NULL; for (int i = n - 1; i >=0; i--) push(&head, keys[i]); traverse(head); return 0; } |

`Output:`

1 -> 2 -> 3 -> 4 -> 5 -> NULL

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <iostream> #include <vector> #include <cstdint> using namespace std; // Data structure for node of a XOR linked list struct Node { int data; Node* link; }; // Helper function to return XOR of x and y Node* XOR(Node *x, Node *y) { return (Node*)((uintptr_t)(x) ^ (uintptr_t)(y)); } // Helper function to traverse the list in forward direction void traverse(Node *head) { Node *curr = head; Node *prev = nullptr; Node *next; while (curr != nullptr) { cout << curr->data << " -> "; // next node would be xor of address of previous node // and current node link next = XOR(prev, curr->link); // update prev and curr pointers for next iteration of the loop prev = curr; curr = next; } cout << "nullptr"; } // Helper function to insert a node in the beginning of the XOR linked list void push(Node* &headRef, int data) { // allocate a new list node and set its data Node* newNode = new Node(); newNode->data = data; // The link field of the new node is XOR of current head and nullptr // since new node is being inserted at the beginning newNode->link = XOR(headRef, nullptr); // update link value of current head node if linked list is not empty if (headRef) { // headRef->link is XOR of nullptr and address of the next node // To get the address of next node, we XOR it with nullptr headRef->link = XOR(newNode, XOR(headRef->link, nullptr)); } // update the head pointer headRef = newNode; } // main function int main() { // input keys vector<int> keys = { 1, 2, 3, 4, 5 }; Node *head = nullptr; for (int i = keys.size() - 1; i >=0; i--) push(head, keys[i]); traverse(head); return 0; } |

`Output:`

1 -> 2 -> 3 -> 4 -> 5 -> nullptr

#### Drawbacks of XOR linked list:

A XOR linked list is simlar to a doubly linked list but not completely equivalent to a doubly linked list. There are several disadvantages of a XOR linked list over doubly linked list which are discussed below:

- A doubly linked list is easy to code and maintain but the code is little complex for a XOR linked list.

- XOR linked list is not supported by several languages such as Java where conversion between pointers and integers is undefined.

- If a pointer to an existing middle node in a XOR linked list is provided, we can’t delete that node from the list or insert a new node before or after it. On the other hand, this can be done easily with a doubly linked list.

**References:** XOR linked list – Wikipedia

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us^ Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply