2.08Beginner6 topics12 min

Java implementation patterns

Small, repeatable Java patterns used throughout the course: static helper methods, a generic utility class, a record as a pair, custom comparators, immutable keys and the List<List<Integer>> adjacency list.

Learning goals

Write helper methods and utility classes cleanly
Use records for pairs and keys
Represent graphs with an adjacency list

Prerequisites

Objects and collectionsJava collections framework

2.08.1

Static helper methods

Put reusable operations (swap, gcd, min/max, bounds checks) in small static methods. They are easy to test and keep algorithm code readable.

A helper should do one thing and have no hidden state.

Java

1static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
2static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
3static boolean inBounds(int r, int c, int rows, int cols) { return r >= 0 && r < rows && c >= 0 && c < cols; }

2.08.2

Generic utility class

A generic utility class holds static methods that work on many types. Make it final with a private constructor so it cannot be instantiated, and use bounded type parameters to state requirements.

The JDK's Collections and Arrays follow this pattern.

Java

1final class ListUtil {
2    private ListUtil() {}
3    static <T extends Comparable<? super T>> boolean isSorted(List<T> xs) {
4        for (int i = 1; i < xs.size(); i++) if (xs.get(i - 1).compareTo(xs.get(i)) > 0) return false;
5        return true;
6    }
7    static <T> void swap(List<T> xs, int i, int j) { T t = xs.get(i); xs.set(i, xs.get(j)); xs.set(j, t); }
8}

2.08.3

Custom pair/record

Graph edges, coordinates and priority-queue entries need to bundle a few values. A record does it in one line and provides correct equals, hashCode and toString, so it also works as a map key.

Avoid using int[] as a map key: arrays use identity equality, so two arrays with equal contents are different keys.

Java

1record Point(int r, int c) {}
2Set<Point> visited = new HashSet<>();
3visited.add(new Point(1, 2));
4boolean seen = visited.contains(new Point(1, 2));   // true
5record State(int node, long dist) {}
6PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(State::dist));

2.08.4

Custom comparator

When the natural order is not what you need (sort descending, by a computed key, by several fields), create a comparator and give it a name if it is reused. Build comparators with Comparator.comparing… where possible; hand-written ones must be consistent and avoid subtraction overflow.

Wrong: (a, b) -> a - b fails for values such as Integer.MIN_VALUE and 1.

Java

1Comparator<int[]> byEnd = Comparator.comparingInt(iv -> iv[1]);   // intervals by end
2int[][] ivs = {{1, 4}, {2, 3}, {0, 9}};
3Arrays.sort(ivs, byEnd);                                           // [2,3] [1,4] [0,9]
4Comparator<String> byLenThenAlpha = Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder());

2.08.5

Immutable key

Keys in a HashMap or HashSet must not change while they are stored, because the hash code decides the bucket. Use immutable types (String, Integer, records with immutable fields). A mutable key that is modified after insertion becomes unfindable.

If you need a composite key, use a record or encode the fields into a long.

Java

1record Cell(int r, int c) {}
2Map<Cell, Integer> dist = new HashMap<>();
3dist.put(new Cell(0, 0), 0);
4long packed = ((long) 3 << 32) | 7;    // pack two ints (3, 7) into one long key
5int r = (int) (packed >>> 32), c = (int) packed;   // unpack: 3, 7

2.08.6

Adjacency list with List<List<Integer>>

A graph with n vertices numbered 0 to n-1 is stored as List<List<Integer>>, where graph.get(u) lists the neighbours of u. It uses O(V + E) memory and visits all neighbours of a vertex in time proportional to its degree. Undirected edges are added in both directions.

For weighted graphs store small records Edge(to, weight) instead of plain integers.

Java

1int n = 5;
2List<List<Integer>> g = new ArrayList<>();
3for (int i = 0; i < n; i++) g.add(new ArrayList<>());
4int[][] edges = {{0, 1}, {0, 2}, {1, 3}};
5for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
6// g = [[1, 2], [0, 3], [0], [1], []]
7record Edge(int to, int w) {}
8List<List<Edge>> wg = new ArrayList<>();

Practice ladder

Now try it yourself

Easy

Write swap and gcd helpers and test them
Create a Point record and use it in a HashSet

Medium

Sort intervals by start, then by end descending
Build an adjacency list from an edge array

Advanced

Explain why a mutable key breaks HashMap and demonstrate it

Key takeaways

Small static helpers and records keep algorithm code short.
Keys must be immutable with consistent equals and hashCode.
List<List<Integer>> is the default adjacency list.