Search code examples
javadequelinked-listarraydeque

Why is ArrayDeque better than LinkedList

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.

Solution

  • Linked structures are possibly the worst structure to iterate with a cache miss on each element. On top of it they consume way more memory.

    If you need add/remove of the both ends, ArrayDeque is significantly better than a linked list. Random access each element is also O(1) for a cyclic queue.

    The only better operation of a linked list is removing the current element during iteration.