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!