Which list implementation is optimal for removing and inserting from the front and back?

Question

I am working on an algorithm that will store a small list of objects as a sublist of a larger set of objects. the objects are inherently ordered, so an ordered list is required.

The most common operations performed will be, in order of frequency:

1. retrieving the nth element from the list (for some arbitrary n)
2. inserting a single to the beginning or end of the list
3. removing the first or last n elements from the list (for some arbitrary n)

removing and inserting from the middle will never be done so there is no need to consider the efficiency of that.

My question is what implementation of List is most efficient for this use case in Java (i.e. LinkedList, ArrayList, Vector, etc)? Please defend your answer by explaining the implementation s of the different data structures so that I can make an informed decision.

Thanks.

NOTE

No, this is not a homework question. No, I do not have an army research assistants who can do the work for me.

Answer 1

Based on your first criteria (arbitrary access) you should use an ArrayList. ArrayLists (and arrays in general) provide lookup/retrieval in constant time. In contrast, it takes linear time to look up items in a LinkedList.

For ArrayLists, insertion or deletion at the end is free. It may also be with LinkedLists, but that would be an implementation-specific optimization (it's linear otherwise).

For ArrayLists, insertion or deletion at front requires linear time (with consistent reuse of space, these may become constant depending on implementation). LinkedList operations at front of list are constant.

The last two usage cases somewhat balance each other out, however your most common case definitely suggests array-based storage.

As far as basic implementation details: ArrayLists are basically just sequential sections of memory. If you know where the beginning is, you can just do a single addition to find the location of any element. Operations at the front are expensive because elements may have to be shifted to make room.

LinkedLists are disjoint in memory and consist of nodes linked to each other (with a reference to the first node). To find the nth node, you have to start at the first node and follow links until you reach the desired node. Operations at the front just require creating a node and updating your start pointer.

Answer 2

I vote for double linked list. http://docs.oracle.com/javase/6/docs/api/java/util/Deque.html