I have a LinkedList, but dont know the size of this LinkedList. How do i know the 10th last element in one iteration.I have pointer for start position.
The solution i gave you is for a generic definition of the data structure linked list and not the java collection implementation. In a linked list, for every node there is a method to get the next element in the list. I think the interviewer does not intend to refer to the java implementation of the linked list. Also, the list should give a method to get the start of the list, this is what i meant by list.start.
Originally posted by Nitesh Kant: The solution i gave you is for a generic definition of the data structure linked list and not the java collection implementation. In a linked list, for every node there is a method to get the next element in the list. I think the interviewer does not intend to refer to the java implementation of the linked list. Also, the list should give a method to get the start of the list, this is what i meant by list.start.
Actually the list does not do that himself. Instead, he uses an Iterator.
Here's the basic way of using iterators:
It can also be used inside a for-loop, and is generic since Java 5.
Lists also have a listIterator() method, which returns an iterator that can also go back using the previous() method.
Lists also have a listIterator() method, which returns an iterator that can also go back using the previous() method.
The idea was not to go back. One should iterate just once and moving forward. If we can go back, we can just keep going forward and when the end is reached we go 10 steps back! Using java linked list, you have to use 2 iterators. One that keeps going and the other that stays on the start and move only after the first iterator has reached the 10th element.
[Nitesh]: Using java linked list, you have to use 2 iterators. One that keeps going and the other that stays on the start and move only after the first iterator has reached the 10th element.
Using a java.util.LinkedList, you don't have to use any iterators, because you do have access to a size() method. This question really makes no sense for a java.util.LinkedList, or for any java.util.List implementation. Just use size() and get().
If you're using JDK 6+, you can also use LinkedList's descendingIterator() method to get a single iterator that goes backwards from the end. You can also do something similar with a previous JDK using listIterator(list.size()), but that requires you to use size().
A more realistic Java-based version of this problem might be what to do with a ResultSet where you can only move forward, never backward. What's the most efficient way to get just the tenth-to-last result from such a ResultSet?
If the question is such a ResultSet, or about a more general kind of linked list (not a java.util.List), with no size() or listEterator(), then I still don't see how the algorithm Nitesh gave will work. It looks like the result variable will either equal the first element (if list size is < 10), or the last (if list size >= 10). It will never equal the tenth to last element, will it?
I would suggest creating a second list or array, which will never have more than ten elements. (The most efficient implementation might be circular buffer, but that's up to you.) Then:
[ September 19, 2007: Message edited by: Jim Yingst ]
Ernest Friedman-Hill
,
author and iconoclast
staff
This question really makes no sense for a java.util.LinkedList, or for any java.util.List implementation. Just use size() and get().
Absolutely i agree. This is what i told in my second comment.
I think the interviewer does not intend to refer to the java implementation of the linked list.
then I still don't see how the algorithm Nitesh gave will work. It looks like the result variable will either equal the first element (if list size is < 10),
Agree, the algorithm should throw an exception if the total no. of items are less than 10.
or the last (if list size >= 10).
Nope, since the result variable only moves one element at a time after the main iterator has iterated 10 elements, the difference between the result variable and the current element in the iterator will always be 10 elements. When the main iterator finishes, the result variable will be 10 nodes behind the end i.e. the 10th last node. The above algorithm iterates the list only once and does not create more data structures copying the same data as there in the list. Actually, the problem should have been:
How can you find the 10th last item in a *singly* linked list in one iteration without making additional data structures.
The code Ernest gave hits bulls-eye, that was what i was referring to when i talked about 2 iterators. Again, this question does not really make sense for a java collection implementation of linked list.
Ah, OK. I see now, thanks. However this doesn't really seem to square with your comment "One should iterate just once and moving forward." You're really iterating twice here in parallel - accessing the next element twice for each element except the last ten. I wasn't sure why you thought it was important to only iterate once, but I gave a common example where this might be meaningful - a forward-only ResultSet. Which wouldn't be amenable to your solution. Oh well. It was a vague, poorly-defined problem anyway. Depending what restrictions we choose to assume, there are several possible solutions, as seen.
Originally posted by song fresh: i appreciate the algorithm given by Ernest Friedman-Hill. it is also a good method to judge whether a linkedlist is a cycle linkedlist.
Well, you can't make cyclic java.util.LinkedLists...
absolutely right. i mean that it is a algorithm to solve that question. the pseydo code follows: //begin CycleLinkedList list = ....; //two references of CycleLikedList pointing to the start CycleLikedList list1 = list; CycleLikedList list2 = list; //body { list1 step 3 elements forward; list2 step 5 elements forward; if list1 chase up list2 then list is a cycle linkedlist; } //end
all right?
Post by:autobot
On my planet I'm considered quite beautiful. Thanks to the poetry in this tiny ad:
a bit of art, as a gift, the permaculture playing cards