Thread: Couple of questions about XOR linked lists...

Ok, I get the basic concept of an XOR linked list... but I have a couple of questions concerning manipulation of the list.

1. How would you remove the head or tail? I'm familiar with Java, so what I would do there (with a traditional linked list) is just set the head to the node right after it, and set that node's previous to null. But in C and XOR linked lists, the memory of the previous "head" is still being used, despite me re-assigning head to the node after, right?

How would I go about freeing the memory of that de-referenced node?

2. The XOR function in C, "^", uses numbers. The links in my XOR linked list are node structs, so I typecast them to integers in order to use the "^" function. VS gives me a warning after I compile: 'XORListNode *' differs in levels of indirection from 'int'

Can someone elaborate on what this means?

Thanks.

It's an HW assignment... and my professor told us to use the (unsigned int) typecast.

I'm just REALLY confused about what happens when I do the operation and how I can get a node from it.

So here's the definition of a node

Code:

struct node
{
	void *data;
	struct node *nextPrev;
}

Let's say I want to add something to the end of the list... with *tail being a pointer node declared already, and *list being a pointer XOR list also declared already

Code:

if(list->tail != NULL)
	{
		struct node *beforeTail;
		beforeTail = malloc(sizeof(struct node));
		beforeTail = (unsigned int)list->tail->nextPrev ^ 0;
		
	}

The problem is, i'm not sure the last line is right (even though it compiles). I know what comes out of the XOR operation is an unsigned int, but my professor says we should typecast that back to a node like so:

Code:

beforeTail =(node) ((unsigned int)list->tail->nextPrev ^ 0);

...which doens't compile. Neither does node*. So is my original line right?

Using that cast causes the code not to compile.... "error C2296: '^' : illegal, left operand has type 'unsigned int *' "

Ugh... why do I have a feeling that i'm missing something simple?

To perform the XOR operations, cast the pointers to your integral type (which in C99 should be uintptr_t; in C89 unsigned long is the best you can do. Either way it's bad code).

Ideally you'd make your "nextPrev" member integral because there's absolutely no reason at all to make it a pointer. If you need it to be a pointer, though, cast back to a pointer before storing the value.

So you have something like:

Code:

struct node *next, *prev; /* you got these from the XORed value */
unsigned long next_prev;
next_prev = (unsigned long)next ^ (unsigned long)prev;
/* or if next_prev has to be a pointer */
struct node *next_prev;
next_prev = (struct node *)((unsigned long)next ^ (unsigned long)prev);

You can break it down:

Code:

unsigned long prev_int = (unsigned long)prev;
unsigned long next_int = (unsigned long)next;
unsigned long next_prev = prev_int ^ next_int;
/* etc */

Either way, the XOR linked list is an essentially worthless data structure, and you'll have no need for it in real life.