//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;
}
XOR linked lists
Author
Can someone help me? I know I'm inserting the nodes wrong.
Yeah, but it's extremely hard to follow. Just curious... are you sure you need to save this memory?
Author
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.
All I can say is saving what, 4 bytes, is not worth this hassle.
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
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
Quote:Original post by Daniel Miller
Yeah, 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]
Author
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;
unsigned long link;
};
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;
unsigned long link;
};
Quote:Original post by ELFanatic
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.
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.
Quote:Original post by Zahlman
And 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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
