文章目录

(一)复杂度分析：ArrayList
(二)复杂度分析：LinkedList
(三)均摊复杂度
 (四)ArrayList的缩容
 (五)复杂度震荡

(一)复杂度分析：ArrayList

查：get(int index)方法的时间复杂度是O(1)

    @Override
    public E get(int index) {
        rangeCheck(index);
        //假设存放的是int类型，地址值=index*4+数组的首地址
        return elements[index];
    }

数组的特点：随机访问（无论访问哪个元素）速度非常快

改：set(int index, E element)方法的时间复杂度是O(1)

    @Override
    public E set(int index, E element) {
        rangeCheck(index);
        E old = elements[index];
        elements[index] = element;//存储也是先计算地址，再存，也很快
        return old;
    }

增：add(int index, E element)方法的时间复杂度如下：
O(n)的n是数据规模，此处的数据规模是size
数组执行add方法需要向右挪动index之后的元素

最好情况复杂度（index=size）：O(1)
最坏情况复杂度（index=0）：O(n)
平均情况复杂度（0<index<size）：O[(1+2+…+n)/n]，相当于O(n/2)，即O(n)

    @Override
    public void add(int index, E element) {
        if (element == null) return;//加上就不可以存储null
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);//capacity取值为size+1，就是保证比size多一个，不怕不够用
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

删：remove(int index)方法的时间复杂度如下：
数组执行remove方法需要向左挪动index之后的元素

最好情况复杂度（index=size）：O(1)
最坏情况复杂度（index=0）：O(n)
平均情况复杂度（0<index<size）: O(n)

    @Override
    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }

总结：数组增删慢，查询、修改快

(二)复杂度分析：LinkedList

查：get(int index)方法的时间复杂度如下：

最好情况复杂度：O(1)
最坏情况复杂度：O(n)
平均情况复杂度: O(n)

    @Override
    public E get(int index) {
        return node(index).element;
    }

    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        //从first开始，next index次 就可以找到要找的结点
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

改：set(int index, E element)方法的时间复杂度如下：

最好情况复杂度：O(1)
最坏情况复杂度：O(n)
平均情况复杂度: O(n)

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        //从first开始，next index次 就可以找到要找的结点
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

增：add(int index, E element)方法的时间复杂度如下：
网上常说的链表的插入时间复杂度是O(1)指的是插入那一瞬间的复杂度是O(1)，整体的复杂度还是O(n)，因为同样调用了node(int index)方法

最好情况复杂度：O(1)
最坏情况复杂度：O(n)
平均情况复杂度: O(n)

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //要特殊处理index=0的情况
        if (index == 0) {
            first = new Node<>(element, first);
        } else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

删：remove(int index)方法的时间复杂度如下：
网上常说的链表的删除时间复杂度是O(1)指的是插入那一瞬间的复杂度是O(1)，整体的复杂度还是O(n)，因为同样调用了node(int index)方法

最好情况复杂度：O(1)
最坏情况复杂度：O(n)
平均情况复杂度: O(n)

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0) {
            first = first.next;
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
//            prev.next = prev.next.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

注意：链表的增删的瞬间，不用像数组那样挪动元素，但是从整体上来看链表的时间复杂度还是O(n)

链表的优点：省内存（用一个就创建一个，不像数组动态创建，1.5倍扩容）

(三)均摊复杂度

下面分析AbstractList类中add(E element)方法的时间复杂度

最好情况复杂度：O(1)
最坏情况复杂度：O(n)（容量不够需要扩容时）
平均情况复杂度：O(1)（因为大多数情况都是O(1)，(1+1+1+1…+n)/n，所以平均下来也是O(1)）
均摊复杂度：O(1)（绝大多数都是O(1)，只有个别少数是O(n)的情况用均摊复杂度更合适）

什么情况下适合使用均摊复杂度？
经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况

(四)ArrayList的缩容

如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
（比如剩余空间占总容量的一半时，就进行缩容）

缩容和扩容很类似，只是缩容是申请一块小一点的内存空间，然后把数组拷贝过来

我们之前是在add时增加扩容操作，现在应该在remove时增加缩容操作
我们是在add之前判断是否要扩容，现在应该在remove之后判断是否缩容

代码如下：

测试效果如下：

clear()方法也可以缩容，可以直接创建一个默认长度的数组，如下：

(五)复杂度震荡

如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡

我们现在的扩容倍数是1.5倍，如下：
我们现在的缩容时机是剩余容量大于总容量一半，如下：

接下来把扩容倍数设定为2倍，如下：

让缩容时机的判断语句在size = newCapacity时也为真

效果如下：
假设数组的默认长度为4，使用普通的add(E element)方法增加元素，复杂度为O(1)

再一次添加元素时需要扩容，复杂度为O(n)

如果此时删掉刚才添加的元素

需要缩容，复杂度为O(n)

此时又增加一个元素，又要扩容，复杂度又为O(n)…
如果一直循环这样的操作，复杂度一直维持在O(n)，这种情况叫做复杂度震荡（之前一直是O(1)，后面突然维持O(n)）