A login check calls activeTokens.contains(token) on every request. The method name is honest. The layout behind it is not. If activeTokens is a list of a hundred thousand strings, each request walks the list. The product feels slow. Nobody “wrote a bad algorithm.” They stored uniqueness in a shape that cannot answer uniqueness cheaply.
A data structure is a layout that makes some operations cheap and others expensive. Memorizing twenty names does not skill you up. Matching the job to the layout does.
This post is the series glossary and index: the words later posts will use without re-defining, a path from arrays to specialized trees, a JDK map for readers who already write Java, and a living table of every structure in the series. Each row is a link. The last post is a decision guide: given the hot operation, which layout.
Why layout beats a list of names
The same verb — “is this token already here?” — has a different cost depending on how the tokens sit in memory:
boolean alreadyLoggedIn(List<String> activeTokens, String token) {
return activeTokens.contains(token); // walks the list
}
boolean alreadyLoggedIn(Set<String> activeTokens, String token) {
return activeTokens.contains(token); // hashes, then checks a bucket
}Both compile. Both pass a unit test with five tokens. Only the second stays cheap when the set grows. That gap — same API, different layout, different bill — is the whole subject.
Four jobs show up constantly in backend code. Each one has a shape that fits and a shape that fights:
| Job | Cheap layout | Expensive layout |
|---|---|---|
Read index i | Array / ArrayList | Linked list |
| Undo / matching braces | Stack (ArrayDeque) | Searching a list for “the last one” |
| Unique keys, fast lookup | HashSet / HashMap | List.contains |
| Next-best item (leaderboard, scheduler) | Heap / PriorityQueue | Sort the whole collection on every insert |
You do not need every structure on day one. You need enough literacy to look at a slow method and ask what is this data doing, and what layout would make that cheap?
Terms this series will not re-teach
Read these once. Later posts link here instead of repeating them.
ADT vs implementation. An abstract data type is the contract: a queue is FIFO; a set has unique members. An implementation is the layout that delivers that contract: ArrayDeque for a queue, a hash table for a set. Confusing the two is how people reach for java.util.Stack (a synchronized subclass of Vector) when they meant “LIFO.”
Contiguous vs linked. An array sits in one block: index i is pointer arithmetic. A linked list sits in nodes: to reach the fifth element you walk four pointers. Contiguous wins at scans and random access. Linked wins at splicing when you already hold the node.
Time and space. Big-O describes how cost grows with input size n, not how many milliseconds a laptop spends on ten items. O(1) is independent of n. O(n) grows with n. O(log n) grows, but slowly — typically “cut the search space in half each step.” Space is the extra memory the structure keeps besides the payload.
Worst-case vs amortized. ArrayList.add is usually O(1), and occasionally O(n) when the backing array doubles. Averaged over a long sequence of appends, that doubling is cheap. That average is amortized O(1). Hash tables make the same kind of promise — until a bad hash function, or a load factor you ignored, turns “expected O(1)” into a walk of a long chain. Amortized is not a guarantee on the next call.
In-place. An operation that rearranges existing storage instead of allocating a second copy. Useful when n is large and you can afford to mutate.
Note: This series teaches structures — representation, operations, complexity, when not to use them. It does not run algorithm problem sets (BFS puzzles, DP, sorting contests). Graph and tree posts cover how the data is stored and the operations the layout supports. Walks, sorts, and problem-solving live in the Algorithms Roadmap.
How to read a complexity table
Every structure post will include a small table of operations. Read it as a shopping list, not as a score. There is no “fastest structure.” There is a structure whose expensive operations are ones you rarely perform.
A sketch you will see again:
Structure: dynamic array (ArrayList)
get(i) O(1)
append amortized O(1)
insert(0) O(n) — everything slides
search O(n) — unless you already know the indexWhen you pick a structure, pick it for the operation that runs in the hot path. An autocomplete box that prepends keystrokes into an ArrayList is paying O(n) on every character. A linked list would make prepend cheap and random access expensive — which is fine if you never ask for index i.
You are ready to leave this page and read a structure post when you can say, for a piece of your own code, which operation is hot and whether the current layout makes that operation cheap.
The skill path
Four stages. Stay on a stage until the “you are ready” line is true; skipping a stage is how people memorize red-black rotations without being able to choose between a list and a set.
Beginner — linear layouts and hashing
Arrays, dynamic arrays, linked lists, stack, queue, deque, then hash tables and sets. These are the shapes behind almost every Java collection you already import.
You are ready for the next stage when you can explain why ArrayList.get(i) is cheap, why LinkedList.get(i) is not, why HashMap.get is usually cheap, and when a stack is a queue with the ends swapped.
Intermediate — trees, priority, and graphs as data
Binary trees, BSTs, heaps, tries, and graph representations (adjacency list vs matrix, directed vs weighted). This is where “ordered” and “hierarchical” stop being synonyms for “sorted list.”
You are ready for the next stage when you can say what goes wrong if you insert already-sorted keys into an unbalanced BST, why a heap is not a sorted array, and why a graph is a layout before it is an algorithm.
Advanced — balanced trees, range queries, specialized layouts
AVL, red-black, B-trees, segment trees, Fenwick trees, then skip lists, Bloom filters, LRU, suffix arrays, splay trees, treaps, and spatial trees. These exist because a job showed up that the beginner layouts cannot do at the size you have: disk-backed indexes, range sums with updates, “maybe in the set,” prefix search over huge string sets, points in a plane.
You are ready for the capstone when you can name the job each of these is for, not only the rotation that keeps them honest.
Choose — match the job to the layout
The last post is a decision guide: given a job, which structure, and which JDK type if there is one. Pick the Right Structure: Match the Job to the Data Layout links every article in this series.
JDK map at a glance
If you already write Java, this is the translation layer. Later posts argue 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 | LinkedHashMap | A list of entries plus a map “to be sure” |
Java 21 gave ordered collections a shared vocabulary (getFirst, getLast, reversed). That API is covered in Sequenced Collections: First, Last, and Reversed Without the Ceremony. This series is about the layouts underneath those interfaces.
Note: HashMap is not O(1) in the worst case. It is expected O(1) with a decent hash and a load factor you respect. Hash Tables: Buckets, Collisions, and When HashMap Lies About O(1) makes that precise; do not treat the Javadoc’s “constant time” as a law of physics.
Living index
Read in skill-path order, or jump to the structure that matches the pain you have today.
Hub
| Post |
|---|
| Data Structures Roadmap: What to Learn from Arrays to Tries (this page) — glossary, skill path, JDK map |
Beginner — linear
| Structure | Post |
|---|---|
| Array (incl. 2D / matrix) | Arrays: Why Index i Is Free and Insert in the Middle Is Not |
| Dynamic array | Dynamic Arrays: Amortized Growth Without Pretending Append Is Always O(1) |
| Linked list (singly, doubly, circular) | Linked Lists: Singly, Doubly, and Circular Without Losing the Head |
| Stack | Stack: Undo, Parse, and Call Frames Are the Same Shape |
| Queue (linear, circular) | Queue: FIFO, Circular Buffers, and Why a Naive Array Queue Rotates |
| Deque | Deque: Both Ends Without Two Structures |
Beginner — hashing
| Structure | Post |
|---|---|
| Hash table | Hash Tables: Buckets, Collisions, and When HashMap Lies About O(1) |
| Set | Sets: Uniqueness Without Scanning the List |
Intermediate — trees, priority, graphs
| Structure | Post |
|---|---|
| Binary tree | Binary Trees: Shape, Traversals, and What “Balanced” Even Means |
| Binary search tree | Binary Search Trees: Ordered Trees That Go Lopsided Under Sorted Input |
| Heap / priority queue | Heaps: Priority in O(log n) Without Sorting the Whole Collection |
| Trie | Tries: Prefix Search Without Scanning Every String |
| Graph (list, matrix, directed, weighted) | Graphs: Adjacency List, Matrix, Directed and Weighted — Pick the Layout First |
Intermediate → advanced — balanced and range
| Structure | Post |
|---|---|
| AVL tree | AVL Trees: Height Balance When You Need Strict Guarantees |
| Red-black tree | Red-Black Trees: The Shape Behind TreeMap and TreeSet |
| B-tree (B+ as a section) | B-Trees: Wide Nodes for Disk (and Why Databases Do Not Use BSTs) |
| Segment tree | Segment Trees: Range Queries Without Rescanning the Array |
| Fenwick tree | Fenwick Trees: Prefix Updates When a Segment Tree Is More Tree Than You Need |
Advanced — specialized
| Structure | Post |
|---|---|
| Union-Find | Union-Find: Connected Components Without Building a Graph |
| Skip list | Skip Lists: Layers of Express Lanes Instead of Rotations |
| Bloom filter | Bloom Filters: Maybe-Yes, Definitely-No, and Why False Positives Are the Point |
| LRU cache | LRU Cache: Hash Map Plus Doubly Linked List as One Machine |
| Suffix array (tree as a variant) | Suffix Arrays: Substring Search Without a Full Suffix Tree |
| Splay tree | Splay Trees: Move What You Touch to the Root |
| Treap | Treaps: BST Order Plus Heap Priority |
| Quadtree / k-d tree | Quadtrees and k-d Trees: Space as a Tree Instead of a Nested Loop |
Capstone
| Post |
|---|
| Pick the Right Structure: Match the Job to the Data Layout |
Read in order if you are skilling up from scratch. Jump to the structure that matches the pain you have today if you already write Java and need one layout explained. Every later post assumes the glossary on this page.
Cheat sheet
Question: what operation is hot, and what layout makes it cheap?
ADT: the contract (queue = FIFO, set = unique)
Implementation: the layout (ArrayDeque, hash table)
Contiguous: index i is O(1); insert in the middle slides
Linked: splice is cheap when you hold the node; get(i) walks
Amortized: cheap on average, not on the next call
HashMap: expected O(1), not a law
JDK defaults: ArrayList, ArrayDeque, HashMap, HashSet, PriorityQueue, TreeMapDo:
- Name the hot operation before you name a structure.
- Prefer the JDK type in the table above unless you have a reason the post will name.
- Treat
O(1)on a hash table as expected cost, and measure ifnis large or the hash is under your control. - Stay on a skill-path stage until you can explain the “you are ready” line in your own words.
Don’t:
- Reach for
java.util.StackorVectorbecause the name matches the textbook. - Use
List.containsas a set and call it done. - Memorize rotations before you can choose between a list and a hash table.
- Treat this series as an algorithms contest. Representation first; puzzles later.
Wrap-up
Data structures are layouts with a bill attached. The beginner layouts — arrays, lists, stacks, queues, deques, hash tables — cover most production Java. Trees, heaps, tries, and graph representations cover ordered, hierarchical, and networked data. Balanced and specialized structures exist for jobs those layouts cannot do at size: disk indexes, range queries, approximate membership, spatial search.
Start with the glossary on this page, then take the beginner linear posts in order. The first one is arrays: why index i is free, why insert in the middle is not, and how a 2D matrix is still that same contiguous idea.