Win a copy of The Little Book of Impediments (e-book only) this week in the Agile and Other Processes forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

doubly linked list using one reference

 
sam liya
Ranch Hand
Posts: 1243
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
fred rosenberger
lowercase baba
Bartender
Posts: 12265
36
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 605
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 21576
33
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 51419
87
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Now now. Let aruna sameera explain what the thread means.
 
sam liya
Ranch Hand
Posts: 1243
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Author and ninkuma
Marshal
Pie
Posts: 65337
97
IntelliJ IDE Java jQuery Mac Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Clever code" never impresses me. It's self-indulgent, smug, pointless and has no place in the production environment.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Author and ninkuma
Marshal
Pie
Posts: 65337
97
IntelliJ IDE Java jQuery Mac Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is exactly what I am referring to.
 
Henry Wong
author
Marshal
Pie
Posts: 22113
88
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 605
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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! )
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic