What to choose to implement deque?

Question

What would you rather choose to implement deque: HashSet or LinkedList. And could you state cons and pros for both please? Thank you.

Answer 1

A HashSet is not a Deque so you would have to use a LinkedList (which does implement Deque). The reason behind this is that HashSet is not an ordered data structure, and hence cannot be used as a queue.

For thread-safe blocking implementations of Deque consider LinkedBlockingDeque or ArrayDeque.

Answer 2

Of course LinkedList. All Dequeue operations there are implemented strictly as O(1) and no excessive memory is used.

Answer 3

HashSet is not an alternative, because a set does not record the order in which the element was added. Additionally, a set does not allow the same element to be added more than once.

LinkedList is a better option or why not using an existing Deque implementation?