Java Collections: When to Use Set, Map, List, or Queue

Taking advantage of the interfaces offered by the Collections Framework keeps developers from spending energy building their own structures, freeing them to focus on the crucial parts of development. These high-quality, high-performance data structures and algorithms improve the excellence and efficiency of applications, while also promoting software reuse and enabling compatibility between APIs that aren’t inherently related.

What is the Collections Framework?

The Collections Framework is a well-defined structure made up of a set of interfaces and classes used to represent and handle groups of data as a single entity, commonly called a collection. Within the Collections Framework, we find the following elements:

• Interfaces: Allow manipulating collections following the principle of “program to interfaces, not implementations,” meaning objects should only be accessed through the methods defined in those interfaces.
• Implementations: Refer to the concrete implementations of the interfaces. These are the classes that provide an actual implementation of the interfaces and are used to create specific collection instances.
• Algorithms: Methods that perform various operations on the objects contained in collections, including operations like searching and sorting.

Interfaces

• Collection: Sits at the top of the hierarchy. There are no direct implementations of this interface, but it defines the fundamental operations for collections, such as adding, removing, clearing, and more.
• Set: This interface defines a collection that doesn’t allow duplicate elements. The SortedSet interface, which inherits from Set, allows the natural ordering of elements, for example, alphabetically.
• List: Defines an ordered collection, where duplicate elements are allowed. This interface is the most appropriate when you need random access to elements using their indices.
• Queue: A type of collection that maintains a priority list, where the order of elements is determined by the implementation of Comparable or Comparator. Through the Queue interface, you can build queues and stacks.
• Map: Each element actually contains two objects: a key and a value. Values can be duplicated, but keys cannot. The SortedMap interface extends Map and allows ascending sorting of keys. An example application of this interface is the Properties class, used to store a system’s settings and properties.

Implementations

• ArrayList: Works like an array that can grow in size. Searching for an element is fast, but inserting and removing elements is slower and proportional to the structure’s size. It’s the ideal choice when fast access to elements is the priority. For example, when creating a catalog of your personal library, where each book gets a sequential number for access.
• LinkedList: Implements a linked list, where each node holds data and a reference to the next node. Unlike ArrayList, searching is slower, but insertions and removals are fast. So prefer LinkedList when you frequently need to insert and remove items, such as when managing a monthly grocery list.
• HashSet: Offers fast access to data, but doesn’t guarantee any ordering. It’s the right choice when your solution requires unique elements and order doesn’t matter. For example, when creating a catalog of your music.
• TreeSet: Data is ordered, but access is slower than in HashSet. Use TreeSet when you need a set of unique elements in natural order. It’s recommended for the same use cases as HashSet, with the added benefit of natural ordering.
• LinkedHashSet: Derived from HashSet, it keeps a doubly linked list of its elements. Elements are iterated in insertion order, or in the order they were last accessed in an iteration. It’s useful for recording the arrival order of runners in a marathon.
• HashMap: Based on a hash table, it allows null keys and values. It doesn’t guarantee any ordering of the data. Choose it when ordering doesn’t matter and you need an identifier, such as the ISBN in a personal library catalog.
• TreeMap: Implements SortedMap and guarantees ascending ordering of keys. You can specify a custom order. Use it when you need an ordered map. Similar to HashMap, but with lower performance.
• LinkedHashMap: Keeps a doubly linked list of elements, iterating in the keys’ insertion order. Useful when insertion order matters, such as recording runners in a marathon.

All these implementations have the methods defined in their interfaces, accept null elements, and, in maps, both keys and values can be null. They aren’t safe for concurrent use and are serializable, which lets you save their state, and they support the clone() method, which creates copies of objects.

Queues are used when you need LIFO, FIFO, or priority-based removal semantics, and, finally, maps are used when you need to associate keys with values.

Lists

Let’s start with a comparison table for lists. The common operations for lists are adding and removing elements, accessing an element by index, traversing elements, and finding an element:

As we can see, ArrayList is good for adding and removing elements at the end, as well as for random access to elements. On the other hand, it’s poor for adding and removing elements at arbitrary positions. Meanwhile, LinkedList is good for adding and removing elements at any position. However, it doesn’t support true O(1) random access. So, when it comes to lists, the default choice is ArrayList until you need fast insertion and removal of elements at any position.

Sets

For sets, we care about adding and removing elements, traversing elements, and finding an element:

As we can see, the default choice is the HashSet collection, since it’s very fast for all the operations it supports. Additionally, if the insertion order of elements also matters, we opt for LinkedHashSet. Basically, it’s an extension of HashSet that keeps track of elements’ insertion order using an internal linked-list structure.

If elements need to be sorted and that sorted order needs to be preserved when adding and removing elements, then we opt for TreeSet.

If the set’s elements are just enum values from a single enum type, then the wisest choice is EnumSet.

Queue

Queues can be split into two groups:

1. LinkedList, ArrayDeque - Implementations of the Queue interface can act as stack, queue, and deque data structures. Generally, ArrayDeque is faster than LinkedList. So it’s the default choice.
2. PriorityQueue - Queue implementation backed by a binary heap data structure. Used for fast retrieval (O(1)) of the highest-priority elements. Adding and removing run in O(log(n)) time.

Maps

Just like with sets, we consider the operations of adding and removing elements, traversing elements, and finding an element for maps:

The selection logic for maps is similar to the selection logic for sets: we use HashMap by default, LinkedHashMap if insertion order also matters, TreeMap for sorting, and EnumMap when the keys belong to values of a specific enum type.

Finally, there are two implementations of the Map interface with very specific applications: IdentityHashMap and WeakHashMap.