Make LinkedList actually win

import java.util.*;

/**
 * Challenge: LinkedList's O(1) insertion is real. Find the access pattern where
 * you can actually use it.
 *
 * Below, both lists do the same job: insert a marker after every tenth element.
 * The LinkedList version loses badly, because index-based insertion walks the
 * chain every single time.
 *
 * Your job: rewrite the LinkedList version so it wins. The input size must not
 * change.
 */
public class Starter {

    static final int N = 40_000;

    static long ms(Runnable r) {
        long start = System.nanoTime();
        r.run();
        return (System.nanoTime() - start) / 1_000_000;
    }

    static List<Integer> filled(List<Integer> list) {
        for (int i = 0; i < N; i++) list.add(i);
        return list;
    }

    /** Index-based: every add(i, e) walks to i first. */
    static void insertMarkersByIndex(List<Integer> list) {
        for (int i = list.size() - 1; i >= 0; i -= 10) {
            list.add(i, -1);
        }
    }

    // TODO 1: write insertMarkersByIterator(List<Integer>) doing the SAME job
    // using a ListIterator: walk the list once, and call it.add(-1) at every
    // tenth position. No index arithmetic, no list.get(), no list.add(i, e).

    public static void main(String[] args) {
        List<Integer> al = filled(new ArrayList<>());
        List<Integer> ll = filled(new LinkedList<>());

        long alIndex = ms(() -> insertMarkersByIndex(al));
        long llIndex = ms(() -> insertMarkersByIndex(ll));

        System.out.println("by index      ArrayList " + alIndex + "ms, LinkedList " + llIndex + "ms");
        System.out.println("sizes match: " + (al.size() == ll.size()));

        // TODO 2: time your iterator version on a fresh LinkedList and print it
        // next to the numbers above. Is it faster than llIndex? Than alIndex?

        // TODO 3: run your iterator version on a fresh ArrayList too. ArrayList
        // also has a ListIterator. Does it help there? Explain why or why not
        // in a comment — the answer is about what add() has to do, not about
        // how you reached the position.

        // TODO 4: one comment, one sentence: the access pattern where you would
        // genuinely choose LinkedList in production code.
    }
}