Question: I am trying to to understand **why Java's ArrayDeque is better than Java's LinkedList** as they both implement Deque interface. 

I hardly see someone using ArrayDeque in their code. If someone sheds more light into how ArrayDeque is implemented, it would be helpful. 

If I understand it, I will be more confident using it. I could not clearly understand the JDK implementation as to the way it manages head and tail references.

Answer: 
I believe that the main performance bottleneck in `LinkedList` is the fact that whenever you push to any end of the deque, behind the scene the implementation allocates a new linked list node, which essentially involves JVM/OS, and that's expensive. Also, whenever you pop from any end, the internal nodes of `LinkedList` become eligible for garbage collection and that's more work behind the scene. 
Also, since the linked list nodes are allocated here and there, usage of CPU cache won't provide much benefit.

If it might be of interest, I have a proof that adding (appending) an element to `ArrayList` or `ArrayDeque` runs in amortized constant time; refer to [this](https://coderodde.wordpress.com/2015/08/01/keeping-vectors-efficient/).
All the people criticizing a `LinkedList`, think about every other guy that has been using `List` in Java probably uses `ArrayList` and an `LinkedList` most of the times because they have been before Java 6 and because those are the ones being taught as a start in most books.

But, that doesn't mean, I would blindly take `LinkedList`'s or `ArrayDeque`'s side. If you want to know, take a look at the below benchmark [done by Brian](https://web.archive.org/web/20191101213733/http://brianandstuff.com/2016/12/12/java-arraydeque-vs-linkedlist/) (archived).

The test setup considers:

> 
> * Each test object is a 500 character String. Each String is a different object in memory.
> * The size of the test array will be varied during the tests.
> * For each array size/Queue-implementation combination, 100 tests are run and average time-per-test is calculated.
> * Each tests consists of filling each queue with all objects, then removing them all.
> * Measure time in terms of milliseconds.
> 
> 
> 

Test Result:

> 
> * Below 10,000 elements, both LinkedList and ArrayDeque tests averaged at a sub 1 ms level.
> * As the sets of data get larger, the differences between the ArrayDeque and LinkedList average test time gets larger.
> * At the test size of 9,900,000 elements, the LinkedList approach took ~165% longer than the ArrayDeque approach.
> 
> 
> 

Graph:

[![enter image description here](https://i.stack.imgur.com/MUHdy.png)](https://i.stack.imgur.com/MUHdy.png)

**Takeaway:**

* If your requirement is storing 100 or 200 elements, it wouldn't make
much of a difference using either of the Queues.
* However, if you are developing on mobile, you may want to use an
`ArrayList` or `ArrayDeque` with a good guess of maximum capacity
that the list may be required to be because of strict memory constraint.
* A lot of code exists, written using a `LinkedList` so tread carefully when deciding to use a `ArrayDeque` especially because it **DOESN'T implement the `List` interface**(I think that's reason big enough). It may be that your codebase talks to the List interface extensively, most probably and you decide to jump in with an `ArrayDeque`. Using it for internal implementations might be a good idea...