Couple of questions about XOR linked lists...

klawson88 · 04-19-2009, 11:13 AM

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.

MK27 · 04-19-2009, 12:17 PM

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).

klawson88 · 04-19-2009, 03:17 PM

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?

MK27 · 04-19-2009, 04:00 PM

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.

klawson88 · 04-19-2009, 04:24 PM

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?

cas · 04-19-2009, 04:55 PM

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.

04-19-2009, 11:13 AM	#1
klawson88 Registered User Join Date: Apr 2009 Posts: 8	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.
klawson88 is offline

04-19-2009, 03:17 PM	#3
klawson88 Registered User Join Date: Apr 2009 Posts: 8	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?
klawson88 is offline

04-19-2009, 04:24 PM	#5
klawson88 Registered User Join Date: Apr 2009 Posts: 8	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?
klawson88 is offline

04-19-2009, 04:55 PM	#6
cas Registered User Join Date: Sep 2007 Posts: 446	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.
cas is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
a couple of questions about System.String	Elkvis	C# Programming	5	02-17-2009 02:48 PM
A couple of Basic questions	ozumsafa	C Programming	8	09-26-2007 04:06 PM
Couple of Questions	toonlover	Windows Programming	10	07-14-2006 01:04 AM
New to C++/ Couple of questions...	danielthomas3	C++ Programming	13	04-14-2002 03:46 PM
couple questions for newb	bluehead	C++ Programming	10	11-24-2001 03:32 AM