Forums Register Login

LinkedList Problem

+Pie Number of slices to send: Send
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.

Please help me
+Pie Number of slices to send: Send
Looks like an interview question, isnt?
Okie, so here is a possible way (pseudo code):
+Pie Number of slices to send: Send


can you please explain me , what is this result and start, start is index or value?
how i will get next

ya , this is a interview question
[ September 19, 2007: Message edited by: Gunjan Kumar ]
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
Thanks a lot for your reply.

I got the idea , but i have one more question, is it possible to do in JAVA
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
[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 ]
+Pie Number of slices to send: Send
I think Nitesh was looking for something like this:

+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
i appreciate the algorithm given by Ernest Friedman-Hill. it is also a good method to judge whether a linkedlist is a cycle linkedlist.
+Pie Number of slices to send: Send
 

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...
+Pie Number of slices to send: Send
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?
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
https://gardener-gift.com


reply
reply
This thread has been viewed 1833 times.
Similar Threads
Loose coupling : Avoid using implementation types like 'LinkedList'; use the interface instead
how to print objects from linked list?
How to remove an element from LinkedList while traversing
Convert LinkedList<Object> to LinkedList<T>
Value Of ice:datatable
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 29, 2024 03:41:42.