Assuming I am using a single threaded application, can java.util.LinkedList have a loop? I see in the source code that Entry is a private inner class, so there is no way to tamper it. Just wondering, finding a loop in a linked is such a popular question for interviews. Nobody asks how to design a list to avoid having loops in the first place. Or am I misunderstanding something here?
2
-
What is a "loop" inside a list? I didn't understand what you are trying to ask. Did you mean a circular list?davidbuzatto– davidbuzatto2012-07-29 06:08:59 +00:00Commented Jul 29, 2012 at 6:08
-
Loop as in a later node in a singly linked list pointing to one of the earlier nodes.vikky.rk– vikky.rk2012-07-29 06:12:05 +00:00Commented Jul 29, 2012 at 6:12
Add a comment
|
3 Answers
You are right since j.u.LinkedList does not expose an api for creating lops it is not supported. Maybe with some reflection violence it might happen.
I think the question comes from a generation of c programmers with a standard library with no linked list, who would often roll their own. Also since there is no private modifier in C it is always possible to create a loop in a C linked list if you wanted to.
answered Jul 29, 2012 at 6:13
Esben Skov Pedersen
4,5072 gold badges36 silver badges49 bronze badges
1 Comment
vikky.rk
Yeah, that is what I thought so.
You can avoid loop in linked list by providing interface that is not exposing specific list implementation. That's what happens in Java. java.util.List is an interface and java.util.LinkedList is just one of implementations which really does not expose much outside of main List inteface.
Interviews or computer science classes are mostly interested in theoretical implementations of linked list where you can link nodes whichever way you are pleased.
So to answer your question: no you can't have a loop in java.util.LinkedList.
Comments
There might be a misunderstanding of sorts. There are many reasons why someone would asks an interview question. This sort of interview question is designed to see how well you would:
- understand the concepts of a linked list
- be able to consider mistakes in programming practice
- discuss Java implementation of the same
the third point is not as important in my mind, as you can obviously access the Java code if you need to understand how it has been implemented.
