GeeCON Prague 2014*
The moose likes Programming Diversions and the fly likes doubly linked list using one reference Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "doubly linked list using one reference" Watch "doubly linked list using one reference" New topic
Author

doubly linked list using one reference

sam liya
Ranch Hand

Joined: Nov 25, 2008
Posts: 1161
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

Joined: Aug 31, 2004
Posts: 11343



"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11354
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 562
    
    7

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
Bartender

Joined: Oct 14, 2005
Posts: 18570
    
    8



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

Joined: Aug 31, 2004
Posts: 11343

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

Joined: May 13, 2004
Posts: 86
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'


http://javasign.blogspot.com/
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39079
    
  23
Now now. Let aruna sameera explain what the thread means.
sam liya
Ranch Hand

Joined: Nov 25, 2008
Posts: 1161
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

Joined: Mar 05, 2008
Posts: 3016
    
  10
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

Joined: Jan 10, 2002
Posts: 61315
    
  66

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


[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3016
    
  10
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

Joined: Jan 10, 2002
Posts: 61315
    
  66

That is exactly what I am referring to.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18876
    
  40

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

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 562
    
    7

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

Joined: May 26, 2007
Posts: 375
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! )


Gabriel
Software Surgeon
 
GeeCON Prague 2014
 
subject: doubly linked list using one reference