List: ArrayList, LinkedList, Vector, Stack

ArrayList: an array that regrows

Start with what an ArrayList has to do. It has to hold things in order, let you reach any position quickly, and keep working when you add more things than it currently has room for.

It does all of that with a single array. When the array fills up, the ArrayList makes a bigger one and copies everything across. You built this by hand in the Section 4.2 exercises, so you already know what’s happening inside.

ArrayList.get(3) delegates to indexed access in its backing array. It does not walk positions 0, 1, and 2 first, so the operation is constant time whether the list holds ten items or ten million. Mainstream JVMs also lay out array elements compactly, which often gives an ArrayList good cache locality. That physical layout is an implementation observation, not a raw-address guarantee in Java source.

That same packing costs you at the front. Inserting at position 0 means every other element has to shift one place to the right to make room.

LinkedList: nodes joined by references

A LinkedList solves the same problem in a different way, and it starts from a different worry. What if you don’t want to shift anything when you insert?

So it doesn’t keep the elements together at all. Each element sits in its own small object, called a node. Each node holds the value and a reference to the next node. Java’s version is doubly linked, which means each node points backwards as well as forwards.

Now inserting between two nodes costs three reference changes and no shifting at all. Nothing moves.

You pay for that somewhere else. There are no positions to calculate any more, so reaching position 5000 means starting at the front and following 5000 references, one at a time.

Answer from memory before opening the explanation. Then compare your rule with the answer and revisit the example if they differ.

1. "LinkedList is better when you add a lot." Measure adding a million items to the end of each. What actually happens?

   Show the answer

   ArrayList wins. Measured on a normal machine, a million additions at the end took about 30 ms for ArrayList and about 53 ms for LinkedList.

   That surprises people, because an ArrayList sometimes has to copy its whole array. But it only does that a handful of times. Each new array is roughly double the last one, so a million additions cause around twenty copies. Copying a block of memory is something processors are very good at.

   Meanwhile a LinkedList makes a new node object for every single element. A million elements means a million objects, each one with a header and two references, scattered around the heap.

   LinkedList does win at adding to the front, where it's about 30 times faster. That's a much narrower claim than the folklore, and it's the true one.

2. Why is `Stack extends Vector` considered a design mistake?

   Show the answer

   Because it makes a stack a List, and a stack shouldn't be one.

   A stack does exactly one job. The last item you put in is the first item you take out. You add to the top and you remove from the top, and you never reach into the middle.

   Because Stack extends Vector, it inherits every List method, including the ones that reach into the middle. So stack.add(0, 99) inserts at the bottom, and stack.get(0) reads past the top. Both of those defeat the point of having a stack.

   This is the substitution test from Section 7.1 failing. Inheritance was used to borrow code, not because a stack really is a kind of list. Use ArrayDeque instead. It has push and pop and no get(i) at all.

3. When is a `LinkedList` genuinely the right choice?

   Show the answer

   Rarely, and the honest answer is worth saying plainly. Most of the time ArrayList is the right choice, and people reach for LinkedList out of habit rather than from measuring.

   It wins when you add and remove at the ends often and almost never look things up by position. A queue is the classic case.

   Even then, ArrayDeque is usually faster, because it uses one array instead of a million small node objects.

   The trap is thinking "I insert in the middle a lot, so I'll use a LinkedList". Inserting in the middle of a LinkedList means finding the middle first, and that walk is the expensive part. You gain nothing.

Write each solution in VS Code, predict its result, and then run the checks. Reading an example does not replace implementing it.

4 exercises100 pointsabout 105 minutes

class Folklore {
    static long time(Runnable r)
    static long timeRandomAccess(List<Integer> l, int rounds)
    static long timeAddFront(List<Integer> l, int rounds)
    static long timeAddEnd(List<Integer> l, int rounds)
}

import java.util.*;

public class Folklore {

    static long time(Runnable r) {
        return 0; // TODO
    }

    // Read the middle element, rounds times.
    static long timeRandomAccess(List<Integer> l, int rounds) {
        return 0; // TODO
    }

    // add(0, i), rounds times.
    static long timeAddFront(List<Integer> l, int rounds) {
        return 0; // TODO
    }

    // add(i), rounds times.
    static long timeAddEnd(List<Integer> l, int rounds) {
        return 0; // TODO
    }

    public static void main(String[] args) {
        // Predict all three comparisons BEFORE running.
        // TODO: get(n/2) 20_000 times on a 100_000 element ArrayList and LinkedList
        // TODO: add(0, i) 40_000 times on fresh lists
        // TODO: add(i) 1_000_000 times on fresh lists
    }
}

class BrokenStack {
    static List<Integer> stackBottomInsert()
    static int stackReadBottom()
    static List<Integer> stackIterationOrder()
    static List<Integer> dequeIterationOrder()
}

import java.util.*;

public class BrokenStack {

    // Push 1, 2, 3. Then insert 99 at the BOTTOM. Return the whole thing as a list.
    static List<Integer> stackBottomInsert() {
        return List.of(); // TODO
    }

    // Push 1, 2, 3. Then read the bottom element WITHOUT popping.
    static int stackReadBottom() {
        return 0; // TODO
    }

    // Push 1, 2, 3. Return the order a for-each loop gives you.
    static List<Integer> stackIterationOrder() {
        return List.of(); // TODO
    }

    // Same three pushes on an ArrayDeque. Return the order it gives you.
    static List<Integer> dequeIterationOrder() {
        return List.of(); // TODO
    }

    public static void main(String[] args) {
        // TODO: print all four and compare the last two carefully
        // TODO: state the substitution test and say exactly how Stack fails it
    }
}

class Views {
    static List<String> setThroughView(List<String> units)
    static List<String> clearThroughView(List<String> units)
    static String touchAfterResize(List<String> units)
    static List<String> realCopy(List<String> units)
}

import java.util.*;

public class Views {

    // subList(1, 4), then set(0, "CHANGED"). Return units.
    static List<String> setThroughView(List<String> units) {
        return units; // TODO
    }

    // subList(1, 4), then clear(). Return units.
    static List<String> clearThroughView(List<String> units) {
        return units; // TODO
    }

    // subList(1, 4), then add something to units, then touch the sublist.
    // Return "ok" or "ConcurrentModificationException".
    static String touchAfterResize(List<String> units) {
        return "ok"; // TODO
    }

    // A real copy of subList(1, 4). Change the copy. units must not move.
    static List<String> realCopy(List<String> units) {
        return List.of(); // TODO
    }

    public static void main(String[] args) {
        // TODO: run all four and watch what leaks into the original
    }
}

class Workloads {
    static long time(Runnable r)
    static long timeRandomAccess(List<Integer> l, int rounds)
    static long timeQueue(Deque<Integer> q, int rounds)
    static long timeInsertFront(List<Integer> l, int rounds)
    static long timeWalk(Iterable<Integer> l, int rounds)
    static String bestFor(String workload)
}

import java.util.*;

public class Workloads {

    // A. Load 200,000 units once, then look up by position constantly.
    // B. A job queue: add at the end, remove from the front, forever.
    // C. Build a roster by inserting each new unit at the front.
    // D. Walk the whole roster repeatedly, never touching positions.

    static long time(Runnable r) {
        return 0; // TODO
    }

    static long timeRandomAccess(List<Integer> l, int rounds) {
        return 0; // TODO
    }

    // Add at the end every round. Once the queue passes 100, remove from the front.
    static long timeQueue(Deque<Integer> q, int rounds) {
        return 0; // TODO
    }

    static long timeInsertFront(List<Integer> l, int rounds) {
        return 0; // TODO
    }

    static long timeWalk(Iterable<Integer> l, int rounds) {
        return 0; // TODO
    }

    // "A", "B", "C" or "D" -> ArrayList, LinkedList or ArrayDeque.
    static String bestFor(String workload) {
        return "unknown"; // TODO: answer after you have measured
    }

    public static void main(String[] args) {
        // TODO: predict each winner, then measure all four
    }
}