Is get(0) on java.util.List always O(1)?

Of my knowledge, there are the following implementations:

• ArrayList
• LinkedList
• Vector
• Stack

(based on http://tutorials.jenkov.com/java-collections/list.html pls correct if wrong)

ArrayList is a dynamic array implementation, so, as array, get is O(1), LinkedList has O(1) for get from Head, Vector and Stack are based on ArrayList, hence, O(1).

So in EVERY case get(0) on any built-in (cause you can make your own, for a specific purpose on making get(0) TS of O(n!)) implementation of List if O(1)?

> Is get(0) on java.util.List always O(1)?

Let us assume that there is a parameter N which stands for the length of the list¹.

For the 4 implementations of List that you mentioned, get(0) is indeed an O(1) operation:

• ArrayList, Vector and Stack all implement get(i) using array subscripting and that is an O(1) operation.

• LinkedList.get(i) involves i link traversals which is O(i). But if i is a constant, that reduces to O(1).

However there are other "built in" implementations of List. Indeed, there are a considerable number of them if you include the various non-public implementations, such as the List classes that implement sublists, unmodifiable lists, and so on. Generalizing from those 4 to "all of them" is not sound².

But get(0) won't be O(1) for all possible implementations of List.

• Consider a simple linked list where the elements are chained in the reverse order. Since get(0) needs to traverse to the end of the list, which is N link traversals: O(N).

• Consider a list that is fully populated from the rows in a database query's result set the first time that you attempt to retrieve a list element. The first get call will be at least O(N) because you are fetching N rows. (It could be worse than O(N) if the database query is not O(N).) So the worst case complexity for any call to get is O(N) ... or worse.

Indeed, with a some ingenuity, one could invent a custom list where get(0) has any Big-O complexity that you care to propose.

^{1 - I am being deliberately vague here. On the one hand, we need to identify a variable N denoting the "problem" size for complexity analysis to make sense. (The length of the list is the obvious choice.) On the other hand, the length of a List is a surprisingly "rubbery" concept when you consider all of the possible ways to implement the interface.}

^{2 - I assume that you are asking this question because you want to write some library code that relies on List.get(0) being O(1). Since you can't prevent someone from using your library with a non-builtin list implementation, your "assume it is builtin" constraint in your question doesn't really help ... even if we could check all possible (past, current or future) builtin List implementations for you.}

Ignoring custom implementations, and only looking at built-in implementations, like suggested at the end of the question, you still cannot say that get(0) will be O(1) regardless of list size.

As an example, calling get(0) on a sublist based on a LinkedList will be O(n):

List<Integer> list = new LinkedList<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
List<Integer> subList = list.subList(4, 8);
Integer num = subList.get(0); // <===== O(n), not O(1)

In that code, subList.get(0) internally calls list.get(4), which has O(n) time complexity.

Yes, for all implementations of List you mentioned get(0) is O(1).