Java Collections Internals & Performance

Look under the hood of Java's collections. After this lesson you'll know exactly how ArrayList, LinkedList, HashMap, TreeMap, and HashSet store data — and you'll pick the right one by its Big-O instead of by guessing.

Learn Java Collections Internals & Performance in our free Java course — a beginner-friendly interactive lesson with worked examples, a practice exercise and…

Part of the free Java course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

You should already know how to use Collections and Generics . This lesson explains the machinery inside them, so you understand why each one is fast or slow — not just how to call add() and get() .

Every collection is just a different strategy for storing items, with different trade-offs:

An ArrayList wraps a plain array (the backing array ). Because the items sit in one contiguous block, jumping to get(i) is a single calculation — that's O(1) random access.

Arrays can't grow, so when the backing array fills up, ArrayList allocates a bigger one (about 1.5x the size), copies everything across, and throws the old one away. Each individual copy is O(n), but because each resize buys a lot of headroom, the copies are rare. Averaged over many add() calls the cost is constant — this is amortized O(1) .

Inserting or removing in the middle is the slow case: every element after the gap must shift one slot, which is O(n) . Read the resizing happen in the output below.

A LinkedList stores no array at all. Each value lives in its own node , and every node holds a pointer to the previous and next node. Java's LinkedList is doubly-linked and keeps a reference to both the head and the tail.

That makes adding or removing at either end O(1) — you just re-wire a couple of pointers, nothing shifts. But there's no index math: to reach get(47) you must walk node by node from the nearest end, which is O(n) . The output prints how many nodes it walks.

A HashMap is an array of buckets . To store a key it calls the key's hashCode() , squeezes that number into the bucket range, and drops the entry there. Lookup repeats the same calculation and scans only that one bucket — so on average put() and get() are O(1) .

When two different keys land in the same bucket that's a collision , and the bucket holds a little list of entries. equals() then decides which entry is really your key. The load factor (size capacity, default 0.75) controls growth: once the map passes 0.75 full it doubles the bucket array and rehashes everything to keep collisions low.

A TreeMap keeps its keys in sorted order using a red-black tree — a binary search tree that rebalances itself on every insert so it never degrades into a slow lopsided shape. Every operation costs O(log n) : a touch slower than HashMap's O(1), but you get ordered iteration plus firstKey() , lastKey() , ceilingKey() , and range views for free.

A HashSet is simply a HashMap where you only care about the keys — the values are a hidden dummy object. That's why a set's elements are unique and why add() and contains() are average O(1) . (A TreeSet is the same trick over a TreeMap, giving sorted, O(log n) behaviour.)

Fill in the two blanks so a Point works as a HashMap key. Remember the contract: equal objects must return equal hash codes. The expected output is in the comments so you can self-check.

Each comment describes a job. Replace each ___ with the collection whose internals best fit that job. The hint on each line tells you the answer — match it to what you learned above.

Now with the scaffolding removed. You get only a comment outline and the expected output. Count each word, then print the counts in alphabetical order — the right Map gives you the sorting for free.

💡 Pre-size when you know the count: new ArrayList (10000) or new HashMap (expected * 4 / 3) skips repeated resize-and-copy work.

💡 Default to ArrayList: contiguous memory is CPU-cache friendly, so it beats LinkedList for almost everything. Reach for LinkedList (or ArrayDeque) only for true queue/deque workloads.

💡 Records are perfect keys: a record auto-generates correct, immutable equals() and hashCode() — ideal as HashMap keys with zero boilerplate.

* ArrayList add at the end is amortized O(1); "avg" means average case — a degenerate hashCode() can make hash collections O(n), or O(log n) once a bucket treeifies.

You can now explain how each core collection stores its data: ArrayList's resizing backing array, LinkedList's pointer-chained nodes, HashMap's buckets driven by hashCode() and equals() , TreeMap's self-balancing red-black tree, and HashSet riding on top of a HashMap. Best of all, you can read the right choice straight off the Big-O table.

Next up: Advanced HashMap, TreeMap & LinkedHashMap — ordering guarantees, navigable maps, and the tricks that make these data structures sing in real code.

Practice quiz

• Browse all free courses
• Cheat sheets & quizzes
• Coding dictionary