This page looks best with JavaScript enabled

When use Dueque

 ·  ☕ 1 min read · 👀... views

Deque vs. LinkedList vs. Stack

Quote From javadoc:

ArrayDeque is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

Use ArrayDeque or LinkedList as queue1

Cons of Linked List

  • Linked structures are the worst structure to iterate with a cache miss on each element
  • Have to allocating a node for each item to insert, which essentially involves JVM/OS and expensive
  • For pop() operation, it mark internal nodes eligible for garbage collection and that’s more work behind the scene

Pros of Linked List

  • When removing the current element during iteration, LinkedList has better performance
  • Worth to note: LinkedList supports null element

When use ArrayDeque as queue

  • if only need to add/remove of both ends, use ArrayDeque
  • e.g.: when using BFS, consider ArrayDeque first.

Use ArrayDeque or Stack as Stack2

Deque exposes a set of operations which is all about being able to fetch/add/remove items from the start or end of a collection, iterate etc. There’s deliverately no way to access an element by position, which Stack exposes because it’s a subclass of Vector, making the Stack inconsistent.

Share on
Support the author with