import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
 
        Integer[] array = new Integer[100000];
        Random random = new Random();
 
        for (int i = 0; i < array.length; i++)
            array[i] = random.nextInt(Integer.MAX_VALUE);
 
        LinkedList<Integer> linkedList = new LinkedList<Integer>(Arrays.asList(array));
        ArrayList<Integer> arrayList = new ArrayList<Integer>(Arrays.asList(array));
 
        long before = System.nanoTime();
 
        for (Iterator<Integer> it = linkedList.iterator(); it.hasNext(); )
            if (it.next() > Integer.MAX_VALUE / 2)
                it.remove();
 
        System.out.println((System.nanoTime() - before) / 1000);
 
        before = System.nanoTime();
 
        for (int i = 0; i < arrayList.size(); i++)
            if (arrayList.get(i) > Integer.MAX_VALUE / 2)
                arrayList.remove(i--);
 
        System.out.println((System.nanoTime() - before) / 1000);
 
        System.out.println(arrayList.equals(linkedList));
    }
 
 
    private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
        for (int integer : intArray) {
            for (int i = 0; i < list.size(); i++) {
                if (integer > list.get(i)) {
                    list.add(i, integer);
                    break;
                }
            }
        }
    }
}
 

aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuQXJyYXlzOwppbXBvcnQgamF2YS51dGlsLkl0ZXJhdG9yOwppbXBvcnQgamF2YS51dGlsLkxpbmtlZExpc3Q7CmltcG9ydCBqYXZhLnV0aWwuUmFuZG9tOwoKcHVibGljIGNsYXNzIE1haW4gewoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBFeGNlcHRpb24gewoKICAgICAgICBJbnRlZ2VyW10gYXJyYXkgPSBuZXcgSW50ZWdlclsxMDAwMDBdOwogICAgICAgIFJhbmRvbSByYW5kb20gPSBuZXcgUmFuZG9tKCk7CgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYXJyYXkubGVuZ3RoOyBpKyspCiAgICAgICAgICAgIGFycmF5W2ldID0gcmFuZG9tLm5leHRJbnQoSW50ZWdlci5NQVhfVkFMVUUpOwoKICAgICAgICBMaW5rZWRMaXN0PEludGVnZXI+IGxpbmtlZExpc3QgPSBuZXcgTGlua2VkTGlzdDxJbnRlZ2VyPihBcnJheXMuYXNMaXN0KGFycmF5KSk7CiAgICAgICAgQXJyYXlMaXN0PEludGVnZXI+IGFycmF5TGlzdCA9IG5ldyBBcnJheUxpc3Q8SW50ZWdlcj4oQXJyYXlzLmFzTGlzdChhcnJheSkpOwoKICAgICAgICBsb25nIGJlZm9yZSA9IFN5c3RlbS5uYW5vVGltZSgpOwogICAgICAgIAogICAgICAgIGZvciAoSXRlcmF0b3I8SW50ZWdlcj4gaXQgPSBsaW5rZWRMaXN0Lml0ZXJhdG9yKCk7IGl0Lmhhc05leHQoKTsgKQogICAgICAgICAgICBpZiAoaXQubmV4dCgpID4gSW50ZWdlci5NQVhfVkFMVUUgLyAyKQogICAgICAgICAgICAgICAgaXQucmVtb3ZlKCk7CiAgICAgICAgCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKChTeXN0ZW0ubmFub1RpbWUoKSAtIGJlZm9yZSkgLyAxMDAwKTsKCiAgICAgICAgYmVmb3JlID0gU3lzdGVtLm5hbm9UaW1lKCk7CiAgICAgICAgCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhcnJheUxpc3Quc2l6ZSgpOyBpKyspCiAgICAgICAgICAgIGlmIChhcnJheUxpc3QuZ2V0KGkpID4gSW50ZWdlci5NQVhfVkFMVUUgLyAyKQogICAgICAgICAgICAgICAgYXJyYXlMaXN0LnJlbW92ZShpLS0pOwoKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oKFN5c3RlbS5uYW5vVGltZSgpIC0gYmVmb3JlKSAvIDEwMDApOwoKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oYXJyYXlMaXN0LmVxdWFscyhsaW5rZWRMaXN0KSk7CiAgICB9CgoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgbGluZWFySW5zZXJ0aW9uKEludGVnZXJbXSBpbnRBcnJheSwgQXJyYXlMaXN0PEludGVnZXI+IGxpc3QpIHsKICAgICAgICBmb3IgKGludCBpbnRlZ2VyIDogaW50QXJyYXkpIHsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBsaXN0LnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgICAgICBpZiAoaW50ZWdlciA+IGxpc3QuZ2V0KGkpKSB7CiAgICAgICAgICAgICAgICAgICAgbGlzdC5hZGQoaSwgaW50ZWdlcik7CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0K