Couple of questions about XOR linked lists...

This is a discussion on Couple of questions about XOR linked lists... within the C Programming forums, part of the General Programming Boards category; Ok, I get the basic concept of an XOR linked list... but I have a couple of questions concerning manipulation ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    16

    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.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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:
    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).
    Last edited by MK27; 04-19-2009 at 12:21 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    16
    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?

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by klawson88 View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    16
    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?

  6. #6
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    957
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21