Operation matrices

Index access means “give me the k-th element”. Arrays and ArrayList compute the address from the index in O(1). A linked list must walk k nodes. Hash maps and trees have no positions at all: they are addressed by key, and TreeMap cannot even report the k-th smallest key without walking.

Run the animation to see the difference between reading element 5 of an array and of a linked list.

1static int getFromArray(int[] arr, int k) {
2    return arr[k];                      // address = base + k * 4: one memory read
3}
4
5static int getFromList(Node head, int k) {
6    Node cur = head;
7    for (int i = 0; i < k; i++) {
8        cur = cur.next;                 // pointer chase: one read per hop
9    }
10    return cur.value;
11}

Inserting at the end of an array list is amortised O(1); inserting anywhere else shifts the tail, O(n). A linked list inserts in O(1) once it holds the node, but *finding* the position costs O(n). Hash tables insert in expected O(1), balanced trees and heaps in O(log n).

A sorted array is the worst for insertion: O(log n) to find the spot, then O(n) to shift. That is the price of its O(1) minimum and O(log n) search.

Deletion mirrors insertion. Removing the last element of an array list is O(1); removing from the front or the middle shifts the tail. Linked lists unlink in O(1) at either end of a doubly linked list. PriorityQueue.poll() removes the best element in O(log n), but remove(Object) must first search the heap, O(n).

Search asks whether a value or key is present. Unsorted structures must scan, O(n). A sorted array uses binary search, O(log n). Hash tables answer in expected O(1) but only for *exact* keys, and containsValue on a map is O(n). Trees answer in O(log n) and also support ordered queries.

The minimum and maximum are free in a sorted array (the two ends), cheap in a balanced tree (the leftmost and rightmost nodes, O(log n)) and, for one of them, free in a heap (the root). A hash table keeps no order, so it scans.

A heap gives only one extreme: a min-queue has the minimum at the root and finding the maximum means scanning. If you need both, use a TreeMap/TreeSet, or two heaps.

The predecessor of x is the largest value below x; the successor is the smallest above it. They answer questions such as “which meeting starts right after 14:00?”. A sorted array finds them with binary search in O(log n); TreeSet.lower/higher/floor/ceiling do it in O(log n) in a tree. Hash tables and heaps cannot answer these without scanning everything.

1static void neighbours() {
2    TreeSet<Integer> starts = new TreeSet<>(List.of(900, 1030, 1400, 1530));
3    System.out.println(starts.lower(1400) + " " + starts.higher(1400) + " " + starts.ceiling(1401));   // 1030 1530 1530
4}

A range query returns everything with a key between lo and hi. Sorted structures locate the start in O(log n) and then walk the k results: O(log n + k). Unsorted structures must test every element, O(n), even when few match.

1static List<Integer> inRange(TreeSet<Integer> set, int lo, int hi) {
2    return new ArrayList<>(set.subSet(lo, true, hi, true));           // finds lo in O(log n), then walks the results
3}