Skip to content
 

The XOR Linked List In C++

Background

It is possible to store the pointers in a linked list in such a way that they ‘overlap’ by using the logical XOR operator.  This allows a user to cut the memory footprint of a basic linked list by 50% at the expense of a couple extra CPU operations.  In today’s world this technique would generally not be used on a desktop or server system (without extreme requirements).  It is more suited towards embedded development on tiny microprocessors that may have a mere few kilobytes of precious ram when the XOR linked list happens to be the most memory efficient way to represent the data.

This implementation is based off the writeup on Wikipedia.  I have created a basic linked list class that supports inserting at the tail and removing from the head.  Intended usage is for this demo is non-duplicate pointers.

XOR is a very interesting logical operator that can be difficult to understand.  There is a bitwise operator refresher located here.  The basic rules are:

  • 0 ^ 0 = 0
  • A ^ 0 = A
  • A ^ A = 0
  • A ^ B = B ^ A
  • (A ^ B) ^ A = B
  • (B ^ A) ^ B = A

When we apply this, instead of having a ‘next’ and ‘prev’ like a normal linked list, we have one ‘NextPrev’ that holds the XOR of both the ‘next’ and ‘prev’.

  • NextPrev = Next ^ Prev
  • Next = NextPrev ^ Prev
  • Prev = NextPrev ^ Next

Based on the rules above, both head ( with Next as 0 ) and tail (with Prev as 0) maintain the actual pointer to the next object because XOR with zero leaves the original bits.  As a side effect the head and tail pointers are the only entry points.  If there is a pointer to an object in the middle of the list, there is no way to traverse from that object without knowing the actual next or previous item.  Another caveat is that debuggers will not be able to recognize the pointers in the list other than ‘head->prev’ and ‘tail->next’.

Implementation

This is the header file for the list.  The behavior of the list is:

  • If there are no entries head and tail are 0
  • If there is one entry, head is the entry and tail is 0
  • If there are 2 or more entries head and tail are both set as are the items m_NextPrev variable that holds both next and previous

DoubleLinkedXOR.h:

#ifndef __DOUBLELINKEDXOR_HEADER__
#define __DOUBLELINKEDXOR_HEADER__

template 
class DoubleLinkedXOR
{
public:
	DoubleLinkedXOR() { m_head = m_tail = 0;}
	~DoubleLinkedXOR(){}

	void AddToTail( T entry )
	{
		if( !m_head )//no items
		{
			entry->m_NextPrev = 0;
			m_head = entry;
		}
		else if( !m_tail ) //just head is set, one item in list
		{
			m_tail = entry;
			m_tail->m_NextPrev = m_head;
			m_head->m_NextPrev = m_tail;
		}
		else//two items or more, insert
		{
			entry->m_NextPrev = m_tail;
			m_tail->m_NextPrev = (T)((int)(m_tail->m_NextPrev) ^ (int)entry);
			m_tail = entry;
		}
	}
	T RemoveFromHead()
	{
		T item = m_head;

		if( !m_head )
		{
		    return 0;
		}
		else if( !m_tail )//just one item
		{
			m_head = 0;
			return item;
		}
		else if( m_head->m_NextPrev == m_tail
			&& m_tail->m_NextPrev == m_head ) // only two items
		{
			m_head = m_tail;
			m_tail = 0;
			m_head->m_NextPrev = 0;
			return item;
		}
		else
		{
			m_head = m_head->m_NextPrev;
			m_head->m_NextPrev = (T)((int)(m_head->m_NextPrev) ^(int) item);
			return item;
		}
	}
private:
	T m_tail;
	T m_head;
};
#endif

The only general requirements of the above template are that the type instantiated is a pointer to an object with a *m_NextPrev member of the same type.  Below is the test object used in the example.

Item.h:

#ifndef __ITEM_HEADER__
#define __ITEM_HEADER__

typedef struct _ITEM {
	int id;
	struct _ITEM *m_NextPrev;
} Item;

#endif

Below is the simple test app I whipped up for the proof of concept. It creates x number of items and removes them as a FIFO.

main.cpp:

#include <stdio.h>
#include <stdlib.h>

#include "Item.h"
#include "DoubleLinkedXOR.h"

int main( int argc, char *argv[] )
{
	DoubleLinkedXOR  *list = new DoubleLinkedXOR ();

	int x, count = 10;

	for( x = 0;  x < count; x++ ) //add all items to list
	{
		Item *newItem = (Item*)malloc(sizeof(Item));
		newItem->id = x;
		list->AddToTail(newItem);
		printf("Added item: %d\n\r", newItem->id);
	}

	for( x = 0; x < count; x++ )
	{
		Item *retrievedItem = list->RemoveFromHead();
		printf("Retrieved item: %d\n\r", retrievedItem->id);
		free(retrievedItem);
	}

	delete list;

	getchar();
	return 0;
}

And my output looks like this when count = 10:

Added item: 0
Added item: 1
Added item: 2
Added item: 3
Added item: 4
Added item: 5
Added item: 6
Added item: 7
Added item: 8
Added item: 9
Retrieved item: 0
Retrieved item: 1
Retrieved item: 2
Retrieved item: 3
Retrieved item: 4
Retrieved item: 5
Retrieved item: 6
Retrieved item: 7
Retrieved item: 8
Retrieved item: 9

The files are here.

2 Comments

  1. Shipra says:

    can you please explain why m_NextPrev has to be pointer of type Item ? Because technically it’s not pointing to that.

    • robert says:

      When there are only 1 or 2 items the pointers are exact. Only when the number grows beyond two are the pointers XOR’d. I cast them as an int although that is probably not best way since there is no official guarantee the pointers are the size of an int.

Leave a Reply