This week's book giveaways are in the Java EE and JavaScript forums.
We're giving away four copies each of The Java EE 7 Tutorial Volume 1 or Volume 2(winners choice) and jQuery UI in Action and have the authors on-line!
See this thread and this one for details.
The moose likes Java in General and the fly likes Linked List Question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Linked List Question" Watch "Linked List Question" New topic
Author

Linked List Question

Shunjie Liu
Greenhorn

Joined: Feb 21, 2006
Posts: 7
Hi, I donno if this is the right place to post such a message as its not really java related but more of from a development stand. Sorry if its the wrong place to ask though

I am developing a Linked List class that handles a list however, there is a potential (in fact almost a certainty) that the nodes could call to itself and cause an endless loop if running through the it. Any suggestion on how to handle such a case ?

Thank you : hope its not too much for a first post
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
Could you post the code to show what you mean?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

I am developing a Linked List class that handles a list...
My suggestion would be to stop doing that. Java already provides a class named java.util.LinkedList that handles a list, and it's guaranteed that you can't twist it into a loop because its API doesn't allow that.
Rusty Shackleford
Ranch Hand

Joined: Jan 03, 2006
Posts: 490
No, learning how a linked list(and other data structures) work is far more beneficial then just learning the API. Learning how things work gets you closer to be a useful, valuable programmer.

As was suggested, posting code would be very helpful.


"Computer science is no more about computers than astronomy is about telescopes" - Edsger Dijkstra
Shunjie Liu
Greenhorn

Joined: Feb 21, 2006
Posts: 7
I have not done any coding yet as I am still trying to figure out a solution.
Basically, what happened is that for a Linked List of Nodes
A-B-C-D-E-F where each letter is a node.
and F points back to D. This would cause an infinite loop if we run through the List

so my question is how can we handle a looping Linked List of nodes ? I know that java's linked list would not have such a problem but I am interested to know how to deal with it if such a problem crops up ?

Example

So it now points to the first Element and causes an endless loop.
Note that this is not the java's implementation of Linked List but my own.
My question how can we handle such a case problem given a list of Nodes thats already looped and we cannot change the elements in the Nodes
Joni Salonen
Ranch Hand

Joined: Jan 07, 2006
Posts: 53
What kind of an object does your getFirst() return?

My question how can we handle such a case problem given a list of Nodes thats already looped and we cannot change the elements in the Nodes


That depends on the operations you wish to perform. If you wish to go through all nodes there are two algorithms: breadth first and depth first search. They both rely on maintaining a list of nodes (a queue in one case, a stack in the other) that you have already processed.
Shunjie Liu
Greenhorn

Joined: Feb 21, 2006
Posts: 7
It turn out to be kind of a brain teaser but I think I have solved the looped linked list problem for now. dunno if it will work but thanks still.

Thanks Rusty Shackleford for the encouragement not forgetting those friendly dudes who helped
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Originally posted by Rusty Shackleford:
No, learning how a linked list(and other data structures) work is far more beneficial then just learning the API. Learning how things work gets you closer to be a useful, valuable programmer.
That seems to be a common attitude, but I haven't observed it to be true myself. It might be true if you're programming in a language where you have to do that sort of thing all the time, like C, but Java is not one of those languages. I've been programming Java for several years and I have never needed to even use a linked list, let alone write my own.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Linked List Question