Thread: Linked lists

How can i implement doubly linked lists using only one pointer value "np[x]" per item
instead of the usual two (next and prev). I am told to assume that all pointer values can be interpreted as k-bit integers. So, this has got to do with bit-wise operations.This has me totally stumped. Can anyone help me get started.

You don't. It's one of those incredibly stupid things they think are good home work assignments, which have no practical purpose.


Quzah.

@spoon! : thanks for that, will look into it
@quzah : yeah, I do agree with you. Only use I could think of is saving space in each node.

I've looked at the article, and I don't see how it's supposed to be useful:

To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one.

If I need two addresses to move a direction, why wouldn't I just use two pointers in my node? With this sort of list, you cannot start at a random node in the list, pick a direction, and go there, because you have to have two addresses in order to move. If all you have is a poitner to that node, you can't do anything! What's the point? The only way you can move through this list is to either start at the very first node, or the very last node. Otherwise, you can't navigate through it.

Furthermore, you have to know you're at the first or last node, or you can't move through it either, because you won't have the two pieces of information you're supposed to be XORing with.

They shouldn't call these XOR lists, they should call them "crippled linked lists". Half the space, half the functionality!


Quzah.