• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

doubly linked list using one reference

 
Ranch Hand
Posts: 1325
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
 
lowercase baba
Posts: 13091
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 28264
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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'
 
Marshal
Posts: 79475
379
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Now now. Let aruna sameera explain what the thread means.
 
shawn peter
Ranch Hand
Posts: 1325
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Master Rancher
Posts: 4921
74
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Sheriff
Posts: 67749
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Master Rancher
Posts: 4921
74
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Sheriff
Posts: 67749
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That is exactly what I am referring to.
 
author
Posts: 23956
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

 
Ranch Hand
Posts: 376
Scala Monad
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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! )
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic