Java Collections Framework – Complete Reference
List Implementations
ArrayList
Properties:
1 Resizable array
2 Ordered, indexed
3 Allows duplicates
4 Not thread-safe
Time & Space Complexity:
1 Access O(1)
2 Insert/Delete end O(1) amortized
3 Insert/Delete middle O(n)
4 Space O(n)
Common Methods:
add(), get(), set(), remove(), size(), contains()
LinkedList
Properties:
1 Doubly linked list
2 Ordered
3 Implements List, Deque
Time & Space Complexity:
1 Access O(n)
2 Insert/Delete O(1)
3 Search O(n)
4 Space O(n)
Common Methods:
add(), addFirst(), addLast(), remove(), getFirst(), getLast()
Vector
Properties:
1 Legacy synchronized ArrayList
2 Thread-safe but slow
Time & Space Complexity:
1 Access O(1)
2 Insert/Delete O(n)
3 Space O(n)
Common Methods:
add(), get(), remove(), capacity()
Stack
Properties:
1 Legacy LIFO stack
2 Extends Vector
Time & Space Complexity:
1 Push/Pop O(1)
2 Peek O(1)
3 Space O(n)
Common Methods:
push(), pop(), peek(), empty()
Queue / Deque Implementations
PriorityQueue
Properties:
1 Heap-based
2 Natural or custom ordering
3 Not thread-safe
Time & Space Complexity:
1 Insert O(log n)
2 Remove O(log n)
3 Peek O(1)
4 Space O(n)
Common Methods:
offer(), poll(), peek(), add()
ArrayDeque
Properties:
1 Resizable array deque
2 No nulls
3 Faster than Stack
Time & Space Complexity:
1 Insert/Delete O(1)
2 Space O(n)
Common Methods:
addFirst(), addLast(), pollFirst(), pollLast()
Set Implementations
HashSet
Properties:
1 Unordered
2 Unique elements
3 Backed by HashMap
Time & Space Complexity:
1 Add/Search/Delete O(1)
2 Space O(n)
Common Methods:
add(), remove(), contains(), size()
LinkedHashSet
Properties:
1 Insertion order preserved
2 Unique elements
Time & Space Complexity:
1 Add/Search/Delete O(1)
2 Space O(n)
Common Methods:
add(), remove(), contains()
TreeSet
Properties:
1 Sorted order
2 Red-Black Tree
Time & Space Complexity:
1 Add/Search/Delete O(log n)
2 Space O(n)
Common Methods:
first(), last(), higher(), lower()
CopyOnWriteArraySet
Properties:
1 Thread-safe
2 Copy-on-write mechanism
Time & Space Complexity:
1 Read O(1)
2 Write O(n)
3 Space O(n)
Common Methods:
add(), remove(), contains()
EnumSet
Properties:
1 Enum-only
2 Bit vector based
3 Very fast
Time & Space Complexity:
1 All ops O(1)
2 Space O(n)
Common Methods:
of(), allOf(), add(), contains()
Map Implementations
HashMap
Properties:
1 Unordered
2 Allows one null key
Time & Space Complexity:
1 Put/Get O(1)
2 Space O(n)
Common Methods:
put(), get(), remove(), keySet(), values()
LinkedHashMap
Properties:
1 Insertion/access order
2 Predictable iteration
Time & Space Complexity:
1 Put/Get O(1)
2 Space O(n)
Common Methods:
put(), get(), remove()
TreeMap
Properties:
1 Sorted keys
2 Red-Black Tree
Time & Space Complexity:
1 Put/Get O(log n)
2 Space O(n)
Common Methods:
firstKey(), lastKey(), higherKey()
ConcurrentHashMap
Properties:
1 Thread-safe
2 Segmented locking / CAS
Time & Space Complexity:
1 Put/Get O(1)
2 Space O(n)
Common Methods:
put(), get(), compute(), merge()
WeakHashMap
Properties:
1 Keys GC eligible
2 Memory-sensitive
Time & Space Complexity:
1 Put/Get O(1)
2 Space O(n)
Common Methods:
put(), get(), remove()
IdentityHashMap
Properties:
1 Reference equality (==)
2 Rare use
Time & Space Complexity:
1 Put/Get O(1)
2 Space O(n)
Common Methods:
put(), get(), containsKey()
Concurrent Collections
BlockingQueue
Properties:
1 Thread-safe
2 Blocking operations
Time & Space Complexity:
1 Insert/Delete O(1)
2 Space O(n)
Common Methods:
put(), take(), offer(), poll()
ConcurrentSkipListMap
Properties:
1 Sorted
2 Thread-safe
Time & Space Complexity:
1 Put/Get O(log n)
2 Space O(n)
Common Methods:
put(), get(), firstKey()
Non-Collection Structures
Trie
Properties:
1 Prefix-based tree
2 Fast string search
Time & Space Complexity:
1 Insert/Search O(L)
2 Space O(n*L)
Common Methods:
insert(), search(), startsWith()
Union-Find
Properties:
1 Disjoint set
2 Path compression
Time & Space Complexity:
1 Union/Find α(n)
2 Space O(n)
Common Methods:
find(), union()