Collections

There are a number of major Collection types in Java:

• List
• Set
• Queue
• Map
• Multimap

List

A List is essentially an object representation of a primitive array. There are various implementations, but they are generally a lot more useful than using primitive arrays directly. The most obvious feature is that most list implementations can grow (or shrink) in size, but this is just the begininning.

Common Operations

Description	Code
An empty immutable list	Collections.EMPTY_LIST
An empty immutable list	<E> List<E> Collections.emptyList()
An empty immutable list	<E> List<E> List.of()
An immutable list (from array)	<E> List<E> List.of(E... elements)
An immutable list (from collection)	<E> List<E> List.copyOf(Collection<? extends E> elements)
An unmodifiable view of a list	<E> List<E> Collections.unmodifiableList(List<? extends E> list)
A thread-safe view of a list	<E> List<E> Collections.synchronizedList(List<? extends E> list)
Replace all elements in a list with a single element	<E> void Collections.fill(List<? super E> list, T replacement)
Converts an Enumeration to an ArrayList	<E> ArrayList<E> Collections.list(Enumeration<E> enumeration)
Reverse the elements in a list	void Collections.reverse(List<?> list)
Shuffle the elements in a list	void Collections.shuffle(List<?> list)
Shuffle the elements in a list	void Collections.shuffle(List<?> list, Random random)
Sort the elements in a list (natural ordering)	<E extends Comparable<? super E>> void Collections.sort(List<E> list)
Sort the elements in a list (by comparator)	<E> void Collections.sort(List<E> list, Comparator<? super E> comparator)

---

ArrayList

The ArrayList implementation is by far the most commonly used and is backed by an array. As elements are added, a new larger array is allocated as necessary and the contents copied.

• Efficient: Calling add() or remove() from the end of the list. Calling get() and set() by index.
• Inefficient: Adding to or removing from arbitrary positions in the list, particularly near the head are expensive operations. Ideally always add and remove from the end of the list.

List<String> list = new ArrayList<>();
list.add("first");
list.add("second");
list.add("third");

// Calls to get() and set() by index is very fast regardless of list size - O(1)
String third = list.get(2);
list.set(0, "Zero");

// Calls to add() and remove() from the end of the list is very fast - O(1)
list.add("fourth");
list.remove(list.size()-1);

// Calls to add() and remove() from the beginning of the list is very slow - O(N)
list.add(0, "Number");
list.remove(0);

LinkedList

The LinkedList implementation is backed by a linked list of objects.

• Efficient: Calling add() or remove() from the beginning or end of the list. Also adding or removing during iteration.
• Inefficient: Index based operations like get() and set() are generally expensive operations.

CopyOnWriteArrayList

The CopyOnWriteArrayList implementation is a thread-safe list. Copy-on-write data structures are optimal for use in multi-threaded environments where data is read very frequently, and only updated occasionally.

• Thread-Safe
• Efficient: Read operations are very efficient. They are lock-free, supporting any number of simultanious threads, and provide the same characteristics as ArrayList.
• Inefficient: Write operations are very expensive. They are synchronized and involve cloning the underlying array. They should be called sparingly and bulk write operations should be preferred.

Set

A Set is a collection of unique objects of the same type. Attempts to add a duplicate element will fail (without an error).

• Elements: Are unique
• Elements: Should be immutable
• Elements: Must implement hashCode() and equals() correctly
• Elements: Some sets require the elements are Comparable (for sorting)

Common Operations

Description	Code
An empty immutable set	Collections.EMPTY_SET
An empty immutable set	<E> Set<E> Collections.emptySet()
An empty immutable set	<E> Set<E> Set.of()
An immutable set (from array)	<E> Set<E> Set.of(E... elements)
An immutable set (from collection)	<E> Set<E> Set.copyOf(Collection<? extends E> elements)
An unmodifiable view of a set	<E> List<E> Collections.unmodifiableSet(List<? extends E> list)
A thread-safe view of a set	<E> List<E> Collections.synchronizedSet(List<? extends E> list)

---

HashSet

The HashSet implementation is backed by a HashMap internally.

• Sorting: Elements are not sorted

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);

// These assertions are correct, you can not add the same element twice
Assertions.assertFalse(set.add(1));
Assertions.assertFalse(set.add(2));
Assertions.assertFalse(set.add(3));

// Careful - if you call set.toString() it is NOT guaranteed to be "[1,2,3]" (but it might be)
Assertions.assertTrue("[1,2,3]", set.toString());

LinkedHashSet

The LinkedHashSet implementation is backed by a LinkedHashMap internally.

• Sorting: Elements are sorted by Insertion Order

Set<Integer> set = new LinkedHashSet<>();
set.add(1);
set.add(2);
set.add(3);

// These assertions are correct - you can not add the same element twice
Assertions.assertFalse(set.add(1));
Assertions.assertFalse(set.add(2));
Assertions.assertFalse(set.add(3));

// This assertion is correct - the set is sorted by insertion order
Assertions.assertTrue("[1,2,3]", set.toString());

TreeSet

The TreeSet implementation is backed by a TreeMap internally.

• Sorting: Elements are sorted by Natural Order or the Comparator provided in the constructor

Set<Integer> set = new TreeSet<>();
set.add(3);
set.add(2);
set.add(1);

// These assertions are correct - you can not add the same element twice
Assertions.assertFalse(set.add(1));
Assertions.assertFalse(set.add(2));
Assertions.assertFalse(set.add(3));

// This assertion is correct - the set is sorted by natural ordering (for numbers, smallest to largest)
Assertions.assertTrue("[1,2,3]", set.toString());

ConcurrentSkipListSet

The ConcurrentSkipListSet implementation is a thread-safe sorted set. It is backed by a ConcurrentSkipListMap internally.

• Thread-Safe
• Sorting: Elements are sorted by Natural Order or the Comparator provided in the constructor

CopyOnWriteArraySet

The CopyOnWriteArraySet implementation is a thread-safe set. It is backed by a CopyOnWriteArrayList internally. Copy-on-write data structures are optimal for use in multi-threaded environments where data is read very frequently, and only updated occasionally.

• Thread-Safe
• Sorting: Elements are sorted by Insertion Order
• Efficient: Read operations are very efficient if the set remains small. They are lock-free, supporting any number of simultanious threads, and provide the same characteristics as ArrayList.
• Inefficient: Write operations are very expensive. They are synchronized and involve cloning the underlying array. They should be called sparingly and bulk write operations should be preferred. Large set size is also an issue as the implementation is backed by an array not a map.

Queue

A Queue is a collection for storage of elements before processing. A Deque is a double-ended queue which supports insertion and removal from both ends.

Description	Code
ConcurrentLinkedDeque	An unbounded concurrent deque based on linked nodes
LinkedBlockingDeque	An optionally-bounded blocking deque based on linked nodes
ArrayBlockingQueue	A bounded blocking queue backed by an array
LinkedBlockingQueue	An optionally-bounded blocking queue based on linked nodes

Map

A Map is a collection that maps keys to values. The keys in the map have a number of constraints:

• Keys: Are unique
• Keys: Should be immutable
• Keys: Must implement hashCode() and equals() correctly
• Keys: Some maps require the keys are Comparable (for sorting)

Common Operations

Description	Code
An empty immutable map	Collections.EMPTY_MAP
An empty immutable map	<K,V> Map<K,V> Collections.emptyMap()
An empty immutable map	<K,V> Map<K,V> Map.of()
An immutable map (from elements)	<K,V> Map<K,V> Map.of(K k1, V v1)
An immutable map (from elements)	<K,V> Map<K,V> Map.of(K k1, V v1, K k2, V v2)
An immutable map (from collection)	<K,V> Map<K,V> Map.copyOf(Map<? extends K, ? extends V> map)
An unmodifiable view of a map	<K,V> Map<K,V> Collections.unmodifiableMap(Map<? extends K, ? extends V> map)
A thread-safe view of a map	<K,V> Map<K,V> Collections.synchronizedMap(Map<? extends K, ? extends V> map)

---

HashMap

The HashMap implementation is the most commonly used.

• Sorting: Elements are not sorted

Map<String, Integer> map = new HashMap<>();
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);

Assertions.assertEquals(1, map.get("One"));
Assertions.assertEquals(2, map.get("Two"));
Assertions.assertEquals(3, map.get("Three"));

LinkedHashMap

The LinkedHashMap implementation is the same as HashMap, but it maintains insertion ordering of entries as they are added.

• Sorting: Entries are sorted by Insertion Order

TreeMap

The TreeMap implementation is map with entries sorted by key (see NavigableMap). It is an implementation of a red-black binary search tree.

• Sorting: Entries are sorted by Natural Order or the Comparator provided in the constructor

ConcurrentHashMap

The ConcurrentHashMap implementation is thread-safe map. It uses lock striping to improve concurrent access.

• Thread-Safe
• Sorting: Elements are not sorted

ConcurrentSkipListMap

The ConcurrentSkipListMap implementation is thread-safe map with entries sorted by key (see NavigableMap). It is a concurrent implementation of skip-lists.

• Thread-Safe
• Sorting: Entries are sorted by Natural Order or the Comparator provided in the constructor

Multimap

The Multimap is a useful map available in the popular Google Guava Core Java library. A MultiMap is a collection that maps keys to a collection of values.

ListMultimap

The ListMultimap implementation stores the values in the map as a list. There are a few implementations:

• ArrayListMultiMap
• LinkedListMultiMap
• ImmutableListMultimap

ListMultimap<String, Integer> map = ArrayListMultimap.create();
map.put("Numbers", 1);
map.put("Numbers", 2);
map.put("Numbers", 3);

// The get() method returns a list, not a single value
Assertions.assertEquals(List.of(1, 2, 3), map.get("Numbers"));

SetMultimap

The SetMultimap implementation stores the values in the map as a list. There are a few implementations:

• HashMultiMap
• LinkedHashMultiMap
• ImmutableSetMultimap
• TreeMultimap

SetMultimap<String, Integer> map = HashMultimap.create();
map.put("Numbers", 1);
map.put("Numbers", 2);
map.put("Numbers", 2);
map.put("Numbers", 3);
map.put("Numbers", 3);
map.put("Numbers", 3);

// The get() method returns a set, so no duplicate values
Assertions.assertEquals(Set.of(1, 2, 3), map.get("Numbers"));

MultimapBuilder

The MultimapBuilder provides the most flexible way to create a multimap with the exact properties you need.

Keys:

• hashKeys()
• linkedHashKeys()
• treeKeys()
• enumKeys()

Values:

• arrayListValues() - ListMultimap
• linkedListValues() - ListMultimap
• hashSetValues() - SetMultimap
• linkedHashSetValues() - SetMultimap
• treeSetValues() - SetMultimap
• enumSetValues() - SetMultimap

// Build a multimap with tree sorted keys and an ArrayList for values
ListMultimap<String, Integer> map = MultimapBuilder.treeKeys().arrayListValues().build();

// Build a multimap with enum keys and a LinkedHashSet for values
SetMultimap<TimeUnit, Double> map = MultimapBuilder.enumKeys(TimeUnit.class).linkedHashSetValues().build();