Time Complexity of Java Collections

Java collections are often chosen from memory: ArrayList for lists, HashMap for key-value lookups, HashSet for uniqueness, and PriorityQueue for heap behavior. Time complexity helps explain why those defaults work and where they stop working.

Use this guide as a practical backend reference. Big-O is not a benchmark, but it is a useful way to compare how collection operations grow as data grows.

Quick reference table

Collection	Operation	Average	Worst	Practical note
ArrayList	get by index	O(1)	O(1)	Fast random access through a backing array.
ArrayList	append	O(1)	O(n)	Usually constant, but resize copies elements.
ArrayList	insert or remove near middle	O(n)	O(n)	Elements after the position must shift.
LinkedList	get by index	O(n)	O(n)	Must walk nodes from the front or back.
LinkedList	add or remove with iterator position	O(1)	O(1)	Only after the position is already known.
HashMap	get or put	O(1)	O(n)	Depends on hash distribution and collision behavior.
TreeMap	get or put	O(log n)	O(log n)	Maintains sorted keys with a balanced tree.
HashSet	contains or add	O(1)	O(n)	Backed by hashing, like HashMap keys.
TreeSet	contains or add	O(log n)	O(log n)	Sorted set behavior.
PriorityQueue	peek	O(1)	O(1)	Reads the heap root.
PriorityQueue	offer or poll	O(log n)	O(log n)	Insert and remove adjust heap order.
ArrayDeque	add or remove at ends	O(1)	O(n)	Usually constant, with occasional resize.

ArrayList complexity

ArrayList stores references in a resizable array.

Getting by index is O(1) because the list can jump directly to the position. Iteration is also efficient in practice because the backing array is compact and cache-friendly.

Appending is usually O(1), but occasionally the list must allocate a larger array and copy existing elements. That single append can be O(n), while the amortized cost across many appends is still O(1).

Insertion or removal near the beginning or middle is O(n) because elements must shift.

List<String> users = new ArrayList<>();
users.add("alice");        // amortized O(1)
String first = users.get(0); // O(1)

For most backend service code, ArrayList is the default list choice.

LinkedList complexity

LinkedList stores each element in a node with links to neighboring nodes.

Adding or removing can be O(1) when the code already has the node position through an iterator. But getting an item by index is O(n), and many real operations need a search before the cheap insert or remove can happen.

This is why LinkedList is often slower than people expect. It has higher memory overhead and more pointer chasing than ArrayList.

If you need queue behavior, consider ArrayDeque before reaching for LinkedList.

HashMap complexity

HashMap is usually described as O(1) average-case for get, put, and containsKey.

That average assumes useful hash codes, a reasonable load factor, and a table that is not overloaded. When collisions grow, lookup can require more work. Modern Java includes collision handling improvements, but good key design still matters.

Map<String, Integer> counts = new HashMap<>();
counts.put("java", 1);       // average O(1)
counts.get("java");          // average O(1)

Set an initial capacity when loading a large known number of entries. Changing the load factor is rarely needed for normal application code.

TreeMap and TreeSet complexity

TreeMap and TreeSet keep keys or values sorted. Their common operations are O(log n), not O(1), because the structure maintains ordering.

That cost is worth paying when you need sorted iteration, range queries, nearest keys, or ordered set behavior.

Use HashMap or HashSet when you only need lookup by equality. Use TreeMap or TreeSet when ordering is part of the requirement.

HashSet complexity

HashSet is backed by hashing. add, contains, and remove are average O(1), with similar caveats to HashMap.

Use it when you need uniqueness and fast membership checks.

Set<Long> seenUserIds = new HashSet<>();
if (seenUserIds.add(userId)) {
    // first time seeing this user id
}

This pattern is often cleaner and faster than repeatedly scanning a list for duplicates.

PriorityQueue complexity

PriorityQueue is backed by a heap. Reading the highest-priority item with peek is O(1). Adding with offer and removing with poll are O(log n).

This makes it useful for “give me the next smallest” or “give me the next highest priority” workflows.

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(30);
queue.offer(10);
queue.offer(20);

int next = queue.poll(); // 10

If you need to repeatedly remove the minimum or maximum item, a priority queue is often a better fit than sorting the whole collection after each change.

Complexity is not the whole decision

Big-O compares growth, but backend code also depends on:

• Memory overhead.
• Garbage collection pressure.
• Cache locality.
• Thread-safety requirements.
• Ordering requirements.
• Serialization shape.
• Database and network costs around the collection.

For example, LinkedList can look attractive in a simple complexity table, but ArrayList often wins in real application code because it is compact and easy for the CPU to scan.

Common mistakes

The first mistake is choosing a collection only from one operation. A list may be built, searched, sorted, filtered, serialized, and returned. The whole workflow matters.

The second mistake is ignoring average versus worst case. HashMap is usually fast, but poor hash behavior or unusual keys can change the story.

The third mistake is using sorted collections without needing sorted behavior. If ordering does not matter, O(1) average hash lookup is usually a better starting point than O(log n) tree lookup.

The fourth mistake is using a list when a set or map would express the real operation better.

Practical backend defaults

Use these defaults unless a specific requirement says otherwise:

• Use ArrayList for ordered lists that you append, iterate, and return.
• Use HashMap for key-value lookup.
• Use HashSet for uniqueness and membership checks.
• Use ArrayDeque for stack or queue behavior in single-threaded code.
• Use PriorityQueue for repeated priority-based removal.
• Use TreeMap or TreeSet when sorted order or range navigation matters.
• Use concurrent collections only when ownership and threading require them.

Then measure hot paths with realistic data.

Related reading

Use the Big-O Cheat Sheet as a quick lookup tool while reviewing code. For deeper explanations, read Big-O Notation Explained, ArrayList vs LinkedList in Java, HashMap Load Factor Explained, and Java PriorityQueue Explained.

You can also browse the Java Collections topic cluster for the full learning path.