Printing partial list with time constraint

[StorLiten]

Background:

I have two lists: one list (list) contains elements of AnyType and one list (index) contains integers. The integers (in index) are sorted in ascending order!

Mission:

To print out the elements in list 'list' @ index given by list 'index'.

Example:

list = {I, really, love, to, hate, you}
index = {0, 1, 4, 5}

printPartial(list, index) will produce the output:

"I really hate you"

The catch:

1. This must work for "all" lists that implements the List interface.
2. This has to be done in O(N) regardless of which type of List (i.e. ArrayList or LinkedList).

Assumptions:

Both lists are of the same type.

public class PartialList<E> {

	public static <E> void printList(List<E> list, List<Integer> index) {
		if( list.size() < index.size() )
			System.out.println("meh, error or something...");

		if(list instanceof ArrayList<?>) {
			for(int i=0; i<index.size(); i++)
				System.out.println( list.get( index.get( i ) ) );
		}
		else {	 
			Iterator<Integer> itr = index.iterator();
			
			while(itr.hasNext())
				System.out.println( list.get( itr.next() ) );
		}
	}
}

For ArrayList, get() is O(1) and since I use a while-loop the program will be O(N) for ArrayLists.

Problem:

Getting O(N) for LinkedLists.

If I'm not mistaken itr.next() is O(1), so this doesn't pose a problem

However, list.get() is O(N) and the for-loop is O(N) for a total of O(N2)(squared).

How do I solve this? Or is it already solved since the integer-list (index) is sorted?

Thanks!

[SasseMan]

just iterate through the list and print the value when you have reached the index that is to be printed.

i = 0
n = 0
for each value in list
if i == index[n]
print list
n = n+1
end
i = i+1
end

this should work since the index list is sorted and should take O(N) w.r.t. list, not index.