Core vocabulary

An element is one item stored in a collection: in int[] a = {4, 9, 2}, the values 4, 9 and 2 are elements. “Size” or “length” is the number of elements.

An index is an element's position. Java arrays and lists are zero-based: the first element is at index 0 and the last at length - 1. Reading outside that range throws ArrayIndexOutOfBoundsException or IndexOutOfBoundsException.

Off-by-one errors, from mixing up < with <= or the last valid index with the length, are the most common bug in this whole subject.

A key identifies an entry; a value is the data attached to it. In a map from student ID to name, the ID is the key and the name is the value. Keys are looked up and compared; values are carried along.

In sorting and searching the key is the field used for comparison, even when the whole record travels with it.

1Map<Integer, String> names = new HashMap<>();
2names.put(1042, "Ana");        // key 1042, value "Ana"
3String who = names.get(1042);  // look up by key

A node (or vertex) stores data. An edge is a connection from one node to another. Linked lists, trees and graphs are all built from nodes and edges and differ only in which connections are allowed.

A linked list node has one outgoing edge (next), a binary tree node has up to two (left, right), and a graph node may have any number.

1class Node {
2    int value;
3    Node next;       // one edge: this is a linked list node
4    Node(int value) { this.value = value; }
5}

Java has no raw pointers. A variable of object type holds a reference: the address of an object on the heap, not the object itself. Copying a reference creates a second name for the same object (an alias), so a change through either name is visible through both.

Primitives (int, double, …) are copied by value. Arrays and objects are shared by reference. Step through the animation to see exactly when two variables share one object and when they do not.

1int[] a = { 10, 20, 30, 40 };               // options 0 and 1 use this 1D array
2int[] b = a;                                // option 0: copies the reference only
3int[] b = a.clone();                        // option 1: copies the elements
4int[][] a2 = { { 10, 20 }, { 30, 40 } };    // options 2 and 3 use this 2D array
5int[][] b2 = a2.clone();                    // option 2: new outer array, SAME row objects
6int[][] b2 = Arrays.stream(a2).map(int[]::clone).toArray(int[][]::new);   // option 3: rows copied too
7b[idx] = v;                                 // (b2[0][idx] = v for options 2 and 3)
8System.out.println(Arrays.toString(a));     // does a see the change?

State is the current value of every variable that can affect what happens next. An algorithm is a sequence of state changes. Describing the state precisely after each step is what a tracing table does.

Smaller state is easier to reason about. Prefer algorithms that carry a few well-named variables over ones that depend on many interacting flags.

An invariant is a condition that stays true across a repeated step, typically at the top of each loop iteration. It is the main tool for proving an algorithm correct. In linear search, “the target is not in arr[0..i-1]” holds before every iteration.

Chapter 7 (the State and Invariants lesson) turns this into a method with worked examples, including Kadane's algorithm.

A mutable object can change after creation (ArrayList, arrays, StringBuilder). An immutable object cannot (String, Integer, records with final fields). Immutable objects are safe to share and to use as map keys; mutable ones need care.

Mutating an object that is already a key in a HashMap or HashSet changes its hash code and makes it unfindable. Always use immutable types as keys.

1String s = "cat";
2String t = s.concat("s");   // new object; s is still "cat"
3
4StringBuilder sb = new StringBuilder("cat");
5sb.append('s');            // same object changed in place

Ordered means the collection remembers an order: insertion order (ArrayList, LinkedHashSet) or sorted order (TreeSet). Unordered means there is no promised order (HashSet, HashMap). Ordered is not the same as sorted: a list is ordered by position even if its values are random.

The animation adds the same values to five collections. Compare how each one stores them: only TreeSet is sorted, and the HashSet order is an implementation detail.

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

A sort is stable if elements with equal keys keep their original relative order. Stability matters when you sort by one key and then another, such as by department and then by salary.

Merge sort, insertion sort and Java's object sort are stable. Quick sort, selection sort and heap sort are not. The demo shows equal values tagged a, b, c and what each algorithm does to their order.