/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone {
    public static final int NUMBER_ELEMENTS = 20_000;
 
    public static double measureTime(Runnable runnable) {
        long start = System.nanoTime();
        runnable.run();
        long end = System.nanoTime();
        return (end - start) / 1e9;
    }
 
    private static void insertUsingAdd() {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < NUMBER_ELEMENTS; i++) {
            list.add(list.size() / 2, i + 1);
        }
    }
 
    private static void insertUsingIterator() {
        List<Integer> list = new LinkedList<>();
        ListIterator<Integer> iterator = list.listIterator();
        for (int i = 0; i < NUMBER_ELEMENTS; i++) {
            iterator.add(i + 1);
            if (i % 2 == 0) {
                iterator.previous();
            }
        }
    }
 
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            // разогрев
            measureTime(Ideone::insertUsingIterator);
            measureTime(Ideone::insertUsingAdd);
        }
 
        System.out.printf("iterator: %.4f seconds\n", measureTime(Ideone::insertUsingIterator));
        System.out.printf("add:      %.4f seconds\n", measureTime(Ideone::insertUsingAdd));
    }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lIHsKICAgIHB1YmxpYyBzdGF0aWMgZmluYWwgaW50IE5VTUJFUl9FTEVNRU5UUyA9IDIwXzAwMDsKCiAgICBwdWJsaWMgc3RhdGljIGRvdWJsZSBtZWFzdXJlVGltZShSdW5uYWJsZSBydW5uYWJsZSkgewogICAgICAgIGxvbmcgc3RhcnQgPSBTeXN0ZW0ubmFub1RpbWUoKTsKICAgICAgICBydW5uYWJsZS5ydW4oKTsKICAgICAgICBsb25nIGVuZCA9IFN5c3RlbS5uYW5vVGltZSgpOwogICAgICAgIHJldHVybiAoZW5kIC0gc3RhcnQpIC8gMWU5OwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgaW5zZXJ0VXNpbmdBZGQoKSB7CiAgICAgICAgTGlzdDxJbnRlZ2VyPiBsaXN0ID0gbmV3IExpbmtlZExpc3Q8PigpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTlVNQkVSX0VMRU1FTlRTOyBpKyspIHsKICAgICAgICAgICAgbGlzdC5hZGQobGlzdC5zaXplKCkgLyAyLCBpICsgMSk7CiAgICAgICAgfQogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgaW5zZXJ0VXNpbmdJdGVyYXRvcigpIHsKICAgICAgICBMaXN0PEludGVnZXI+IGxpc3QgPSBuZXcgTGlua2VkTGlzdDw+KCk7CiAgICAgICAgTGlzdEl0ZXJhdG9yPEludGVnZXI+IGl0ZXJhdG9yID0gbGlzdC5saXN0SXRlcmF0b3IoKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IE5VTUJFUl9FTEVNRU5UUzsgaSsrKSB7CiAgICAgICAgICAgIGl0ZXJhdG9yLmFkZChpICsgMSk7CiAgICAgICAgICAgIGlmIChpICUgMiA9PSAwKSB7CiAgICAgICAgICAgICAgICBpdGVyYXRvci5wcmV2aW91cygpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDEwOyBpKyspIHsKICAgICAgICAgICAgLy8g0YDQsNC30L7Qs9GA0LXQsgogICAgICAgICAgICBtZWFzdXJlVGltZShJZGVvbmU6Omluc2VydFVzaW5nSXRlcmF0b3IpOwogICAgICAgICAgICBtZWFzdXJlVGltZShJZGVvbmU6Omluc2VydFVzaW5nQWRkKTsKICAgICAgICB9CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCJpdGVyYXRvcjogJS40ZiBzZWNvbmRzXG4iLCBtZWFzdXJlVGltZShJZGVvbmU6Omluc2VydFVzaW5nSXRlcmF0b3IpKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50ZigiYWRkOiAgICAgICUuNGYgc2Vjb25kc1xuIiwgbWVhc3VyZVRpbWUoSWRlb25lOjppbnNlcnRVc2luZ0FkZCkpOwogICAgfQp9