Java Reference ยท Collections
The Java Collections Framework
Overview of the Java Collections Framework: Collection, List, Set, Queue, Deque and Map, their main implementations, and how to pick the right one.
The Collections Framework is the part of java.util that gives you ready-made data structures: growable lists, sets without duplicates, queues, double-ended queues and key-value maps. Every structure is described by an interface (what it can do) and implemented by one or more classes (how it does it). Code written against the interface keeps working when you swap the implementation.
There are two separate hierarchies. Collection is the root of lists, sets and queues. Map stands on its own, because a mapping from keys to values is not a collection of single elements. Maps still plug into the framework: keySet(), values() and entrySet() give you collection views of a map.
List<String> names = new ArrayList<>(); Set<Integer> ids = new HashSet<>(); Map<String, Integer> ages = new TreeMap<>(); Deque<String> stack = new ArrayDeque<>();
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
The interfaces
| Interface | Meaning | Duplicates | Order |
|---|---|---|---|
Collection<E> |
Root of lists, sets and queues | Depends | Depends |
List<E> |
Indexed sequence | Allowed | Insertion order, access by index |
Set<E> |
Mathematical set | Not allowed | Depends on the implementation |
SortedSet<E> / NavigableSet<E> |
Set kept in sorted order | Not allowed | Sorted |
Queue<E> |
Elements waiting to be processed | Allowed | Usually FIFO |
Deque<E> |
Queue open at both ends (stack or queue) | Allowed | Insertion order |
Map<K,V> |
Keys mapped to values | Keys unique | Depends |
SequencedCollection<E> |
Defined first and last element (Java 21) | Depends | Defined encounter order |
Main implementations
| Class | Backed by | Strengths |
|---|---|---|
ArrayList |
Resizable array | Fast indexed access; the default list |
LinkedList |
Doubly linked nodes | Cheap insertion at the ends; also a Deque |
HashSet / HashMap |
Hash table | Constant-time lookups on average; no order guarantee |
LinkedHashSet / LinkedHashMap |
Hash table plus linked list | Predictable iteration order |
TreeSet / TreeMap |
Red-black tree | Sorted order, range queries, O(log n) |
ArrayDeque |
Circular array | Fastest stack and queue |
PriorityQueue |
Binary heap | Always gives the smallest element first |
EnumSet / EnumMap |
Bit set / array | Compact collections keyed by enum constants |
Usage notes
- Declare with the interface:
List<String> names = new ArrayList<>();. Use the class type only when you need members that exist only there, such asArrayList.ensureCapacity()orTreeMap.firstKey(). - Collections hold references to objects. Primitives are boxed:
List<Integer>, notList<int>. See Autoboxing. - Most operations are optional. Immutable collections from
List.of()orCollections.unmodifiableList()throwUnsupportedOperationExceptionfrom mutators. - Iteration order:
HashSetandHashMapmake no promise about it, and it can change between Java versions. UseLinkedHash*orTree*when order matters. - Not thread-safe: none of the classes above support concurrent modification. See Concurrent collections.
- Legacy classes:
Vector,StackandHashtablepredate the framework; preferArrayList,ArrayDequeandHashMap/ConcurrentHashMap. - Equality matters: hash-based classes use
equals()andhashCode(); sorted classes useComparableor aComparator.