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.

After glancing at the wikipedia description of XOR linked lists I have no idea why you would want to actually do this, unless it's just an exercise, especially considering:

Quote:

---

XOR of pointers is not defined in some contexts (e.g., the C language), although many languages provide some kind of type conversion between pointers and integers;

---

The whole reason I started this post was to note that pointer addresses are numbers, you don't have to cast them that way, but I have never tried bitshifting them so maybe that is not allowed!

However you solve this problem, then, it will involve one more level of complication because you will have to convert the addresses before working on them (I guess a set of simple functions could do it). If typecasting fails, then you could memcopy the value into a long int (since on 64-bit the pointers are twice the size of an int).

Still, it seems crazy, but good luck (altho I'm of the opinion that a "prev" pointer can never be a real necessity anyway, if you plan everything right).

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?

Quote:

---

Originally Posted by klawson88

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

---

S/he surely meant an unsigned int pointer cast, since pointers are all the same size. Also, nextPrev is a pointer to start with, so:

Code:

---

(unsigned int*)list->tail->nextPrev

---

If you think about it, you will hopefully see how this could make a significant difference.

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.