Thread: xor linked list

I have to develop a linked list similar to one I found asked about on this site:

xor linked list

Mine has a twist though.

The function signatures include pointers to pointers for the head and tail, along with the integer number.

Here is my source.

Code:

                                                                     
                                                                     
                                                                     
                                             
#include <stdio.h>
#include "rndm.h"
#include <stdlib.h>

#define init_seed
#define set_range
#define SIZERANGE 100


typedef struct node
{
	int data;
	unsigned long link;
}node ;

node *head, *tail;


void insert(node **head,node **tail, int n)
{
	node *prev, *cur, *next, *tmp;
	node *newnode = malloc(sizeof(node));
	head = &cur;
	prev = NULL;	

	while(cur->data < n)
		{
                next = (node *)(cur->link ^ (unsigned long)prev);
                prev = cur;
                cur = next;
	}
	
	newnode->link ^= (unsigned long) prev ^(unsigned long) cur;
	prev->link ^= (unsigned long) cur ^ (unsigned long) newnode;
	cur->link ^= (unsigned long) prev ^ (unsigned long) newnode;

}//end insert

void delete(node **head, node **tail, int n)
{

}

void list(node *head)
{

}

main ()
{
	
	head=NULL;
	tail=head;
	int startRange, endRange, n,i;
	long inputSeed;
	printf("Seed: ");
	scanf("%l\n", &inputSeed);
	init_seed(inputSeed);

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

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

}

I am only working on the insert method at this time. I am kind of just code pushing for the declarations in that function, no really knowledge on what I should be doing. I am very confused with the **head and **tail variables.

Can someone kind of give me a push in the right direction concerning how this function should be operating and the variable declarations?

Thanks!

It should insert a node into your list, with the given integer as the value. Presumably you are keeping your list sorted? If so, then you need to walk the list to find where it belongs and insert it there.

Originally Posted by tabstop

It should insert a node into your list, with the given integer as the value. Presumably you are keeping your list sorted? If so, then you need to walk the list to find where it belongs and insert it there.

I'm just struggling on how to handle the pointers.

Originally Posted by ollie88r

I'm just struggling on how to handle the pointers.

You say that as though it means something. They're the head and tail of your list, passed in by pointer so that you can change them should you need to (if the new item ends up in the first/last position).

Originally Posted by tabstop

You say that as though it means something. They're the head and tail of your list, passed in by pointer so that you can change them should you need to (if the new item ends up in the first/last position).

Well for instance

head is **head. and i need to set that to cur, which is also a pointer

I am having trouble figuring out how to pass that variable correctly.

I just tried *cur = *head inside my insert method, and the NULL passed correctly to cur.

I am just confused because head has 2 dereferences and I dont know how to handle that for assignments to other points. I am often getting segmentation errors

Originally Posted by ollie88r

Well for instance

head is **head. and i need to set that to cur, which is also a pointer

I am having trouble figuring out how to pass that variable correctly.

I just tried *cur = *head inside my insert method, and the NULL passed correctly to cur.

I am just confused because head has 2 dereferences and I dont know how to handle that for assignments to other points. I am often getting segmentation errors

*cur = *head looks really wrong here. head is a pointer to a pointer to the head of the list; therefore *head is a pointer to the first element of the list; therefore **head is the first element of the list.

Originally Posted by tabstop

*cur = *head looks really wrong here. head is a pointer to a pointer to the head of the list; therefore *head is a pointer to the first element of the list; therefore **head is the first element of the list.

So I want cur to be pointing to the first node in the list, which is **head.

so node *cur = **head

?

that gives me an incompatible types error

If you want cur to point at the first node of the list, then you do exactly that

Code:

cur = *head;

by setting the value of cur to be the thing that points at the first node of the list.

You cannot possibly want head = 2. 2 is not a valid pointer. (Well, I mean I suppose it is; but you don't own the memory where it points.)

You shouldn't, ever, put data directly in head. That's not what it is for. It is to point at the (already existing) element of the list that is in front. When, in the course of inserting events, you find yourself inserting an element into first position, you will then need to change head to point at that new element.

ok so after your advice and some fidgetting, i still havent managed to figure out what to do with the head. not sure if i am any closer though

Code:

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

        while(newnode->data < cur->data)
        {
                next = (node *)(cur->link ^ (unsigned long)prev);
                prev = cur;
                cur = next;
        }

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




}//end insert

in my main i added

Code:

cur = malloc(sizeof(node));
        cur->data = 0;

so that i had a base case to build the organized list off of.

I get segmentation errors when adding the

Code:

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

part. im assuming this has something to do with initializing but i am not sure

So that's pretty horrendous, as insert functions go. You must be prepared for (1) an empty list (2) the new element to go at the front of the list (3) the new element to go at the end of the list.

Originally Posted by tabstop

So that's pretty horrendous, as insert functions go. You must be prepared for (1) an empty list (2) the new element to go at the front of the list (3) the new element to go at the end of the list.

Well I know its horrendous :/

That's why I'm here...don't really know what im doing.

And my insert is no where near done I know that. Just kinda posting it to see if I am heading in the right direction.