DSA: The Complete Guide

Every system I've built in payments — from ISO 20022 validators to Raft-backed settlement ledgers — is, underneath the domain logic, a handful of data structures wired together with a handful of algorithms. This is the reference I wish I'd had early on: not a list of definitions to memorize, but a working understanding of what each structure is for, what it costs, and when to reach for it. Every example is in Java 25, the language this whole site's stack is built on.

Why Data Structures and Algorithms Actually Matter

It's tempting to treat this as interview trivia — something you cram before a FAANG on-site and never think about again. In production, it shows up differently: it's the difference between a settlement service that holds its 10-second SLA at 10x load and one that falls over, because someone reached for a List.contains() (O(n)) in a hot path where a HashSet.contains() (O(1)) was sitting right there. The structures don't change; only your fluency with them does.

Big O Notation: How to Reason About Cost

Big O describes how an algorithm's cost (time or memory) grows as the input grows — not the exact number of operations, but the *shape* of the growth curve. It's the vocabulary the rest of this article is written in.

• O(1) — constant. Array index access, HashMap get/put (average case). Cost doesn't change with input size.
• O(log n) — logarithmic. Binary search, balanced tree operations. Each step eliminates half the remaining problem.
• O(n) — linear. A single pass over a list or array. Cost grows proportionally with input size.
• O(n log n) — linearithmic. Efficient comparison sorts (mergesort, heapsort, quicksort's average case).
• O(n²) — quadratic. Nested loops over the same input — bubble sort, naive duplicate detection with two loops.
• O(2ⁿ) — exponential. Naive recursive Fibonacci, brute-force subsets. Blows up fast; almost always a sign you need memoization or a different approach.

Amortized Analysis: When "Sometimes Slow" Is Still Fast

Big O usually describes a single operation, but some structures have operations that are cheap almost every time and occasionally expensive — and the honest cost is the *average over a long sequence of operations*, not the worst single one. That average is amortized cost.

ArrayList.add() is the textbook case: appending is O(1) until the backing array is full, at which point it allocates a new array (typically double the size) and copies everything over — an O(n) operation. That sounds like it makes add() O(n), but that expensive copy only happens O(log n) times over n insertions, and each element only ever gets copied a bounded number of times total. Spread across all n insertions, the average cost per add() is still O(1) — that's what "O(1) amortized" in the Arrays section earlier actually means.

Arrays

The array is the structure everything else is built from: a contiguous block of memory, indexed directly. That contiguity is exactly what makes it fast for some things and slow for others.

int[] settlements = new int[1_000];
settlements[42] = 150_00; // O(1) — direct index into a contiguous block

// Insertion in the middle means shifting everything after it — O(n)
int[] withGap = new int[settlements.length + 1];
System.arraycopy(settlements, 0, withGap, 0, 20);
withGap[20] = 999_00;
System.arraycopy(settlements, 20, withGap, 21, settlements.length - 20);

• Read by index: O(1)
• Search (unsorted): O(n)
• Insert/delete at the end: O(1) amortized (with a resizable array like ArrayList)
• Insert/delete in the middle: O(n) — everything after the gap has to shift

Linked Lists

Where an array trades flexibility for fast indexing, a linked list trades indexing for flexibility: each node points to the next, so insertion and removal are cheap wherever you already have a reference — but getting to that reference in the first place means walking the list from the start.

class Node<T> {
    T value;
    Node<T> next;
    Node(T value) { this.value = value; }
}

class SinglyLinkedList<T> {
    Node<T> head;

    void prepend(T value) {
        Node<T> node = new Node<>(value);
        node.next = head;
        head = node; // O(1) — no shifting, unlike an array
    }

    boolean contains(T value) {
        for (Node<T> curr = head; curr != null; curr = curr.next) {
            if (curr.value.equals(value)) return true;
        }
        return false; // O(n) — no random access, has to walk the chain
    }
}

• Singly linked: each node points forward only — cheap prepend, can't walk backward.
• Doubly linked (java.util.LinkedList): each node also points to its predecessor — cheap removal from the middle once you're already there, at the cost of an extra pointer per node.
• Access by index: O(n) — this is why a LinkedList is a poor substitute for an ArrayList when you're indexing into it.

Stacks and Queues

Same underlying idea — a linear sequence — with opposite access disciplines. A stack is last-in-first-out (LIFO): think of the call stack itself, or undo history. A queue is first-in-first-out (FIFO): think of a message queue processing payments in the order they arrived.

Deque<String> stack = new ArrayDeque<>();
stack.push("pacs.008 received");
stack.push("validated");
stack.pop(); // "validated" — last one in, first one out

Deque<String> queue = new ArrayDeque<>();
queue.offer("payment-1");
queue.offer("payment-2");
queue.poll(); // "payment-1" — first one in, first one out

Hash Tables

A hash table is what makes O(1) lookup possible for non-indexed data: a hash function turns a key into a bucket index, so get and put don't need to search — they compute where the value should be and go straight there.

Map<String, PaymentStatus> ledger = new HashMap<>();
ledger.put("INSTR-4471", PaymentStatus.SETTLED); // O(1) average
ledger.get("INSTR-4471");                        // O(1) average — no scan

• Average case: O(1) for get/put/contains, given a well-distributed hash function.
• Worst case: O(n) if every key collides into the same bucket — why a good hashCode() implementation matters more than it looks like it should.
• LinkedHashMap keeps insertion order at a small overhead; TreeMap keeps sorted order at O(log n) per operation via a red-black tree underneath.

Trees: Binary Trees and BSTs

A tree is a hierarchy: each node has at most a fixed number of children. A binary search tree (BST) adds an ordering invariant — everything in the left subtree is smaller, everything in the right subtree is larger — which is what turns search into a binary-search-like O(log n), *if the tree stays balanced*.

class BSTNode {
    int value;
    BSTNode left, right;
    BSTNode(int value) { this.value = value; }
}

boolean contains(BSTNode node, int target) {
    if (node == null) return false;
    if (node.value == target) return true;
    return target < node.value
        ? contains(node.left, target)
        : contains(node.right, target); // discard half the remaining tree each step
}

Tries (Prefix Trees)

A trie stores strings character by character down a tree, where every node's children are indexed by the next character — so all words sharing a prefix share the same path from the root. Autocomplete, spell-checkers, and IP routing tables all lean on this shape.

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isWord = true;
    }

    boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return false; // no word in the trie has this prefix
        }
        return true; // O(length of prefix) — independent of how many words are stored
    }
}

The payoff: checking whether *any* stored word starts with a given prefix costs O(length of the prefix) — not O(number of words) the way scanning a list or even a hash set of full words would. A HashSet can tell you if a whole word exists; only a trie can efficiently tell you if anything *starts with* it.

String Pattern Matching

Finding a substring the naive way — try every starting position, compare character by character — is O(n·m) for a text of length n and a pattern of length m. That's fine for short strings, but it's the wrong tool for searching a large log file or a genome. Two classic algorithms bring it down to O(n + m).

• Rabin-Karp — hash the pattern once, then slide a rolling hash across the text; only compare characters when the hashes match. The rolling hash is the trick: updating it for the next window is O(1), not a full recompute, because sliding the window just drops one character's contribution and adds another's.
• KMP (Knuth-Morris-Pratt) — precomputes, from the pattern alone, how far to safely skip ahead on a mismatch instead of restarting from scratch. The insight: if a mismatch happens after partially matching, you already know something about the text you just scanned — KMP is what makes sure that knowledge isn't thrown away.

Heaps and Priority Queues

A heap is a tree with a weaker invariant than a BST — only that every parent is smaller (min-heap) or larger (max-heap) than its children, not a full ordering. That's exactly enough structure to always answer "what's the smallest/largest element?" in O(1), with O(log n) insert and remove.

PriorityQueue<Integer> pq = new PriorityQueue<>(); // min-heap by default
pq.offer(50);
pq.offer(10);
pq.offer(30);
pq.poll(); // 10 — always the smallest, without a full sort

This is the structure behind Dijkstra's shortest path, behind merging k sorted streams, and behind any "process the highest-priority item next" queue — including, not coincidentally, how a real settlement engine might prioritize which pending instruction to process next under load.

Graphs

A graph generalizes a tree: nodes (vertices) connected by edges, with no restriction on cycles or hierarchy. Payment networks, service dependency maps, and the SEPA/SWIFT correspondent-banking network itself are all graphs.

Map<String, List<String>> graph = new HashMap<>();
graph.put("BankA", List.of("BankB", "BankC"));
graph.put("BankB", List.of("BankD"));

// Breadth-first search — explores level by level, finds the shortest path in an unweighted graph
Set<String> visited = new HashSet<>();
Queue<String> queue = new ArrayDeque<>();
queue.offer("BankA");
visited.add("BankA");

while (!queue.isEmpty()) {
    String node = queue.poll();
    for (String neighbor : graph.getOrDefault(node, List.of())) {
        if (visited.add(neighbor)) queue.offer(neighbor); // add() returns false if already present
    }
}

• BFS (breadth-first search): queue-based, explores nearest nodes first — the right tool for shortest path in an unweighted graph.
• DFS (depth-first search): stack-based (or recursive), goes as deep as possible before backtracking — the right tool for cycle detection, topological sort, and exploring all paths.
• Weighted shortest path: Dijkstra's algorithm (non-negative weights) — a BFS with a priority queue instead of a plain queue.

Topological Sort, Minimum Spanning Trees, and Shortest Paths

BFS and DFS are the traversal primitives; most graph problems that actually show up are one of a handful of named algorithms built on top of them.

• Topological sort — order the nodes of a directed acyclic graph (DAG) so every edge points from earlier to later. This is DFS with a twist: append each node to the front of the result only after all its dependents have been visited. It's how a build system orders compilation steps, or how a service dependency graph decides startup order.
• Minimum spanning tree (Kruskal's) — connect every node with the least total edge weight, no cycles. Sort edges by weight, add each one unless it would create a cycle (checked with Union-Find — the structure covered earlier isn't just a toy, this is its real job).
• Dijkstra's shortest path — a greedy BFS variant using a priority queue instead of a plain queue, always expanding the closest unvisited node next. Correct only for non-negative edge weights.
• Bellman-Ford — slower (O(V·E) vs. Dijkstra's O(E log V)) but handles negative edge weights, and can detect negative-weight cycles, which Dijkstra can't do at all.

// Topological sort via DFS — post-order, then reverse
static List<String> topoSort(Map<String, List<String>> graph) {
    Deque<String> result = new ArrayDeque<>();
    Set<String> visited = new HashSet<>();
    for (String node : graph.keySet()) {
        if (!visited.contains(node)) dfs(node, graph, visited, result);
    }
    return new ArrayList<>(result); // already in correct order — pushed to the front
}

static void dfs(String node, Map<String, List<String>> graph, Set<String> visited, Deque<String> result) {
    visited.add(node);
    for (String dep : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(dep)) dfs(dep, graph, visited, result);
    }
    result.addFirst(node); // this node depends on everything already placed
}

Sorting Algorithms

Java's Collections.sort()/Arrays.sort() already gives you a well-tuned sort (dual-pivot quicksort for primitives, a stable TimSort for objects) — you rarely hand-roll one in production. But knowing what's underneath explains *why* the built-in sort is fast, and lets you reason about which one to reach for when the default doesn't fit.

• Quicksort — O(n log n) average, O(n²) worst case. Picks a pivot, partitions around it, recurses. Fast in practice, not stable, worst case hits on already-sorted or adversarial input.
• Mergesort — O(n log n) guaranteed, stable. Splits, sorts each half, merges. Predictable cost, but needs O(n) extra space — why Java's object sort uses a variant of this (TimSort) rather than quicksort: correctness and stability matter more than saving that memory.
• Heapsort — O(n log n) guaranteed, in-place. Builds a heap, repeatedly extracts the max. No extra memory, but not stable and typically slower in practice than a well-tuned quicksort.
• Insertion sort — O(n²), but O(n) on nearly-sorted input. This is why production sorts switch to insertion sort for small sub-arrays (TimSort's actual runs) — the constant factor is tiny and it's genuinely fast when the data is almost in order already.

static void quicksort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) { swap(a, i, j); i++; }
    }
    swap(a, i, hi);
    quicksort(a, lo, i - 1);
    quicksort(a, i + 1, hi);
}

static void swap(int[] a, int i, int j) {
    int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}

Searching Algorithms

Linear search (O(n)) is the only option on unsorted data. The moment data is sorted, binary search turns that into O(log n) by discarding half the remaining search space on every comparison.

static int binarySearch(int[] sorted, int target) {
    int lo = 0, hi = sorted.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoids overflow vs. (lo + hi) / 2
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

The same halving idea generalizes past plain "find this value" — binary search over a *condition* (find the first index where some predicate becomes true) is one of the most underused tools in everyday problem-solving, well beyond textbook searching.

Two Pointers and Sliding Window

A huge class of array and string problems has a shape that doesn't need a new data structure at all — just two indices moving through the same array with a rule for when each one advances. It turns an apparent O(n²) (check every pair, or re-scan every window) into O(n) — one pass, no nested loop.

// Two pointers: does a sorted array contain a pair summing to target?
static boolean hasPairSum(int[] sorted, int target) {
    int lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
        int sum = sorted[lo] + sorted[hi];
        if (sum == target) return true;
        if (sum < target) lo++;   // sum too small — only a bigger left value helps
        else hi--;                 // sum too big — only a smaller right value helps
    }
    return false;
}

// Sliding window: length of the longest run without a repeated character
static int longestUniqueSubstring(String s) {
    Set<Character> window = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        while (window.contains(s.charAt(right))) {
            window.remove(s.charAt(left)); // shrink from the left until valid again
            left++;
        }
        window.add(s.charAt(right));
        best = Math.max(best, right - left + 1);
    }
    return best;
}

The tell: "contiguous subarray/substring satisfying some condition" is almost always sliding window; "pair or triplet in a sorted array satisfying some condition" is almost always two pointers moving toward each other.

Bit Manipulation

Working directly on a number's binary representation is faster than almost any other operation — no branching, no memory access beyond a register. It shows up more than it looks like it should: flags, permissions, set membership for small fixed universes, and a category of interview problems that have a one-line bitwise solution once you see it.

int flags = 0;
flags |= (1 << 3);        // set bit 3
boolean isSet = (flags & (1 << 3)) != 0; // check bit 3
flags &= ~(1 << 3);       // clear bit 3
flags ^= (1 << 3);        // toggle bit 3

// A classic: find the single number that appears once in an array where
// every other number appears exactly twice — XOR cancels out pairs.
static int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) result ^= n; // a ^ a == 0, so every pair vanishes
    return result;
}

• n & (n - 1) clears the lowest set bit — the basis of a fast "count set bits" loop and a one-line power-of-two check (n > 0 && (n & (n - 1)) == 0).
• n & -n isolates the lowest set bit — used in Fenwick trees (binary indexed trees) for range-sum queries.
• Bitmasks represent a subset of a small fixed universe as a single integer — 1 << i means "element i is in the set," which turns subset enumeration and small-set DP into integer operations instead of actual Set objects.

Recursion and Backtracking

Recursion is a function solving a problem by solving a smaller version of the same problem, with a base case that stops the descent. Backtracking is recursion with an escape hatch: try a choice, recurse, and if it doesn't pan out, undo the choice and try the next one.

static List<List<Integer>> permutations(List<Integer> nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), new boolean[nums.size()], result);
    return result;
}

static void backtrack(List<Integer> nums, List<Integer> current, boolean[] used, List<List<Integer>> result) {
    if (current.size() == nums.size()) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        current.add(nums.get(i));
        backtrack(nums, current, used, result);   // choose, explore
        current.remove(current.size() - 1);        // un-choose — the "back" in backtracking
        used[i] = false;
    }
}

Dynamic Programming

Dynamic programming is recursion plus memory: when a recursive solution recomputes the same subproblem many times, cache the result instead of recomputing it. It turns exponential blowups into polynomial time by trading memory for time — the same trade from the Big O section, just with a name of its own.

// Naive recursive Fibonacci: O(2ⁿ) — recomputes fib(n-2) inside both fib(n-1) and fib(n)
static long fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// Memoized: O(n) — each subproblem solved exactly once
static long fibMemo(int n, Map<Integer, Long> cache) {
    if (n <= 1) return n;
    if (cache.containsKey(n)) return cache.get(n);
    long result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
    cache.put(n, result);
    return result;
}

• Top-down (memoization): write the natural recursive solution, add a cache. Easiest to reason about, closest to the problem statement.
• Bottom-up (tabulation): build the answer iteratively from the smallest subproblems up, usually in an array. No recursion overhead, often the faster real-world choice.
• The tell that a problem wants DP: overlapping subproblems (the same smaller input shows up more than once) plus optimal substructure (the best answer is built from the best answers to subproblems).

Greedy Algorithms

A greedy algorithm makes the locally-best choice at each step and never reconsiders it — no backtracking, no exploring alternatives. It's fast and simple, but only correct for problems where the locally-best choice genuinely leads to the globally-best answer, which is a real constraint, not a given.

• Activity selection: always pick the next activity that finishes earliest — provably optimal for this specific problem.
• Dijkstra's shortest path: always expand the closest unvisited node next — a greedy choice that works because edge weights are non-negative (it breaks with negative weights, which is what Bellman-Ford exists for).
• Huffman coding: always merge the two least-frequent nodes — builds a provably optimal prefix-free encoding.
• The failure mode: greedy applied to a problem without that provable structure (the classic counterexample is coin change with a non-canonical coin system) silently gives a wrong answer, not a slow one — this is the one category here where "it ran and returned something" isn't evidence it's correct.

Union-Find (Disjoint Set)

Union-Find tracks a collection of non-overlapping sets and answers one question fast: are these two elements in the same set? With path compression and union-by-rank, both find and union run in near-O(1) (technically O(α(n)), the inverse Ackermann function — for any input size that could ever exist, that's effectively a small constant).

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    void union(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA == rootB) return;
        if (rank[rootA] < rank[rootB]) { int tmp = rootA; rootA = rootB; rootB = tmp; }
        parent[rootB] = rootA;
        if (rank[rootA] == rank[rootB]) rank[rootA]++;
    }
}

This is the structure behind Kruskal's minimum spanning tree algorithm, cycle detection in undirected graphs, and — closer to home — detecting whether a set of payment accounts belong to the same settlement group without walking a full graph traversal every time.

Choosing the Right Data Structure: A Cheat Sheet

The question that actually matters day to day isn't "what's the definition of a red-black tree" — it's "which structure fits the access pattern I actually have." A rough map:

• Need O(1) lookup by key, don't care about order? HashMap / HashSet.
• Need O(1) lookup and insertion order preserved? LinkedHashMap / LinkedHashSet.
• Need sorted order maintained automatically, with O(log n) operations? TreeMap / TreeSet.
• Need fast add/remove at both ends? ArrayDeque, as a stack or a queue.
• Need "give me the smallest/largest, repeatedly"? PriorityQueue.
• Need fast random access by index? ArrayList, not LinkedList.
• Need to know if two things are connected, across many merges? Union-Find.
• Need to find every stored string starting with a given prefix? Trie, not a HashSet of full strings.
• Scanning for a contiguous run/window satisfying a condition? Two pointers or a sliding window before reaching for anything heavier.
• Ordering tasks with dependencies, or finding the cheapest way to connect everything? Topological sort or a minimum spanning tree — both graph problems, neither needs brute force.
• Recomputing the same subproblem more than once? That's your signal for memoization/DP, before you optimize anything else.

Algorithms are just decisions about what work to do now versus what work to avoid doing later — every structure in this article is a different answer to that same question.