ArrayDeque Vs Linkedlist

ArrayDeque works by keep track of a head and tail pointers inside an ArrayList.

Which have the time complexity of $O(1)$ add for both head and tail

LinkedList is similar but for LinkedList, random access is costly. And thus could have performance hit.

We should use ArrayDeque in most case

Benchmarking showing that LinkedList is much slower comparing to ArrayDeque

When should we use linkedlist

ArrayDeque doesn't implement the List interface. So therefore bad for backward compatibility.

LinkedList implements both Deque and List