Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Linked List Question

 
Shunjie Liu
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2409
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Could you post the code to show what you mean?
 
Paul Clapham
Sheriff
Posts: 21107
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 490
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Shunjie Liu
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 21107
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic