## Recommended Posts

Can someone help me? I know I'm inserting the nodes wrong.
//prv is declared universally and initialized to NULL;
void insert(int data)
{
Node * tmp = (Node *)malloc(sizeof(Node));
tmp->data = data;

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


##### Share on other sites
wtf, is that a real method for doing linked lists?

##### Share on other sites
Yeah, but it's extremely hard to follow. Just curious... are you sure you need to save this memory?

##### Share on other sites
Well it's a homework assignment and teacher barely covered it. I've looked online for a site that teaches XOR linked lists and I can't find nothing. If I can just figure out how to insert I can finishe the rest of the assignment okay, I think.

All I can say is saving what, 4 bytes, is not worth this hassle.

##### Share on other sites
Yea, what a waste of time.

##### Share on other sites
well.... the point isn't to teach you a useful datastructure, but probably to figure out bitwise operations and memory allocation. It's a neat assignment IMHO.

I can't figure out your datastructure so I can't help you. It's homework so you'll just get hints or leading questions but you should post your List and Node class definitions.

use source tags ([] with source in the middle)

-me

##### Share on other sites
Quote:
 Original post by Daniel MillerYeah, but it's extremely hard to follow. Just curious... are you sure you need to save this memory?

Seconded. XOR linked lists are a fun little hack though [grin]

As for your code, each node link should store (prev ^ next), not (current ^ next).

I was going to include some code, but since it's for homework I'll leave it at that.

John B

[Edited by - JohnBSmall on March 7, 2007 12:25:50 PM]

##### Share on other sites
Well the homework isn't just insert.

But see, I don't get it. initially prv = nxt = NULL. so when I insert cur, I assign cur->link = (prv ^ nxt) which = NULL so cur->link = NULL. how does that work? does head = NULL or will it point to the first element?

I don't know how but I was talking to a classmate and he made it work with only a prv and a cur. So I went after that.

Definition for Node:

struct Node{
int data;
};

##### Share on other sites
Quote:
 Original post by ELFanaticWell it's a homework assignment and teacher barely covered it. I've looked online for a site that teaches XOR linked lists and I can't find nothing. If I can just figure out how to insert I can finishe the rest of the assignment okay, I think.All I can say is saving what, 4 bytes, is not worth this hassle.

Yeah, as others have said, it's a waste of time.

I mean your course, not the XOR method. But that too - when you care that much about memory, you probably should be using a dynamic array such as std::vector anyway. In fact, most C++ experts tell you to choose std::vector as your "default" container and a minority recommend std::deque instead. I've never, ever heard a knowledgeable C++ type person suggest that std::list be your first choice if you don't know any better.

And if you don't know what I'm talking about with all those std::things, your course is REALLY a waste of time.

Unfortunately, it seems like the majority of them are like this. Sorry.

##### Share on other sites
Quote:
 Original post by ZahlmanAnd if you don't know what I'm talking about with all those std::things, your course is REALLY a waste of time.

You know, as tempting as it is to agree with you about this, I think it's worth bearing in mind that "programming" as a subject covers a hell of a lot of things, and it might not be practical to teach good C++ techniques as part of that, or it might not be practical to teach the C++ standard libraries at any rate.

I think it's much more important to understand common programming structures and understand how the code you write actually maps to the machine architecture than it is to know details about any one language - even one as widely used as C++. I think it makes sense to teach using C for low-level work and something like Python, Java or C# for high-level work - C++ is very useful in industry because it provides access to both the high-level and the low level, but as a language it's full of traps and pitfalls, and I don't think that makes it a good language to base a course around. And of course, we don't even know what course ELFantastic is doing - it could be high-school level to first year university, and it could be intended to be highly vocational, or highly theoretical, and any combination of those implies different things about the what can be usefully taught.

Having said all that, teaching XOR linked lists is almost certainly pointless, and it does suggest a poorly structured course overall. If it's supposed to teach you about the properties of bitwise operators then there are far better ways to teach it, and if it's supposed to be useful in practice, then, well, that's just stupid.

And back on topic:
This forum has fairly strict rules about asking and answering homework questions, so I really can't be very explicit, but:
Maintain a pointer to the head of the list.
That pointer can be initialized to NULL.
When you add the first element, it's a special case, because it has nothing to link to yet.
Each time you add an element, you'll need to update the head pointer.
Each time you add an element, think about what all the current elements link fields contain to begin with, and think about what they need to contain after you've added the element.
Think about the structure as if it were a normal doubly linked list (so each element has a next and previous pointer), and think about the link field as being an encoded version of the next and previous fields, instead of meaningful data in its own right.

You'll probably have to maintain other data (ie, not just the head pointer) to implement operations other than insert, but if you understand how the XOR linked list trick works, then you should be able to work it out. Check the Wikipedia page as well.

John B

##### Share on other sites
Quote:
 Original post by ZahlmanAnd if you don't know what I'm talking about with all those std::things, your course is REALLY a waste of time.

Where did it say that he was learning C++?

jfl.

##### Share on other sites
Quote:
Original post by JohnBSmall
Quote:
 Original post by ZahlmanAnd if you don't know what I'm talking about with all those std::things, your course is REALLY a waste of time.

You know, as tempting as it is to agree with you about this, I think it's worth bearing in mind that "programming" as a subject covers a hell of a lot of things, and it might not be practical to teach good C++ techniques as part of that, or it might not be practical to teach the C++ standard libraries at any rate.

I think it's much more important to understand common programming structures and understand how the code you write actually maps to the machine architecture than it is to know details about any one language - even one as widely used as C++. I think it makes sense to teach using C for low-level work and something like Python, Java or C# for high-level work - C++ is very useful in industry because it provides access to both the high-level and the low level, but as a language it's full of traps and pitfalls, and I don't think that makes it a good language to base a course around. And of course, we don't even know what course ELFantastic is doing - it could be high-school level to first year university, and it could be intended to be highly vocational, or highly theoretical, and any combination of those implies different things about the what can be usefully taught.

Having said all that, teaching XOR linked lists is almost certainly pointless, and it does suggest a poorly structured course overall. If it's supposed to teach you about the properties of bitwise operators then there are far better ways to teach it, and if it's supposed to be useful in practice, then, well, that's just stupid.

And back on topic:
This forum has fairly strict rules about asking and answering homework questions, so I really can't be very explicit, but:
Maintain a pointer to the head of the list.
That pointer can be initialized to NULL.
When you add the first element, it's a special case, because it has nothing to link to yet.
Each time you add an element, you'll need to update the head pointer.
Each time you add an element, think about what all the current elements link fields contain to begin with, and think about what they need to contain after you've added the element.
Think about the structure as if it were a normal doubly linked list (so each element has a next and previous pointer), and think about the link field as being an encoded version of the next and previous fields, instead of meaningful data in its own right.

You'll probably have to maintain other data (ie, not just the head pointer) to implement operations other than insert, but if you understand how the XOR linked list trick works, then you should be able to work it out. Check the Wikipedia page as well.

John B

Yeah, it's the first insert that I think I'm having problems wtih. My teacher posted the actual code for inserting but I can't seem to figure out how to do so the first time. I'm going to ask my teacher tomorrow for the code and just turn it in late. I've never had problems with hw assignments before. I'm kinda going through some rough times though, or it could really be I met my match. I don't know. It's all weird thoguh.

##### Share on other sites

See, that wasn't too hard to find ;)

EDIT: Oh, and yes, the first insert is a special case, nicely explained by JohnBSmall.