Pick the Right Structure:Match the Job to the Data Layout

A feature-flag check calls knownFlags.contains(name) on every request. A store locator answers “pins in this viewport” by walking fifty thousand lat/longs. Both teams used ArrayList. Both compiled. Both passed tests with ten items. One job needed a set. The other needed a spatial tree. Same type. Two different expensive layouts.

Name the hot operation, then pick the layout that makes that operation cheap. This page is the series decision guide — not a recap of every rotation. Terms this series will not re-teach (ADT vs implementation, amortized vs worst-case, contiguous vs linked, how to read a complexity table) live on the Data Structures Roadmap. Jump to the row that matches the pain you have today.

The two bills that look like one type

contains and “in this box” are honest verbs. The layout behind them is not:

boolean flagOn(List<String> known, String name) {
    return known.contains(name); // walks n flags
}

List<Pin> inViewport(List<Pin> pins, Box box) {
    return pins.stream().filter(box::contains).toList(); // scans every pin
}

Both pass a unit test. At production size, the first is a uniqueness job (hash set). The second is a region job (quadtree / k-d tree). Wrapping either in a prettier method name does not change the bill.

Note: If you cannot name the operation that runs in the hot path, you are not ready to name a structure. Start there.

Random access

Index i is pointer arithmetic only when the slots sit in one block. A linked list makes you walk i pointers to get there.

Job	Structure	JDK	Post
get(i) / set(i) on a fixed length	Array	T[]	Arrays: Why Index i Is Free and Insert in the Middle Is Not
Same, but the length will grow	Dynamic array	ArrayList	Dynamic Arrays: Amortized Growth Without Pretending Append Is Always O(1)

Reach for ArrayList when you need a growable indexed list. A static T[] is the right call when the length is part of the contract (buffer, matrix row, packed bytes). Insert in the middle still slides the tail on both.

Append vs prepend

Append at the end of a dynamic array is usually cheap. Insert at the front is a slide. If the hot path is “add here, I already hold the node,” you wanted links.

Job	Structure	JDK	Post
Append, occasional grow	Dynamic array	ArrayList	Dynamic Arrays
Prepend / splice when you hold the node	Linked list	LinkedList (rarely)	Linked Lists: Singly, Doubly, and Circular Without Losing the Head

LinkedList is a real layout, not a faster ArrayList. It wins at splice. It loses at get(i). Most Java code that thought it needed a linked list needed an ArrayDeque or an ArrayList. Use the linked-list post to see the pointers; do not default to the type.

Undo, FIFO, both ends

LIFO, FIFO, and “either end” are three contracts. They are not three excuses to search a list for “the last one.”

Job	Structure	JDK	Post
Undo, matching braces, call frames	Stack	ArrayDeque	Stack: Undo, Parse, and Call Frames Are the Same Shape
FIFO, workers, circular buffer	Queue	ArrayDeque	Queue: FIFO, Circular Buffers, and Why a Naive Array Queue Rotates
Push/pop both ends	Deque	ArrayDeque	Deque: Both Ends Without Two Structures

ArrayDeque is the JDK default for all three. Do not reach for java.util.Stack or Vector because the textbook used those names. Stack is a synchronized subclass of Vector. The contract you wanted is the deque.

A naive array queue that always arraycopys on dequeue is the other trap — the queue post is that rotation story.

Unique keys and key → value

Uniqueness is not a List.contains loop with a nicer name. Lookup by key is not a scan of pairs.

Job	Structure	JDK	Post
Key → value, no order	Hash table	HashMap	Hash Tables: Buckets, Collisions, and When HashMap Lies About O(1)
Unique members, no order	Hash set	HashSet	Sets: Uniqueness Without Scanning the List

Do not use List.contains as a set. It compiles. It walks. HashMap.get is expected O(1), not a law — a broken hashCode turns the table into one fat chain. If you need insertion order, that is LinkedHashMap, not a list plus a map “to be sure.”

Ordered keys

“I need it sorted” is not one layout. A plain BST goes lopsided under sorted input. Balanced trees, skip lists, splay, and treaps are different answers to that height problem. If you do not yet know what “balanced” means, start with the shape:

Job	Structure	JDK	Post
Shape, traversals, what balanced means	Binary tree	none	Binary Trees: Shape, Traversals, and What “Balanced” Even Means
Ordered tree, no rebalance	BST	none (teaching)	Binary Search Trees: Ordered Trees That Go Lopsided Under Sorted Input
Strict height, read-heavy, you own the node	AVL	none	AVL Trees: Height Balance When You Need Strict Guarantees
Ordered map in production Java	Red-black	TreeMap / TreeSet	Red-Black Trees: The Shape Behind TreeMap and TreeSet
Concurrent ordered map	Skip list	ConcurrentSkipListMap	Skip Lists: Layers of Express Lanes Instead of Rotations
Working set is the same few keys	Splay	none	Splay Trees: Move What You Touch to the Root
BST order + random heap priority / split-merge	Treap	none	Treaps: BST Order Plus Heap Priority

Production Java with ordered keys: TreeMap. Sequential default is red-black. Concurrent and ordered is the skip list. AVL, splay, and treap are layouts you implement when the JDK type is the wrong bet — not replacements for TreeMap because the name was on a slide.

Next-best / priority

A retry queue that sorts the whole list on every insert is paying to learn who is next. You only needed the root.

Job	Structure	JDK	Post
Next-best in, next-best out	Heap	PriorityQueue	Heaps: Priority in O(log n) Without Sorting the Whole Collection

Peek is O(1). Insert and extract are O(log n). The rest of the array is unordered on purpose. If you needed a fully sorted snapshot, sort once. If you needed live “who is next,” that is the heap.

Prefix strings (and one text, many substrings)

Autocomplete that filters eighty thousand names with startsWith is a scan. A support tool that calls indexOf on the same 40 MB log twenty times is the same tax on a different job.

Job	Structure	JDK	Post
Prefix / autocomplete over many strings	Trie	none	Tries: Prefix Search Without Scanning Every String
Many substring queries on one text	Suffix array	none	Suffix Arrays: Substring Search Without a Full Suffix Tree

There is no java.util.Trie. String.indexOf is the one-shot tool. Build a trie when the dictionary is the product. Build a suffix array when the haystack is stable and the queries keep coming.

Graphs vs union-find

A graph is vertices and edges. “Are these two in the same component?” is a smaller question. Do not store an adjacency list you never walk except to ask that.

Job	Structure	JDK	Post
Neighbors, directed, weighted — pick the layout first	Graph	none (you pick list vs matrix)	Graphs: Adjacency List, Matrix, Directed and Weighted — Pick the Layout First
Same component? union these two	Union-Find	none	Union-Find: Connected Components Without Building a Graph

A dense “who follows whom” matrix of 50,000 users is two and a half billion cells to answer a forty-item question. Adjacency list first. Algorithms that walk the graph are a later category; this series stops at the representation.

Range queries

“Sum of a[L..R]” after a point update is not “rescan the slice.” Two layouts share that job with different width.

Job	Structure	JDK	Post
Arbitrary range + point (or range) update	Segment tree	none	Segment Trees: Range Queries Without Rescanning the Array
Prefix / range when the tree would be more tree than you need	Fenwick	none	Fenwick Trees: Prefix Updates When a Segment Tree Is More Tree Than You Need

No JDK type for either. Fenwick is the smaller machine when the query is a prefix (or a range you can write as two prefixes). Segment tree is the general interval machine.

Approximate membership

“Have we seen this URL?” at a scale where storing every key is the expensive part. A hash set is exact. A Bloom filter is cheaper because it is allowed to be wrong in one direction.

Job	Structure	JDK	Post
Maybe-yes, definitely-no	Bloom filter	none (BitSet + hashes, or Guava)	Bloom Filters: Maybe-Yes, Definitely-No, and Why False Positives Are the Point

False positives are the product, not a bug. If a yes must be exact, you wanted a set.

Cache eviction

Last-N sessions in memory. Request N+1 arrives. Drop the one nobody has touched — not the one that logged in first.

Job	Structure	JDK	Post
O(1) get / put / evict LRU	Hash map + doubly linked list	LinkedHashMap (accessOrder)	LRU Cache: Hash Map Plus Doubly Linked List as One Machine

A list alone cannot find the key. A map alone cannot name the victim. The machine is both. LinkedHashMap with access-order is the JDK shortcut; the post is why that shortcut works.

Disk indexes

A BST (or TreeMap) is a tree of objects in RAM. A database page is a block you pay to read. Those are not the same width.

Job	Structure	JDK	Post
Ordered index on disk / pages	B-tree (B+ in the leaves)	none — you talk to the engine	B-Trees: Wide Nodes for Disk (and Why Databases Do Not Use BSTs)

There is no java.util.BTree. In-memory ordered keys stay TreeMap. Unordered lookup stays HashMap. You do not hand-roll page-sized nodes in the service layer.

Spatial

“Show pins in this viewport” and “nearest tap” are not hash lookups. There is no exact key. A nested loop over ArrayList<Pin> is the layout that cannot skip a region.

Job	Structure	JDK	Post
Points in a plane / region queries	Quadtree / k-d tree	none	Quadtrees and k-d Trees: Space as a Tree Instead of a Nested Loop

A few hundred pins can stay a scan. Measure before you split the plane. A TreeMap ordered by latitude still leaves longitude as a leftover walk.

JDK defaults

If you already write Java, this is the translation layer. Later posts argued the details; this table keeps you from reaching for the legacy type.

Job	Reach for	Avoid as a default
Fixed-size contiguous storage	T[]	Wrapping it in a list “just in case”
Growable indexed list	ArrayList	Vector (legacy synchronized)
Stack / queue / deque	ArrayDeque	java.util.Stack; LinkedList as a queue unless you need the list API
Unique elements, no order	HashSet	List.contains as a set
Key → value, no order	HashMap	Hand-rolled arrays of pairs
Sorted keys	TreeMap / TreeSet	Sorting a HashMap on every read
Next-best element	PriorityQueue	Sorting the whole list on every insert
Insertion-ordered map / LRU	LinkedHashMap	A list of entries plus a map “to be sure”
Concurrent ordered map	ConcurrentSkipListMap	Wrapping TreeMap in a lock without measuring

Java 21 gave ordered collections a shared vocabulary (getFirst, getLast, reversed) — see Sequenced Collections. This series is the layouts underneath those interfaces.

The rest of the structures in this guide have no JDK type. That is a signal: you build them, you take a library, or you do not need them yet.

Cheat sheet

Read this as a shopping list for the hot path, not as a ranking. There is no fastest structure — only a layout whose expensive operations are ones you rarely perform.

Question:     what operation is hot, and what layout makes it cheap?
Index i:      T[] / ArrayList          — not LinkedList
Ends:         ArrayDeque               — not Stack / Vector
Unique / KV:  HashSet / HashMap        — not List.contains
Ordered KV:   TreeMap                  — ConcurrentSkipListMap if concurrent
Next-best:    PriorityQueue            — do not sort the whole list
Prefix:       trie                     — not startsWith on every string
Substring:    suffix array             — not indexOf on a stable haystack
Neighbors:    graph layout first       — list vs matrix is the choice
Same set?:    union-find               — not a graph you never walk
Range + upd:  segment / Fenwick        — not a rescan of a[L..R]
Maybe in?:    Bloom filter             — false positives are the point
LRU:          LinkedHashMap            — map + list as one machine
Disk index:   B-tree in the engine     — TreeMap is RAM, not pages
Region:       quadtree / k-d tree      — not a nested loop over pins

Do:

• Name the hot operation before you name a structure.
• Prefer the JDK type in the table unless a post named a reason not to.
• Treat HashMap as expected O(1), and measure if n is large or the hash is under your control.
• Use the roadmap glossary when a later post says “amortized” or “contiguous” without defining it.

Don’t:

• Reach for Stack, Vector, or List.contains as a set because the name matched the textbook.
• Hand-roll AVL, splay, or a treap to beat TreeMap on a mixed read/write map.
• Store uniqueness, priority, or a viewport in an ArrayList and call the method something honest.
• Memorize rotations before you can choose between a list and a hash table.

Wrap-up

The cheap operation is a property of the layout, not of the method name. Beginner jobs — index i, append, undo, FIFO, unique keys — are ArrayList, ArrayDeque, HashMap, and HashSet. Ordered keys, next-best, and graph representation are the next layer. Balanced trees, range structures, Bloom filters, LRU, suffix arrays, and spatial trees exist because a job showed up that those defaults cannot do at the size you have.

You do not need every structure on Monday. You need the habit this page is for: look at the slow method, name the hot operation, and pick the row that makes that operation cheap. The glossary and skill path stay on the Data Structures Roadmap. The twenty-six structure posts linked above are the layouts.