Classifying data structures

Primitive types (int, long, double, char, boolean, …) hold a single value directly. Non-primitive (reference) types such as arrays, String and collections are objects that hold references and have methods.

Collections cannot store primitives, only their wrappers (Integer, Long), so List<int> does not compile and List<Integer> boxes every value. That boxing has a real memory and time cost, covered in Chapter 4.

In a linear structure each element has at most one predecessor and one successor: arrays, linked lists, stacks and queues. In a non-linear structure an element can connect to several others: trees and graphs.

Linear structures are traversed from one end. Non-linear ones need a traversal strategy (depth-first or breadth-first).

A static structure has a fixed size chosen at creation: a Java array. A dynamic structure can grow and shrink: ArrayList, LinkedList, HashMap.

Dynamic does not mean free. An ArrayList is built on an array that it replaces with a bigger one when full; Chapter 4 shows why that still costs O(1) per append on average.

1int[] fixed = new int[5];            // length is 5 forever
2List<Integer> grows = new ArrayList<>();
3for (int i = 0; i < 1000; i++) grows.add(i);   // size changes as needed

Contiguous structures (arrays) keep elements next to each other in memory, so element k is at base + k × size: one calculation, one read, and CPU caches love it. Linked structures keep elements in separate objects joined by references, so reaching element k means following k links.

In exchange, a linked list can insert or remove at a known node in O(1) without shifting anything. Run the animation in both modes to count memory reads.

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}

A homogeneous structure holds one element type (int[], List<String>). A heterogeneous one mixes types: a record or class with different fields, or List<Object>.

Prefer homogeneous collections of a well-chosen element type, and put mixed data into a class or record so the compiler can check it.

1int[] scores = {90, 85, 77};                       // homogeneous
2record Student(String name, int grade) {}          // heterogeneous fields in one type
3List<Student> roster = List.of(new Student("Ana", 9));

An ephemeral structure is changed in place; the old version is gone. A persistent structure keeps every earlier version available, usually by sharing unchanged parts between versions instead of copying them.

A persistent linked list shows the idea: adding at the front creates one new node whose next points at the old list, so both versions coexist.

1record Cons(int head, Cons tail) {}
2Cons a = new Cons(3, new Cons(2, null));   // [3, 2]
3Cons b = new Cons(9, a);                   // [9, 3, 2]: shares all of a
4// a is unchanged and still [3, 2]; b adds one node

A mutable structure can be modified after construction; an immutable one cannot, so it is safe to share across threads and to use as a key. List.of, Set.of and Map.of create immutable collections that throw UnsupportedOperationException on modification.

Immutability costs copying when you want a changed version, which is why persistent structures share parts.

1List<Integer> fixed = List.of(1, 2, 3);
2// fixed.add(4);                        // throws UnsupportedOperationException
3List<Integer> editable = new ArrayList<>(fixed);
4editable.add(4);                        // fine: a mutable copy