Finding Nth last number in a Singly Linked List in Java

[proggR]

I need to find the Nth last number in a Singly Linked List in Java. I'm not using the LinkedList Class I'm making my own and implementing Collections. I need to find an efficient way to essentially count backwards N links and isolate just that link. I have a few ways of doing it already but none seem all that efficient when you think about if you had millions of records. The List is linked via nextLink only and doesn't have a previousLink. It also needs to use a foreach loop.

Its just a little puzzle I've been assigned and I wanted to see if anyone has any more efficient methods.

So far my thoughts are either, reverse the list, foreach through until you've reached the Nth iteration, isolate the object, reverse the list again. But if you're working with millions of links thats burdensome. Another method could be to create a temporary second linked list that will only ever have N number of links, removing the first until the end is reached and then isolating the first because it will contain the Nth from last link. However if they want the 900,000th last then you're going to have a very large second list, which I suppose isn't too bad because its temporary but it still seems to be lacking in efficiency.

Anyhelp would be appreciated. I'll keep Googling in the mean time.

[Daniel0]

If you have to need to select the nth element, why not choose a data structure that has O(1) access time like an array or hash table instead of a linked list which takes O(n)? If you just want to be able to move backwards, then use a doubly linked list.

 

Just remember that finding the 998th last element in for instance a 1000 element list is the same as finding the 2nd element. For the general problem, it makes no difference if you go forwards or backwards. Worst case will always be that you have to go through all the elements.

 

Maybe if you tell what you need the data for, we'll be able to help you better.

[proggR]

I realize there's better data structures for it. I've been asked to used a singly linked list and cycle backwards through it though. I think its mainly to see what I (and a co-worker) can come up with to show our aptitude with Java.

Another kicker is that we can't know the size of the list. Otherwise, like you said, it would be an easy solution.

 

[proggR]

public E findNthLast(int nth) {
	int ctr = 0, ctr2 = 0;
	E solution = null;
	for (E item : list) {
		ctr++;
		if (ctr > nth) {
			ctr2++;
		}
	}
	solution = list.get(ctr2 - 1);
	return solution;
}

 

This just needs some way to check if N is larger than the size of the list and it should be the most efficient way. Most efficient I can think of anyway.

Although I suppose I could initialize ctr2 to -1 and then I don't need the ctr2-1 as the index and I can check if its still -1 and it would know it was larger than the size.