ArrayList的一点知识点

古巴比伦王颁布了汉谟拉比法典，刻在黑色的玄武岩，距今已经三千七百多年，你在橱窗前，凝视菜单的字眼，我却在旁静静欣赏我巩固到的知识点--ArrayList（动态列表）

扩容

ArrayList

当我们添加数据到末尾的时候，会先去确认一下需不需要扩容，扩容的话就要增加到当前容量的1.5倍，然后再把原来数据复制一份，再做正常的添加。System.arrayCopy() 如果做插入的话，会把split前后的数据分别复制到新数组里面，顺便留出位置来给需要的元素。 这里可以发现，频繁的扩容或者插入的话会非常的消耗性能，所以要是能提前预知好数据容量，还是直接在初始化的时候，把数组写死。

LinkedList

链表的扩容完全不用考虑那么多，毕竟只是把node的指向修改一下。

增删改查

array啊，就是排在一起，所以查找的话肯定是ArrayList比较快，而LinkedList就需要一个个的找了，但是鬼精的设计的Node既有pre，又有next，所以干脆get方法直接来了个二分查找。 get(index)方法返回的是nod(index).item 就是这个node

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

   private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

ArrayList的SubList

对SubList的所有操作都会变现到原来的parentList上，不信你看

   public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

fail-fast && fail-safe

这俩是数据安全的两种机制。

fail-safe 快速失败

当在迭代器Iterator遍历的过程中，对当前容器进行修改，内部modCount会和ExpectedModCount对比，由于不一致，导致数据修改失败。 这里有个点，list中只有在长度修改的时候，修改次数才会增加，修改数据不会。 一开始我想不通，为何迭代的时候不能修改长度？ arraylist的迭代器.

   private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

代码层面是因为在生成迭代器的时候就给变量赋值，所以后期修改数组长度的时候，会不一致，但是不一致能怎样呢？直到去了一趟便利店，才想明白啊，人这是为了数据安全，或者说数据的有效性。 我们在一个俩线程里面都持有了当前的list， a线程要拿出第0个位置的元素，b线程直接给删掉了，那到底改还是不改呢。所以这个就是为了数据安全。

https://blog.csdn.net/qq_31780525/article/details/77431970 这个讲的很不错。

关于遍历

RandomAccess是用来当标记的，意思是，随机访问任意下标元素都比较快。ArrayList实现了RandomAccess 遍历用for循环； LinkedList用Iterator会快一些，链表与数组的性质，你懂的。 但是，arraylist也不是傻的对不对，作者确实重写了listIterator方法，两种方式遍历相差无几，当然推荐还是for。

我做的测试：

 public class Test {
    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList(100000);
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
        LinkedList<Integer> linkedList = new LinkedList();
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }

        detectedForTime(list,"list--for--");
        detectedIteratorTime(list,"list--iterator--");
        detectedForTime(linkedList,"linkedList--for--");
        detectedIteratorTime(linkedList,"linkedList--iterator--");

    }

    static void detectedForTime(List list,String tag){
        long start = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            list.get(i);
        }
        System.out.println(tag + (System.currentTimeMillis() - start));
    }

    static void detectedIteratorTime(List list,String tag){
        long start = System.currentTimeMillis();
        Iterator iterator = list.iterator();
        while (iterator.hasNext()){
            iterator.next();
        }
        System.out.println(tag + (System.currentTimeMillis() - start));
    }
}

result:
list--for--7
list--iterator--11
linkedList--for--6552
linkedList--iterator--6

以上。