aspose file tools*
The moose likes Java in General and the fly likes LinkedList Problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "LinkedList Problem" Watch "LinkedList Problem" New topic
Author

LinkedList Problem

Gunjan Kumar
Ranch Hand

Joined: Mar 26, 2007
Posts: 74
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


Gunjan Kumar
SCJP 1.5
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

Looks like an interview question, isnt?
Okie, so here is a possible way (pseudo code):


apigee, a better way to API!
Gunjan Kumar
Ranch Hand

Joined: Mar 26, 2007
Posts: 74


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 ]
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

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.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19783
    
  20

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Gunjan Kumar
Ranch Hand

Joined: Mar 26, 2007
Posts: 74
Thanks a lot for your reply.

I got the idea , but i have one more question, is it possible to do in JAVA
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

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.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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 ]

"I'm not back." - Bill Harding, Twister
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

I think Nitesh was looking for something like this:



[Jess in Action][AskingGoodQuestions]
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

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.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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.
song fresh
Greenhorn

Joined: Sep 19, 2007
Posts: 2
i appreciate the algorithm given by Ernest Friedman-Hill. it is also a good method to judge whether a linkedlist is a cycle linkedlist.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

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...
song fresh
Greenhorn

Joined: Sep 19, 2007
Posts: 2
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?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: LinkedList Problem