We have walked the path from the array to weighted graphs and covered the problem-solving techniques. What is left is the main practical question: which structure do you take for a particular task? There is no generally "best" answer: every structure is fast at one thing and slow at another. But the choice follows a simple guide.
The easiest way to see it is a picture: three structures, the same seven keys, one question.
The same question costs differently: the array scans cell after cell, the tree descends three levels, the hash table computes a bucket number and lands straight in it. Choosing a structure is choosing which operation will be cheap.
General-purpose structures
Most storage tasks are covered by four types.
- An array — when there is little data, it rarely changes, and access goes by index. Nothing is simpler, access by number is instant, but search and removal are slow and the size is fixed.
- A linked list — when elements are added and removed at the ends and the volume is not known in advance. Textbooks recommend it "when there are many insertions in the middle", but in practice that does not hold: to insert in the middle you first have to walk the chain to it, and a plain
ArrayListwins almost always thanks to contiguous memory. In Java its role today is more often taken byArrayDeque. - A balanced search tree — when you need fast search, insertion, removal and order at the same time. Red-black trees and 2-3-4 trees give O(log N) for everything and can walk the data in ascending order.
- A hash table — when you need the fastest possible access by key (O(1) on average; with a poor hash function all keys land in one bucket and the lookup degenerates into a scan) and you do not need order. The fastest search, but no sorting, useless without the exact key, and it wants spare memory.
The default rule of thumb: access by key and order does not matter — a hash table; order or range queries matter — a balanced tree. Arrays and lists are for simple or narrow cases.
A quick cheat sheet of costs
To estimate whether a structure will carry the load, use big O notation — the growth order of the number of operations:
| Structure | Search | Insert | Delete | Order |
|---|---|---|---|---|
| Array (unordered) | O(N) | O(1) | O(N) | no |
| Ordered array | O(log N) | O(N) | O(N) | yes |
| Linked list | O(N) | O(1) | O(N)* | no |
| Balanced tree | O(log N) | O(log N) | O(log N) | yes |
| Hash table | O(1) average | O(1) average | O(1) average | no |
| Heap | O(N) | O(log N) | O(log N)** | weak |
* removal from a list is O(1) once the element is found; **only the maximum is cheap to remove from a heap.
Read it this way: an operation marked O(N) becomes the bottleneck on large data — which means the structure is wrong for that scenario.
Structures as tools
Some structures are picked not for storage but for a particular mechanism:
- A stack — when you need "last in, first out": undoing actions, parsing expressions, depth-first traversal.
- A queue — "first in, first out" processing: tasks in order, breadth-first traversal.
- A priority queue / heap — when you always need the most urgent element: schedulers, Dijkstra's algorithm, MST.
- A graph — when the task is about connections: routes, networks, dependencies.
Not only structures, algorithms too
Sorting deserves its own note, since nearly everyone needs it. For large arrays you take quicksort (O(N·log N) on average, the fastest in practice) or merge sort (a guaranteed O(N·log N) with no risk of degenerating). Simple sorts are for small volumes only, and for integers and short strings there is radix sort with linear time.
How to choose in practice
A short order of steps when the choice is in front of you:
- Which operations are frequent? Search, insertion, ordered traversal, "take the maximum"? Optimise for those and turn a blind eye to the rare ones.
- Is order needed? If yes — a tree or another ordered structure; if no — a hash table will do.
- How much data? On small data the difference between structures is invisible, so take the simplest one (an array, a list). Optimising pays off when there is a lot of data.
- Do not reinvent the wheel. Standard libraries already ship lists, trees, hash tables, queues and heaps. You learn how they work in order to pick the right one, not in order to write it again.
How it is done in Java
The "do not reinvent the wheel" point is worth unfolding: the standard library already holds implementations of every structure discussed here, and in practice the choice turns into a choice of class. Here is the map.
| Structure | Class | What is inside | What to watch |
|---|---|---|---|
| Array | ArrayList | a plain array, grows by about half | get(i) — O(1), add at the end — O(1) amortised, insertion in the middle — O(N) |
| Linked list | LinkedList | doubly linked nodes | the ends are O(1), but get(i) is O(N) plus cache misses: it loses to ArrayList almost always |
| Stack and queue | ArrayDeque | a circular queue in an array | every operation is O(1); Stack is not used — it inherits from Vector and iterates bottom-up |
| Hash table | HashMap, LinkedHashMap | buckets, collisions in a list, a tree past the threshold | O(1) on average, no order; LinkedHashMap keeps insertion order |
| Balanced tree | TreeMap, TreeSet | a red-black tree | guaranteed O(log N), keys in ascending order, firstKey, subMap |
| Heap | PriorityQueue | a binary heap in an array | offer and poll — O(log N), peek — O(1); iteration is not sorted |
| Sorting | Arrays.sort, Collections.sort | primitives — guarded quicksort, objects — TimSort | TimSort is stable and speeds up on partially ordered data |
By default you take ArrayList and HashMap — together they cover most tasks. ArrayDeque — when you need a stack or a queue, TreeMap — when you need order or ranges, PriorityQueue — when you always need the most urgent element. Everything else is a narrow case.
The picture from the top of the article can be executed: the same keys in three classes, one question each.
live example
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Lookup {
public static void main(String[] args) {
int[] ids = {50, 25, 75, 10, 60, 90, 42};
List<Integer> list = new ArrayList<>();
Map<Integer, String> hash = new HashMap<>();
TreeMap<Integer, String> tree = new TreeMap<>();
for (int id : ids) {
list.add(id);
hash.put(id, "order " + id);
tree.put(id, "order " + id);
}
int steps = 0;
for (int id : list) {
steps++;
if (id == 42) break;
}
System.out.println("list: " + steps + " comparisons to reach key 42");
System.out.println("hash table: " + hash.get(42) + ", iteration " + hash.keySet());
System.out.println("tree: " + tree.get(42) + ", next key " + tree.higherKey(42));
}
}
Run
Running examples is part of paid access. There the same code runs inside the article: editor, run and check next to the paragraph. Three free days →
The list honestly walked all seven elements. The hash table answered at once, but its iteration handed the keys back in bucket order — neither insertion order nor ascending. The tree answered and also told which key comes next: a hash table cannot answer that question at all.
The trap. The most common mistake with structures is not the choice itself but the fact that it cannot be changed afterwards. Once a concrete class leaks into field declarations, parameters and return types, swapping one structure for another turns into an edit across the whole codebase — and then it simply never happens, even when the choice is visibly wrong.
List<Order> orders = new ArrayList<>();
ArrayList<Order> pinned = new ArrayList<>();
The first line keeps the freedom: the implementation can be swapped in one place. The second nails the choice into the signatures. The rule is simple: variables, fields, parameters and return types are declared with an interface (List, Map, Set, Deque), and the concrete class is named once — in new. The interface is picked by the behaviour you need: List — access by index, Deque — work at the ends, NavigableMap — range queries. Then the conclusion "we do need order here after all" costs one line instead of a day of edits.
In short
- There is no ideal structure: the choice is a trade-off shaped by the frequent operations of your task.
- By key without order — a hash table (O(1)); with order and ranges — a balanced tree (O(log N)); simple cases — an array and a list.
- Big O is the quick way to tell whether a structure will carry the volume: an O(N) operation becomes the bottleneck on large data.
- Structures used as tools (stack, queue, heap, graph) are picked by the mechanism of the task, and sorting is picked by the size and type of the data.
- Declare the variable with an interface and name the class once in
new— otherwise the choice can no longer be changed.
What to read next
- Hash tables — where the O(1) comes from and what is paid for it.
- Red-black trees — how a tree keeps order and guarantees O(log N).
- Maths for big O notation — so the cost table is read rather than memorised.
- Why data structures and algorithms — the section's opening article, handy for re-reading the whole map.