Java List类源码剖析

ArrayList

• ArrayList底层维护了一个Object类型的数组elementData[]，如果使用无参构造器创建ArrayList对象，初始elementData容量为0，第一次添加，其容量扩充为10，如需要再次扩容，则扩容为原来的1.5倍
• 主要用于查询 *** 作，增删效率低。

//自己写的代码
ArrayList arrayList = new ArrayList ();
for (int i = 0; i < 10; i++) {
    arrayList .add(i);
}
aarrayList.add(11);
//使用无参构造器创建对象时，DEFAULTCAPACITY_EMPTY_ELEMENTDATA为一个空数组，并不给定初始大小
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//我们在代码中调用ArrayList的add方法，其实调用的是这个，然后这个add方法又调用了另一个重载后的add方法
public boolean add(E e) {
    modCount++;     //modCount记录了数组的修改次数
    add(e, elementData, size); 
    return true;
}
//核心逻辑，判断是否需要扩容的逻辑，不需要便直接赋值并让size++
private void add(E e, Object[] elementData, int s) {
    //如果s(即传进来的size)与当前数组的length相等，则说明再添加的话需要扩容
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
//这里的无参函数grow又调用了重载后的grow函数
private Object[] grow() {
    return grow(size + 1);
}
//数组扩容，其实还是调用了数组的copyof方法
private Object[] grow(int minCapacity) {
    //这里的newCapacity决定了扩容后的大小
    return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity)); 
}
//决定扩容是1.5倍还是10    比如说刚开始传入的minCapacity=1，然后下一次扩容传入11
private int newCapacity(int minCapacity) { 
    // overflow-conscious code
    int oldCapacity = elementData.length; //第一次：0 		第二次：10
    int newCapacity = oldCapacity + (oldCapacity >> 1); //第一次：0     第二次：15
    if (newCapacity - minCapacity <= 0) {  //第一次：0-1<0       第二次：15-11>0
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) //此时elementData还等于默认的空集合
            return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY为10
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8      
    //如果要扩容的大小超过了最大限制，调用hugeCapacity进行扩容，否则直接返回newCapacity即可
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}
//这里newLength即为10
public static <T> T[] copyOf(T[] original, int newLength) { 
    return (T[]) copyOf(original, newLength, original.getClass());
}
//
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    //这里已经将copy数组的长度设置为了10
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]	
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //关键一步， 参数依次为原数组，srcPos，拷贝后的数组，srcPos，拷贝的长度
    //拷贝长度Math.min(original.length, newLength)，为了防止原数组很长，每次只拷贝一部分
    System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
    return copy;
}

Vector

• Vector底层也是一个对象数组，protected Object[] elementData
• Vector是线程同步的，即线程安全的，Vector类的方法带有synchronized，但效率不如ArrayList
• 使用无参构造器创建Vector对象时，直接会给定初始数组大小为10，这里与ArrayList不同，之后每次扩容2倍

//自己写的代码
Vector vector = new Vector();
for (int i = 0; i < 10; i++) {
    vector.add(i);
}
vector.add(11);
//追进去的源码
//调用无参构造器时，直接给了初始容量10
public Vector() {
    this(10);
}
//之后调用的一系列方法，与上面几乎完全一样，唯一不同的函数为newCapacity，即确定扩容后大小的函数
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;  //10
    //capacityIncrement为vector方法的属性，为了提供一个api让用户自己指定扩容的增量
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? //0>0不成立，newCapacity = 2*oldCapacity
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity <= 0) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

LinkedList

• 双向链表，存放了first和last两个结点，每个节点有prev，next，item三个属性
• 它也是线程不安全的，适合用于单线程状态
• 适合用于增删 *** 作

//自己写的代码
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
//默认删除第一个结点
linkedList.remove();
//跟进去的源码
public boolean add(E e) {
    linkLast(e);
    return true;
}
//默认向链表的最后添加结点
void linkLast(E e) {
    final Node<E> l = last;
    //新结点的prev指向l，值item为e，next指向null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    //如果l为空，说明原来链表里没有元素，直接让first也指向新添加的结点即可
    if (l == null)
        first = newNode;
    else//l不为空，则让l.next指向新添加的结点
        l.next = newNode;
    size++;
    modCount++;
}

public E remove() {
    return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    //如果删除的是空结点，则会报异常
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
//核心逻辑，将双向链表的第一个结点删除
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;  //取出内容
    final Node<E> next = f.next; //取出要删去的结点的下一个结点
    f.item = null;
    f.next = null; // help GC  GC垃圾处理机制处理
    first = next;  //把first指向后移
    if (next == null)  //如果删除后链表为空，则让last也为空
        last = null;
    else   //first指向的不为空，last不用修改，只需要则将next的prev指向设置为空
        next.prev = null;
    size--; //元素个数--
    modCount++; //修改次数++
    return element;
}