A data structure is a decision about how to lay data out in memory. An algorithm is a decision about how to walk it. Almost everything else in this track is a consequence of those two sentences.
Why the layout is the whole thing
Suppose you have a million customer records and need to find one by email.
- Stored in an array, in no order: you check each in turn. A million comparisons in the worst case.
- Stored sorted by email: binary search finds it in about twenty.
- Stored in a hash table keyed by email: roughly one.
Same data, same question, same machine. The difference is entirely how the data was arranged before the question was asked. That is what choosing a data structure means, and it is why "make the code faster" is usually the wrong instinct — the code is rarely the problem.
There is no best structure
Every structure is fast at some things by being slow at others, and the trades are not subtle.
| Structure | Access by index | Search | Insert at front | Insert at end |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) — it is full |
| ArrayList | O(1) | O(n) | O(n) | O(1)* |
| Linked list | O(n) | O(n) | O(1) | O(1) |
| Hash table | — | O(1)* | O(1)* | O(1)* |
| Balanced BST | — | O(log n) | O(log n) | O(log n) |
| Heap | — | O(n) | O(log n) to insert, O(1) to read the min | |
* amortised or average. The distinction matters and gets its own treatment in ArrayList and hash tables.
Read the hash table row and it looks like the answer to everything. It is not: it has no order at all, so "the first ten alphabetically" or "everything between these two dates" is a full scan. A balanced tree is slower at every single operation and answers both instantly.
Four questions that pick one
- How do you look things up? By position → array. By key → hash table. By range or in order → tree.
- Does order matter? Insertion order, sorted order, or no order at all — this alone rules out most of the table.
- What changes, and where? Mostly reads → an array is hard to beat. Constant insertion and removal at the ends → a linked structure or a deque.
- How big does it get? At n = 100 everything is instant and you should pick whatever is clearest. The table only starts mattering when n is large — and then it matters a lot.
Question 4 is the one people skip. An O(n²) algorithm over a list that is always ten elements long is not a bug, and rewriting it is wasted effort.
What Java gives you
You will rarely implement these at work — the JDK ships them, and its versions are better tested than yours will be. What you need is to know which one you are reaching for.
| You want | Use | Underneath it is |
|---|---|---|
| An indexed sequence | ArrayList | a growable array |
| A queue or a stack | ArrayDeque | a circular buffer |
| Key to value | HashMap | a hash table with chaining |
| Key to value, in key order | TreeMap | a red-black tree |
| Key to value, in insertion order | LinkedHashMap | a hash table plus a linked list |
| Unique elements | HashSet | a HashMap ignoring the values |
| Always the smallest first | PriorityQueue | a binary heap |
Two worth knowing about specifically. java.util.Stack should not be used — it
extends Vector, so every method is synchronised whether you share it or not, and it
inherits get(int), which lets callers reach into the middle of a "stack". Use
ArrayDeque. And LinkedList is almost never the right answer despite its
name: it implements List, so people reach for it to get O(1) insertion, then call
get(i) in a loop and get O(n²).
So why implement them at all?
Because the trades in that first table are not memorisable facts, they are consequences — and
they stay slippery until you have written the code that causes them. You do not really know why
ArrayList.add is amortised O(1) until you have written the resize, and you will not
predict how a hash table degrades until you have written the bucket that a bad
hashCode turns into a linked list.
That is what the rest of this track does. Next: memory, because the reason an array beats a linked list at scanning is not in the complexity table at all.