doubly linked list using one reference

[shawn peter]

can anyone tell me how to implement a doubly linked list using only one reference value?
this is actually not a java questions.but it is related to programming.so i think it is not problem?

[marc weber]

[fred rosenberger]

By definition, a doubly linked list has a reference to the NEXT node, and a reference to the PREVIOUS node. I don't see how having a single reference could POSSIBLY be called a doubly linked list.

see the wikipedia article.

[Steve Fahlbusch]

Unless the OP is refering to a circular double linked list - but even this is a stretch.

Please provide us with more information so that we can help you.

[Paul Clapham]

List referenceValue = new LinkedList();

In this example, LinkedList is a doubly linked list. Notice that I just used one reference value in my code.

But probably that wasn't what you meant. Like the others said, we need to know what you did mean.

[marc weber]

Steve Fahlbusch wrote:Unless the OP is refering to a circular double linked list - but even this is a stretch...

Right. I've thought about ways to "go backwards" using only "forward" references, and it can be done. But there's no way I would call that a "doubly linked" list.

[Aurelian Tutuianu]

marc weber wrote:Right. I've thought about ways to "go backwards" using only "forward" references, and it can be done. But there's no way I would call that a "doubly linked" list.

But you can call that 'single linked list with more than double effort to find something'

[Campbell Ritchie]

Now now. Let aruna sameera explain what the thread means.

[shawn peter]

normally doubly linked list have two references .
I need to implement a doubly linked list using one reference?how can i implement this?

here is the question what i need to solve?

Explain how to implement a doubly linked list using only one reference value instead of
the usual next and previous references.

[Mike Simmons]

Well, a quote of the question and an answer (sorta) can be found here. The answer given does not make any sense in Java, though it could work in other languages. However even in those other languages, it strikes me as a rather poor answer. The only way you can interpret the value at a particular node is if you already understand the links at the previous node. Which really defeats the purpose of a doubly linked list, doesn't it? If you can only understand the list by reading it from the beginning, you might as well just use a simple singly-linked list.

My guess is that the given answer is in fact the intended answer. Which is to say, it's not just a bad answer, but a bad question. I think someone came up with a mildly clever idea, did not realize that it was actually quite pointless, and then made a rather inane trivia question out of it. And now you have the misfortune of having this inane question inflicted on you. I would question the intelligence of whoever is asking this question of you. If that's your professor or a job interviewer, well, I guess you will need to find a more diplomatic way to put that. There are some places where a clever use of XOR is actually useful for something. However, this isn't one of them.

[Bear Bibeault]

"Clever code" never impresses me. It's self-indulgent, smug, pointless and has no place in the production environment.

[Mike Simmons]

Well, I think it's possible to have a clever solution to a particular problem, which is also worthy of praise. But I think that only really happens if you're putting the needs of the particular problem first, and looking for the best possible solution to that problem. Whereas if you start with [what you think is] a clever solution, and then try to invent a problem that leads to that solution... that's a recipe for disaster. The original poster's problem statement smells strongly of this latter possibility.

[Bear Bibeault]

That is exactly what I am referring to.

[Henry Wong]

However even in those other languages, it strikes me as a rather poor answer. The only way you can interpret the value at a particular node is if you already understand the links at the previous node. Which really defeats the purpose of a doubly linked list, doesn't it? If you can only understand the list by reading it from the beginning, you might as well just use a simple singly-linked list.

It's not quite as bad as that -- you just need to know the node that you arrived from. Meaning, if you just know a node, it is useless, you can't go anywhere.

However, if you know the node that you arrived from, then to go to the next node, just take the xor. And to turn around to the previous node, then use the node that you arrived from. In both cases, the current node becomes the new node that you arrived from.

Another interesting point is, you actually don't know the direction that you are moving in. Traversing backwards is done in the same way as traversing forward.


Interesting... but of course, totally not possible in Java.

Henry

[Steve Fahlbusch]

It also makes this useless in any automatic (or dynamic if you will) memory managed language.

Hey memory manager all of these objects no longer have any valid references you may remove these.

[Gabriel Claramunt]

I'm probably nitpicking, but the solution uses TWO references encoded in only one value. I still need to have the previous and next value.
(Only a C/C++ programmer could have come up with that monstrosity! )