Java Collection Framework Comparison
List Implementations in Java
Feature ArrayList LinkedList Vector Stack
Order of Maintains Maintains Maintains Maintains
Elements insertion order insertion order insertion order insertion
order
Implementati Resizable array Doubly linked list Resizable array Resizable
on array
(extends
Vector)
Performance Faster for random Faster for Faster for Faster for
access insertion/removal random access LIFO
operations
Thread Safety Not thread-safe Not thread-safe Not thread-safe Not thread-
safe
Common Use Fast random Frequent Similar to LIFO
Case access insertions/deletio ArrayList, with operations
ns more memory (push, pop)
overhead
Example `ArrayList<Intege `LinkedList<Intege `Vector<Intege `Stack<Intege
r> list = new r> list = new r> list = new r> stack = new
ArrayList<>()` LinkedList<>()` Vector<>()` Stack<>()`
Set Implementations in Java
Feature HashSet LinkedHashSet TreeSet SortedSet
Order of No order Insertion order Sorted order Sorted order
Elements (unordered) (ordered) (natural or (natural or
custom custom
comparator) comparator)
Backing Hash table Hash table + Linked list Red-Black Tree Extends `Set`
Structure and provides
sorted
methods
Null Allows one `null` Allows one `null` Does not allow Depends on
Elements element element `null` elements implementatio
n (e.g.,
`TreeSet` does
not allow)
Time Constant-time Slightly slower due to Logarithmic Same as
Complexit operations linked list (`O(1)` for time (`O(log n)`) `TreeSet` since
y (`O(1)`) add, `O(n)` for remove) for basic it extends
operations `SortedSet`
Thread Not thread-safe Not thread-safe Not thread-safe Not thread-
Safety safe
Common Fast operations, Maintain insertion Maintain Maintain
Use Case no need for order elements in sorted order
order sorted order and access
elements in
ranges
Example `HashSet<Intege `LinkedHashSet<Intege `TreeSet<Intege Used as a type
r> set = new r> set = new r> set = new for `TreeSet`,
HashSet<>()` LinkedHashSet<>()` TreeSet<>()` not a concrete
implementatio
n
Map Implementations in Java
Feature HashMap LinkedHashMap TreeMap ConcurrentHashMap
Order of No order Insertion order Sorted order No order (unordered)
Element (unordered) (ordered) (natural or
s custom
comparator)
Backing Hash table Hash table + Linked Red-Black Segmented hash table
Structur list Tree
e
Null Allows one Allows one `null` Does not Allows one `null` key,
Element `null` key and key and multiple allow `null` no `null` values
s multiple `null` `null` values keys
values
Time Constant-time Slightly slower due Logarithmic Constant-time
Complex operations to linked list (`O(1)` time (`O(log operations (`O(1)`) for
ity (`O(1)`) for add, `O(n)` for n)`) for most operations
remove) operations
Thread Not thread- Not thread-safe Not thread- Thread-safe
Safety safe safe
Commo Fast lookups Maintain insertion Maintain Thread-safe operations
n Use and updates order elements in in concurrent
Case sorted order environments
Example `HashMap<Int `LinkedHashMap<In `TreeMap<Int `ConcurrentHashMap<I
eger, String> teger, String> map = eger, String> nteger, String> map =
map = new new map = new new
HashMap<>()` LinkedHashMap<>( TreeMap<>()` ConcurrentHashMap<>
)` ()`
Queue Implementations in Java
Feature PriorityQueue ArrayDeque LinkedList ConcurrentLinkedQueue
Order Elements are Elements are Elements are Elements are ordered in
of ordered by their ordered in FIFO ordered in FIFO order
Elemen priority order FIFO order
ts
Backing Heap (priority- Resizable array Doubly linked Non-blocking queue
Structu based) list (CAS-based)
re
Null Does not allow Allows `null` Allows `null` Does not allow `null`
Elemen `null` elements elements elements elements
ts
Time Logarithmic time Constant-time Constant-time Constant-time
Comple (`O(log n)`) for operations operations operations (`O(1)`) for
xity add/remove (`O(1)`) for (`O(1)`) for add/remove
add/remove add/remove
Thread Not thread-safe Not thread-safe Not thread- Thread-safe
Safety safe (concurrent)
Commo Maintain priority Fast queue Queue with Concurrent queue
n Use ordering operations linked list operations
Case structure
Exampl `PriorityQueue<I `ArrayDeque<In `LinkedList<In `ConcurrentLinkedQueue
e nteger> queue = teger> queue = teger> queue = <Integer> queue = new
new new new ConcurrentLinkedQueue
PriorityQueue<>( ArrayDeque<>( LinkedList<>() <>()`
)` )` `
