// 9. hét – Beszúrás az elejére: láncolt lista O(1) vs. dinamikus tömb O(n)
// Futtatás: java ListVsArray.java
import java.util.ArrayList;
import java.util.LinkedList;

public class ListVsArray {
    public static void main(String[] args) {
        System.out.println("n elem beszúrása a LISTA ELEJÉRE (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);     // minden elemet el kell tolni: O(n)
            long t1 = System.nanoTime();
            LinkedList<Integer> l = new LinkedList<>();
            for (int i = 0; i < n; i++) l.addFirst(i);   // csak mutatókat állítunk: 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("\nn-szer a KÖZÉPSŐ elem olvasása (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);   // közvetlen elérés: O(1)
        long t1 = System.nanoTime();
        for (int i = 0; i < n; i++) s += l.get(n / 2);   // szekvenciális elérés: 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);
    }
}