fail-fast机制, ArrayList, LinkedList 简单记录

fail-fast机制：Iterator的concurrentModifiedException

• 在迭代器生成后一边读取一边修改就会出现这个问题

        Map<Integer, Integer> maps = new HashMap<>();
        maps.put(1, 2);
        maps.put(3, 1);
        Iterator<Integer> keys = maps.keySet().iterator();
        while (keys.hasNext()) {
            int tmp = keys.next();
            System.out.println(tmp);
            maps.put(tmp + 1, tmp + 1);
        }
//抛出concurrentModifiedException异常

ArrayList

• 数组做为内部存储结构
• 寻址操作的时间复杂度为O(1)
• 为什么ArrayList实现了RandomAccess并且RandomAccess是空的？因为RandomAccess是标记函数，标记函数就是jvm中标记这个接口可以实现但没有提供任何的实现。
• 查找时间复杂度：O(1)；插入和删除时间复杂度：O(n)
• 扩容是如何实现的：内部自动实现的，把容量扩充为之前的1.5倍，然后拷贝Arrays.copyOf方法。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

LinkedList

• 双向链表作为内部的存储结构
• 查找 + 插入/删除的时间复杂度：O(n)
• 头尾插入或者删除的时间复杂度：O(1)

LinkedList和ArrayList的区别

1、底层数据结构不同；一个是数组，一个是链表；
2、适用场景 不同，ArrayList适合用于寻址操作，LinkedList适用于头尾删除。