Linked List Question

[Shunjie Liu]

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]

Could you post the code to show what you mean?

[Paul Clapham]

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]

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]

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

    
 
LinkedList list = new LinkedList();
list.add("A");
list.add("B");
list.add("C");
list.add(list.getFirst());
 

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]

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]

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]

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.