Thread: xor linked list

well i don't know what i should have....i can just traverse it but without printing out at every time i increment cur i won't have a list function!!!

i thought that:

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

was all i needed to make next pointer point to the next node!!

and then

prv = cur;

is just incrementing the prv pointer to where cur was...

then increments cur:

cur = next;


so what i am asking is how could i make the next pointer actually increment to the next node that is actually in the list???

should i do this???

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

okay so after a long night and no sleep i figured it all out...but i still have a problem with listing the numbers after i insert it...

Code:

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

#define MAX_NUMBERS 100

typedef struct _node{
        int data;
        unsigned long link;
} node;//end node

node *head, *tail;

void  insert(int insertNum){
        node *nekw, *next, *prv, *cur;
        nekw = malloc(sizeof(node));
        cur = head;
        prv = NULL;
        nekw->data = insertNum;

        while((cur != NULL) && (cur->data < nekw->data)){
                next = (node *)(cur->link^(unsigned long)prv);
                prv = cur;
                cur = next;
        }//end while loop

        if(next == NULL){
                next = nekw;
                tail = next;
                printf("this is the next thing in the list %d\n", tail->data);
        }//end if statement
        else if(((cur != NULL) && (next != NULL))&& (cur->data > nekw->data)){
                nekw->link = (unsigned long) prv ^ (unsigned long)cur;
                next = (node *)(cur->link ^ (unsigned long)prv);
                cur->link = ((unsigned long)nekw ^ (unsigned long)next);
                head = nekw;
        }//end else if statement
        else{
                cur = nekw;
                head = cur;
                printf("this is head %d\n", head->data);
        }//end else statement.
}//end insert.

void list(){
        int cnt = 1;
        node *cur, *prv, *next;
        cur = head;
        prv = NULL;
        printf("This is the list in ascending order: \n");
        printf("%2.1d", cur->data);//this will never print anything!!! even though cur->data = 1!!

        while((cur != NULL) && (++cnt < MAX_NUMBERS)){
                next = (node *)(cur->link^(unsigned long)prv);//this will always be null
                prv = cur, cur = next;
                printf("%2.1d", cur->data);//this is where it will error
                if(cnt % 10 == 0){
                        printf("\n");
                }//end if statement.
        }//end while loop
}//end list.

int main(){
        head = NULL;
        tail = head;
        int cnt;

        for(cnt = 1; cnt < MAX_NUMBERS; cnt++){
                insert(cnt);
        }//end for loop.

        list();
     
        return 0;
}//end main.

here is my ouput: it won't go to the next thing in the list...next thing will always be null!!! I checked my insert method over and over again...i found that i never set head the last time...so i made sure that tail and head are set perfect after every case...and still get the error...

Code:

This is the list in ascending order:
Segmentation fault

i found that i never set head the last time...so i made sure that tail and head are set perfect after every case...and still get the error...

I'm not so sure about that. It appears that head will always be NULL in your code above.

Also, change this:

Code:

node *nekw, *next, *prv, *cur;

to this:

Code:

node *nekw, *next = NULL, *prv, *cur;

Finally, your insert function appears to be overly complex. My insert function has seven basic statements.

okay i will try and see if next = null will help out...

Originally Posted by adramalech

okay i will try and see if next = null will help out...

You've got to do a heckuva lot more than that to fix your code. Unfortunately, IMHO, your code is not very elegant. But I tried to stay within the constraints of what you've already written and offer the following synopsis of a solution. And yes, I've already tested it to verify that it works.

First your insert function will need a static node for the previous record. It will be initialized to NULL. Then malloc space for the current record node structure. The link of this struct will be initialized with the address of the previous record. If this is the first record then the previous record will be NULL and link of the current record will be NULL. Then insertNum will be assigned to the data field of the current record. Next we determine if the previous record is not equal to NULL. If so, the previous link will be XOR'd with the address of the new record and the previous record and tail pointer will point to the current record. Otherwise, if the previous record is NULL, then the previous record will point to head which points to the current record.

Your list function will need a node pointer as a parm input. Either head or tail will be passed to your list function dependent up whether you want to display the records first to last of last to first.

In the list function you will need to define an unsigned long to keep track of the previous record. This unsigned long will be initialized to zero. Use a while loop to determine if the input is not equal to NULL. In the while loop, define an unsigned long to keep track of the next record. This unsigned long will be equal to the the previous record XOR'd with the what is in the link of the node pointer that was the input parm for the function. Now print what's in the node pointe data field. Next, we have to set the previous variable to the address of the node pointer input parm. And finally we have to set the input node pointer to next which was calculated above. Finally the while loop will break when the input node pointer is NULL

okay so i looked through my code and even further simplifed the insert function the delete function now takes care of all cases, and i also have go through and rewrote my list function to be able to list from head or tail!!!

i still have a problem and it originates with the insert method!!! i don't know how to make it work..somehow the link after the first node breaks, because when i go to traverse the list for the 2nd time i will still always get null!!! it will only output 1 number!!!!

Code:

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

typedef struct _node{
        int data;
        unsigned long link;
}node;//end node

node *head, *tail;
static int MAX_NUMBERS = 100;

void insert(int insertNum){
	node *nekw, *next, *prv, *cur;
	nekw = malloc(sizeof(node));
	cur = head;
	prv = NULL;
	nekw->data = insertNum;
	while((cur != NULL) && (cur->data < nekw->data)){
		next = (node *)(cur->link ^ (unsigned long) prv);
		prv = cur;
		cur = next;
	}//end while loop

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

	if(prv == NULL){
		head = nekw;
	}//end if statement
	else if(cur == NULL){
		tail = nekw;		
	}//end elseif statement.
	else{
		prv->link ^= (unsigned long)cur ^ (unsigned long)nekw;
		cur->link ^= (unsigned long)prv ^ (unsigned long)nekw;		
	}//end else statement.
}//end insert.

void delete(int deleteNum){
	node *cur, *prv, *next;
        cur = head;
        prv = NULL;
        while((cur != NULL) && (cur->data != deleteNum)){
		next = (node *)(cur->link^(unsigned long)prv);
		prv = cur, cur = next;
        }//end while loop
	
	next = (node *)(cur->link ^ (unsigned long) prv);
	
	if((cur == tail) && (cur->data == deleteNum)){
		free(cur);
		prv->link ^= (unsigned long) next;
		tail = prv;
	}//end if statement.
	else if((cur != head) &&(cur->data == deleteNum)){
		prv->link ^= (unsigned long) next;
		next->link ^= (unsigned long) prv;
		free(cur);
	}//end else if statement
	else{
		free(cur);
		next->link ^= (unsigned long) prv;
		head = next;
	}//end else statement
}//end delete.

void list(node *head){ 
        int cnt = 0;
	int x = 0;
	node *tmp, *tmpOne, *tmpTwo;
	tmp = head;
	tmpOne = NULL;
	printf("This is the list in acending order: \n");
	while(tmp != NULL){
		x = tmp->data;
		printf("&#37;d", x);
		tmpTwo = (node *)(tmp->link ^ (unsigned long)tmpOne);
		tmpOne = tmp;
		tmp = tmpTwo;
		if(++cnt % 10 == 0){
			printf("\n");
		}//end if statement.
      	}//end while loop
}//end list.

int main(){
        head = NULL;
        tail = head;
	int cnt;
	for(cnt = 1; cnt < MAX_NUMBERS; cnt++){
                insert(cnt);
        }//end for loop.
        list(head);
        return 0;
}//end main.

i still have a problem and it originates with the insert method!!! i don't know how to make it work

Code:

bool insert(int insertNum)
{
	node *prev = NULL, *next = NULL, *nekw = NULL, *prevB4prev = NULL;
	node *cur = head;
	if((nekw = (node *)malloc( sizeof(node))) == NULL)
	{
		printf("Malloc failed\n");
		return false;
	}
	nekw->data = insertNum;
	while ( (cur != NULL) && (cur->data < nekw->data) )
	{
		next = (node *) (cur->link ^ (unsigned long) prev);
		prev = cur;
		cur  = next;
	}
	if (head == NULL)
	{
		head = nekw;
		head->link = 0;
	}
	else if (cur == NULL)
	{
		prev->link = prev->link ^ (unsigned long) nekw;
		nekw->link = (unsigned long) prev ^ (unsigned long) cur;
		tail = nekw;
	}
	else if (cur->data >= nekw->data)
	{
		if (prev == NULL)
			head = nekw;
		else
		{
			prevB4prev = (node *) (prev->link ^ (unsigned long) cur);
			prev->link = (unsigned long) prevB4prev ^ (unsigned long) nekw;
		}
		nekw->link = (unsigned long) prev ^ (unsigned long) cur;
		next = (node *) ((unsigned long) prev ^ cur->link);
		cur->link = (unsigned long) nekw ^ (unsigned long) next;
	}
	return true;
}