ArrayList

image.png

由上图可以看出ArrayList底层是根据数组实现的。

1、查询：

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

通过源码可以看出get方法直接根据索引到数组中查询即可，效率高

2、插入操作：

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
}

查看源码可以看出，将elementData数组中的数组从index位置复制到elementData的index + 1位置。
(相当于从index开始，数组内容往后移动一位)
elementData[index] = element;将index出的数组内容，复制给新的值，这样实现了插入操作。

可以看出插入操作需要移动数组内容，效率低。

3、添加操作：

ArrayList源码

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}


private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

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);
}

上面add的代码很简单：
ensureCapacityInternal(size + 1);这一行就是保证数组的长度要大于存储元素的长度
elementData[size++] = e;这一行就是将添加的元素赋值给了数组的下一个空间。

主要要看ensureCapacityInternal方法：

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

如果默认new ArrayList();初始化的时候是给一个长度为0的空数组，
这行主要是判断如果是空数组，默认长度为DEFAULT_CAPACITY（10）

接下来进入ensureExplicitCapacity方法
如果minCapacity最小的长度大于elementData.length（数组的长度）

进入grow方法（数组扩容）

int newCapacity = oldCapacity + (oldCapacity >> 1);这行算出新的数组长度
相当于int newCapacity = oldCapacity + (oldCapacity / 2)
也就是说newCapacity = oldCapacity * (1.5)
扩容50%的意思

elementData = Arrays.copyOf(elementData, newCapacity);创建一个新的数组并elementData（旧的数组值赋值到新的数组）并赋值给elementData。

以上代码：可以看出一旦元素的内容超过ArrayList内数组的容量，那么需要进行数组内容的移动，也是效率低的操作。

4、删除操作：

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
}

System.arraycopy(elementData, index+1, elementData, index,numMoved);这里将index+1之后的数组内容复制到elementData
相当于将index之后的数组内容往前移一位（挤掉要删除的值）

查看源码可以得知，删除操作要移动数组内容，效率低。

5、修改操作

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

查看源码可以得知，修改操作直接通过索引操作数组内容，效率高。

总结：ArrayList底层是数组结构，查询，修改效率高。增加，插入，删除效率低。

手写模拟代码：

package com.yidu.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Vector;

import org.omg.Messaging.SyncScopeHelper;
/**
 * 模拟数组集合(底层数组实现)
 * @author Administrator
 */
public class Array{
    private Object[] elementsData;
    private int size;
    //构造方法，初始化数组
    public Array(){
        this(10);
    }
    public Array(int initialCapacity){
        if(initialCapacity<1){
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        elementsData=new Object[initialCapacity];
    }
    public void add(Object obj){
        //数组扩容
        ensureCapacityInternal();
        elementsData[size++]=obj;
        
    }
    public void add(int index,Object obj){
        rangeCheck(index);
        //数组扩容
        ensureCapacityInternal();
        System.arraycopy(elementsData, index, elementsData, index+1, size-index);
        elementsData[index]=obj;
        size++;
        
    }
    public Object get(int index){
        rangeCheck(index);
        return elementsData[index];
    }
    public void remove(int index){
        rangeCheck(index);
        System.arraycopy(elementsData, index+1, elementsData, index, size-index-1);
        elementsData[--size]=null;
    }
    public void remove(Object obj){
        if(obj==null){
            for (int i = 0; i < elementsData.length; i++) {
                if(elementsData[i]==obj){
                    System.arraycopy(elementsData, i+1, elementsData, i, size-i-1);
                    elementsData[--size]=null;
                    break;
                }
            }
        }else{
            for (int i = 0; i < elementsData.length; i++) {
                if(elementsData[i].equals(obj)){
                    System.arraycopy(elementsData, i+1, elementsData, i, size-i-1);
                    elementsData[--size]=null;
                    break;
                }
            }
        }
    }
    public void set(int index,Object obj){
        rangeCheck(index);
        elementsData[index]=obj;
    }
    private void rangeCheck(int index){
        if(index>=size||index<0){
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    private void ensureCapacityInternal(){
        if(size==elementsData.length){
            Object[] newArr=new Object[size*2];
            //将旧数组拷贝到新数组
            System.arraycopy(elementsData, 0, newArr, 0, elementsData.length);
            elementsData=newArr;
        }
    }
    public static void main(String[] args) {
        Array a=new Array();
        for (int i = 0; i < 21; i++) {
            a.add(i);
        }
        System.out.println(a.size);
    }
}