Thread: xor linked list

Well you've got walking the list down, except for the "falling off the cliff" part (what happens when you reach the end of the list?) I have no idea why "newnode" changed to "tmp" midway through your function.

Originally Posted by tabstop

Well you've got walking the list down, except for the "falling off the cliff" part (what happens when you reach the end of the list?) I have no idea why "newnode" changed to "tmp" midway through your function.

tmp is copied from my teachers powerpoint, guess i didnt make it to changing it yet :P

let me clarify my assignment

my teacher has provided me with a random number generator. we have to tell it to generate 100 numbers between 1 and 9999. this is done through a provided file i compile with mine.

so upon generating these 100 number, i have to put them in order with the insert method. so only on the first instance of running the insert method will my list be empty. and i do not believe i have to deal with falling off the end because the insert method is only called exactly 100 times.

so here is some crappy pseudo on how i think it should go

Code:

put random # in new node
check if new nodes data is greater than current nodes data
if it is, put new node between current node, and next node.
if its not, walk the list (with the while), till you find a node with data less than the data in the new node.

is there more to it than that?

Only if you never ever ever ever ever insert a number will you not have to deal with the empty list.

Only if the numbers come in reverse order will you never insert a number at the end of the list (if the first is 6, and the second is 8, guess what! That's the new end of the list!)

Code:

void insert(node **head,node **tail, int n)
{
        node *newnode;
        cur = *head;
        newnode = malloc(sizeof(node));
        newnode->data = n;
        while((cur != NULL) && (cur->data < newnode->data))
        {
                next = (node *)(cur->link ^ (unsigned long)prev);
                prev = cur;
                cur = next;
        }
        if(cur->data >= newnode->data)
        {

        }
        if(cur == NULL)
        {

        }


}//end insert

does that account for all possibilities?

http://imgur.com/qAy9U.jpg

can someone explain to me how this works?

i dont get how the prev->link and cur-link get their new numbers

Originally Posted by ollie88r

http://imgur.com/qAy9U.jpg

can someone explain to me how this works?

i dont get how the prev->link and cur-link get their new numbers

I'm assuming you can physically see the assignment statement, which is how prev->link and cur->link get their new numbers. If you don't understand why that gives you the right numbers, you should review what ^ means, and even better, what happens when you do something like x ^ y ^ y (i.e., ^ the same number twice).

Originally Posted by tabstop

I'm assuming you can physically see the assignment statement, which is how prev->link and cur->link get their new numbers. If you don't understand why that gives you the right numbers, you should review what ^ means, and even better, what happens when you do something like x ^ y ^ y (i.e., ^ the same number twice).

tmp->link = (unsigned long) prv ^ (unsigned long) cur;
prv->link ^= (unsigned long) cur ^ (unsigned long) tmp;
cur->link ^= (unsigned long) prv ^ (unsigned long) tmp;


temp->link = 2^3 (that i get)
prv->link ^= 3^5

which is

(1^3) ^= 3^5

so the 3's cancel out and it becomes 1^5

cur->link ^= 2^5

which is

2^4 ^= 2^5


so the 2s cancel out and it becomes 4^5

is this correct with the image i have attached?

Originally Posted by ollie88r

tmp->link = (unsigned long) prv ^ (unsigned long) cur;
prv->link ^= (unsigned long) cur ^ (unsigned long) tmp;
cur->link ^= (unsigned long) prv ^ (unsigned long) tmp;


temp->link = 2^3 (that i get)
prv->link ^= 3^5

which is

(1^3) ^= 3^5

so the 3's cancel out and it becomes 1^5

cur->link ^= 2^5

which is

2^4 ^= 2^5


so the 2s cancel out and it becomes 4^5

is this correct with the image i have attached?

That looks right.

Gah ive been staring at this code all day

here is what i got for my insert and main functions

Code:

void insert(node **head,node **tail, int n)
{
        node *cur = *head;
        node *prev = NULL;
        node *newnode = malloc(sizeof(node));
        newnode->data = n;

        while((cur != NULL) && (cur->data < newnode->data))
        {
                node *next = (node *)(cur->link ^ (unsigned long)prev);
                prev = cur;
                cur = next;
        }
        if(cur->data >= newnode->data)
        {
                // if previous is null, the list is empty
                if (prev == NULL)
                {
                        *head = newnode;
                }
                // if previous is not null, find the previous node to the previous node
                else
                {
                        node *prevb4prev = (node *) (prev->link ^ (unsigned long) cur);
                        prev->link ^= (unsigned long) prevb4prev ^ (unsigned long) newnode;

                }
        }
        if(head == NULL)
        {
                *head = newnode;
                (*head)->link = 0;
        }
        if(cur == NULL)
        {
                prev->link = prev->link ^ (unsigned long)newnode;
                newnode->link = (unsigned long)prev ^ (unsigned long)cur;
                *tail = newnode;
        }

        newnode->link = (unsigned long)prev ^ (unsigned long)cur;
        node *next = (node *) ((unsigned long)prev ^ cur-> link);
        cur->link ^= (unsigned long)newnode ^ (unsigned long)next;


}

int main()
{
        head = NULL;
        tail = head;
        float inputSeed= 0;
        int i, startRange, endRange;

        printf("Seed:");
        scanf("%f",&inputSeed);
        init_seed(inputSeed);

        printf("Range:");
        scanf("%d %d",&startRange,&endRange);
        set_range(startRange,endRange);

        for (i = 0; i < SIZERANGE; ++i )
        {
                insert( (node**)head, (node**) tail, rndm() );
        }
}

I believe my logic is pretty sound, but who knows. I am not getting any compiling errors. But I am getting a segmentation error. Im assuming its a pointer problem. Can you help me find it?

Thanks

So besides the fact that it is pointless and ancient, can someone help me find the memory error?