Understanding Java Collections: Interfaces, APIs, and Implementation Choices

Java collections, also known as containers, are derived from the two main interfaces Collection and Map. Collection stores single elements, while Map stores key‑value pairs.

Collection Interface

The Collection interface defines the core CRUD methods that all sub‑interfaces and implementations inherit. The operations are categorized as:

Function

Method

Add

add() / addAll()

Remove

remove() / removeAll()

Update

Not directly provided (use remove + add)

Read

contains() / containsAll()

Other

isEmpty() / size() / toArray()

Add

boolean add(E e);

The add() method inserts a single element; primitive types are auto‑boxed. addAll(Collection<? extends E> c) adds all elements from another collection.

boolean addAll(Collection<? extends E> c);

Remove

boolean remove(Object o);

Removes the specified element. The counterpart removeAll(Collection<?> c) removes all elements present in the given collection.

boolean removeAll(Collection<?> c);

Read

boolean contains(Object o);

Checks if a specific element exists. containsAll(Collection<?> c) checks if the collection contains all elements of another collection. boolean containsAll(Collection<?> c); Additional utility methods include isEmpty(), size(), and toArray().

List

Lists are ordered and allow duplicate elements. According to the JDK documentation, a list is "an ordered collection (also known as a sequence)" and "unlike sets, lists typically allow duplicate elements".

The two main implementations are ArrayList and LinkedList. Their time‑complexities are summarized below:

Operation

Method

ArrayList

LinkedList

Add (end)

add(E e)

O(1)

O(1)

Add (index)

add(int index, E e)

O(n)

O(n)

Remove (index)

remove(int index)

O(n)

O(n)

Remove (object)

remove(E e)

O(n)

O(n)

Update

set(int index, E e)

O(1)

O(n)

Read

get(int index)

O(1)

O(n)

Because ArrayList is backed by an array, it provides O(1) random access, making read and update operations faster. LinkedList excels when inserting or removing elements at the ends without shifting other elements.

Vector

Vector

also extends AbstractList and uses an array internally, but it is synchronized, which makes it slower and it is considered deprecated in modern code.

Queue & Deque

A Queue follows FIFO semantics, while a Deque allows insertion and removal at both ends. The standard Queue methods have two variants: one that throws exceptions and one that returns special values.

Function

Throws Exception

Returns Value

Add

add(e)

offer(e)

Remove

remove()

poll()

Peek

element()

peek()

For Deque, the API mirrors this pattern for both the front and rear ends.

Function

Throws Exception

Returns Value

Add

addFirst(e) / addLast(e)

offerFirst(e) / offerLast(e)

Remove

removeFirst() / removeLast()

pollFirst() / pollLast()

Peek

getFirst() / getLast()

peekFirst() / peekLast()

Implementation recommendations: use ArrayDeque for most queue/deque needs because it is more efficient; LinkedList is only needed for legacy Java 6 compatibility.

Stack

Although Java provides a Stack class, it extends Vector and is discouraged. Use a Deque (e.g., ArrayDeque) to implement stack semantics:

Deque<Integer> stack = new ArrayDeque<>();

Set

Sets are unordered and contain no duplicate elements, matching the mathematical definition of a set. The three common implementations are:

HashSet : backed by a HashMap, unordered, O(1) basic operations.

LinkedHashSet : combines a hash table with a linked list to preserve insertion order while keeping O(1) performance.

TreeSet : backed by a red‑black tree, provides sorted order with O(log n) operations.

All three store elements as keys in an internal map with a constant placeholder object as the value.

Conclusion

The article reviewed the main Java collection interfaces and their concrete implementations, highlighted the typical use‑cases and performance characteristics, and offered guidance on choosing the right data structure for interview or production code.