ArrayList vs LinkedList efficiency

Question

I have a problem which uses many insertions in the list at the beginning and afterwards search and retrieval operations are extensively used, So which approach is good and efficient?

Approach 1: Use LinkedList as my data structure for the whole program.

Approach 2: Use ArrayList as my data structure for the whole program.

Approach 3: Use LinkedList as my data structure at the beginning for insertion and do Arraylist al = new Arraylist(ll); for retrieval operations.

How much does the changing of data structure cost?? Is it actually worth doing it?

Answer 1

Since they both implement the same interface you can find this out for yourself by writing your code so that the constructor can be plugged in and test your code both ways. Benchmarking can be done with jmh.

You can plug in the constructor by using the Supplier interface.

Depending on the nature of your problem you may find that using a Deque is appropriate.

Answer 2

Allow me to suggest a 4th approach: using ArrayDeque for the whole program. It has efficient insertion at the front and the back (possibly even faster then LinkedList) and search efficiency like ArrayList. ArrayDeque is an unfairly overlooked class in the Java Collections Framework, possibly because it was added later (Java 6, I think). It does not implement the List interface, so you will have to write your program specifically for it.

Other than that, the only two valid answers to your question are

1. Do not worry about efficiency until you absolutely have to.
2. If and when you have to worry about efficiency, you will have to make your own measurements of what performs satisfactorily on your data in your environment. No one here can tell you.

Answer 3

It depends on Frequencies of insert and retrieve operations. Here are the complexities:

• ArrayList -> Insertion in the beginning : O(n)
• ArrayList -> Retrieval based on index : O(1)
• LinkedList -> Insertion in the beginning : O(1)
• LinkedList -> Retrieval based on index : O(i) where i is number of elements to be scanned.

So, if you have more retrievals than insertions, go for ArrayList, if not, go for LinkedList.