data-structures Tutorial => XOR Linked List

Example

A XOR Linked list is also called a Memory-Efficient Linked List. It is another form of a doubly linked list. This is highly dependent on the XOR logic gate and its properties.

Why is this called the Memory-Efficient Linked List?

This is called so because this uses less memory than a traditional doubly linked list.

Is this different from a Doubly Linked List?

Yes, it is.

A Doubly-Linked List is storing two pointers, which point at the next and the previous node. Basically, if you want to go back, you go to the address pointed by the back pointer. If you want to go forward, you go to the address pointed by the next pointer. It's like:

A Memory-Efficient Linked List, or namely the XOR Linked List is having only one pointer instead of two. This stores the previous address (addr (prev)) XOR (^) the next address (addr (next)). When you want to move to the next node, you do certain calculations, and find the address of the next node. This is the same for going to the previous node. It is like:

How does it work?

To understand how the linked list works, you need to know the properties of XOR (^):

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

Now let's leave this aside, and see what each node stores.

The first node, or the head, stores 0 ^ addr (next) as there is no previous node or address. It looks like this.

Then the second node stores addr (prev) ^ addr (next). It looks like this.

The tail of the list, does not have any next node, so it stores addr (prev) ^ 0. It looks like this.

Moving from Head to the next node

Let's say you are now at the first node, or at node A. Now you want to move at node B. This is the formula for doing so:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

So this would be:

addr (next) = addr (prev) ^ (0 ^ addr (next))

As this is the head, the previous address would simply be 0, so:

addr (next) = 0 ^ (0 ^ addr (next))

We can remove the parentheses:

addr (next) = 0 ^ 0 addr (next)

Using the none (2) property, we can say that 0 ^ 0 will always be 0:

addr (next) = 0 ^ addr (next)

Using the none (1) property, we can simplify it to:

addr (next) = addr (next)

You got the address of the next node!

Moving from a node to the next node

Now let's say we are in a middle node, which has a previous and next node.

Let's apply the formula:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Now substitute the values:

addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

Remove Parentheses:

addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

Using the none (2) property, we can simplify:

addr (next) = 0 ^ addr (next)

Using the none (1) property, we can simplify:

addr (next) = addr (next)

And you get it!

Moving from a node to the node you were in earlier

If you aren't understanding the title, it basically means that if you were at node X, and have now moved to node Y, you want to go back to the node visited earlier, or basically node X.

This isn't a cumbersome task. Remember that I had mentioned above, that you store the address you were at in a temporary variable. So the address of the node you want to visit, is lying in a variable:

addr (prev) = temp_addr

Moving from a node to the previous node

This isn't the same as mentioned above. I mean to say that, you were at node Z, now you are at node Y, and want to go to node X.

This is nearly same as moving from a node to the next node. Just that this is it's vice-versa. When you write a program, you will use the same steps as I had mentioned in the moving from one node to the next node, just that you are finding the earlier element in the list than finding the next element.

Example Code in C

/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
 
// Node structure of a memory efficient doubly linked list
struct node
{
    int data;
    struct node* npx;  /* XOR of next and previous node */
};
 
/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b)
{
    return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
 
/* Insert a node at the begining of the XORed linked list and makes the
   newly inserted node as head */
void insert(struct node **head_ref, int data)
{
    // Allocate memory for new node
    struct node *new_node  = (struct node *) malloc (sizeof (struct node) );
    new_node->data = data;
 
    /* Since new node is being inserted at the begining, npx of new node
       will always be XOR of current head and NULL */
    new_node->npx = XOR(*head_ref, NULL);
 
    /* If linked list is not empty, then npx of current head node will be XOR 
       of new node and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next. So if we do XOR of 
        // it with NULL, we get next
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }
 
    // Change head
    *head_ref = new_node;
}
 
// prints contents of doubly linked list in forward direction
void printList (struct node *head)
{
    struct node *curr = head;
    struct node *prev = NULL;
    struct node *next;
 
    printf ("Following are the nodes of Linked List: \n");
 
    while (curr != NULL)
    {
        // print current node
        printf ("%d ", curr->data);
 
        // get address of next node: curr->npx is next^prev, so curr->npx^prev
        // will be next^prev^prev which is next
        next = XOR (prev, curr->npx);
 
        // update prev and curr for next iteration
        prev = curr;
        curr = next;
    }
}
 
// Driver program to test above functions
int main ()
{
    /* Create following Doubly Linked List
       head-->40<-->30<-->20<-->10   */
    struct node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
 
    // print the created list
    printList (head);
 
    return (0);
}

The above code performs two basic functions: insertion and transversal.

Insertion: This is performed by the function insert. This inserts a new node at the beginning. When this function is called, it puts the new node as the head, and the previous head node as the second node.
Traversal: This is performed by the function printList. It simply goes through each node and prints out the value.

Note that XOR of pointers is not defined by C/C++ standard. So the above implementation may not work on all platforms.

References

Note that I have taken a lot of content from my own answer on main.

PDF - Download data-structures for free

Previous Next

data-structures

Fastest Entity Framework Extensions

Example

Why is this called the Memory-Efficient Linked List?

Is this different from a Doubly Linked List?

How does it work?

Example Code in C

References

Got any data-structures Question?

data-structures

data-structures Linked List XOR Linked List

Fastest Entity Framework Extensions

Example

Why is this called the Memory-Efficient Linked List?

Is this different from a Doubly Linked List?

How does it work?

Example Code in C

References

Got any data-structures Question?