// 第 9 周 – 在开头插入：链表 O(1) 与动态数组 O(n)
// 运行：java ListVsArray.java
import java.util.ArrayList;
import java.util.LinkedList;

public class ListVsArray {
    public static void main(String[] args) {
        System.out.println("inserting n elements at the BEGINNING (ms)");
        System.out.printf("%9s %12s %12s%n", "n", "ArrayList", "LinkedList");
        for (int n = 10_000; n <= 160_000; n *= 2) {
            ArrayList<Integer> a = new ArrayList<>();
            long t0 = System.nanoTime();
            for (int i = 0; i < n; i++) a.add(0, i);     // 每个元素都要移动：O(n)
            long t1 = System.nanoTime();
            LinkedList<Integer> l = new LinkedList<>();
            for (int i = 0; i < n; i++) l.addFirst(i);   // 只需设置指针：O(1)
            long t2 = System.nanoTime();
            System.out.printf("%9d %12.1f %12.1f%n", n, (t1 - t0) / 1e6, (t2 - t1) / 1e6);
        }

        System.out.println("\nreading the MIDDLE element n times (ms)");
        int n = 20_000;
        ArrayList<Integer> a = new ArrayList<>();
        LinkedList<Integer> l = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            a.add(i);
            l.add(i);
        }
        long t0 = System.nanoTime();
        long s = 0;
        for (int i = 0; i < n; i++) s += a.get(n / 2);   // 直接访问：O(1)
        long t1 = System.nanoTime();
        for (int i = 0; i < n; i++) s += l.get(n / 2);   // 顺序访问：O(n)
        long t2 = System.nanoTime();
        System.out.printf("ArrayList: %.1f ms, LinkedList: %.1f ms   (%d)%n", (t1 - t0) / 1e6, (t2 - t1) / 1e6, s % 10);
    }
}