Selecting the Best Java Collection Class for Your Application, Page 4
A deque (pronounced "deck") is a double-ended queue for which elements can be added to or removed from either end.
Classes that organize a collection as a deque implement the Deque interface. The methods defined in the Deque interface return immediately. This means that an attempt to remove an object from an empty deque fails either by returning null or throwing an exception, depending on which method is called. An attempt to add an object to a size-limited deque that is full fails either by returning false or throwing an exception.
Some classes that organize a collection as a deque implement a sub-interface of Deque named BlockingDeque. The BlockingDeque interface adds methods to Deque that may not return immediately if a queue is empty or full. The putFirst and putLast methods will wait to return or block until the queue is no longer full. The takeFirst and takeLast methods will block until the queue is no longer empty. There are also similar methods that will time out if they block for more than a specified amount of time.
If you have decided that a deque is the organization to use, here are suggestions regarding which class to use:
- ArrayDeque: The ArrayDeque class can be used to organize objects into a deque. The add and remove operations take a short amount of time that is independent of how many objects are in the deque. Deques based on the ArrayDeque class do not block.
The ArrayDeque class is often the best choice for managing a deque. However, in some cases, a LinkedList will be faster. If performance is important, experiment to see if LinkedList performs better in your application.
- LinkedList: The LinkedList class can be used to organize objects into a deque. The add and remove methods take a short amount of time that is independent of how many objects are in the queue. Deques based on the LinkedList class do not block.
- LinkedBlockingDeque: The LinkedBlockingDeque class can be used to organize objects into a queue. The LinkedBlockingDeque class has methods that block.
Stacks impose an order on the objects they contain so that the most recently added object will be the next object removed. Stacks are sometimes referred to as LIFO (last in, first out) structures.
Unlike the other organizations supported for collections, there is no interface common to classes the are used to organize stacks.
If you have decided that a stack is the organization to use, here are suggestions regarding which class to use:
- Firstly, do not use the Stack class for new code. The Stack class is poorly designed. All of its methods are synchronized, which can introduce unneeded overhead.
- Since Java provides no Stack interface, use one of the Deque classes to implement a stack. The operations needed to support a stack organization are a subset of the operations for a deque.
Performance of Collection ClassesIf you are not interested in how objects will be organized in a collection, then the only other consideration is performance. In that case, use the ArrayList class. It is fast and makes efficient use of memory.
What Have You Learned?This article has explained how to choose a collection based on object organization and performance constraints.
About the AuthorMark Grand is a software architect and book author with over 30 years of experience. Mark specializes in distributed systems, object oriented design, and Java, and he was the architect of the first commercial business-to-business e-commerce product to use the Internet.