java（ArrayList、Vector、LinkedList底层结构和源码分析）

ArrayList：

（1）允许所有元素，包含null，可以加入多个null

（2）ArrayList是由数组来实现数据存储的

（3）ArrayList基本等同于Vector，除了ArrayList是线程不完全（执行效率高），在多线程情况下，不建议使用ArrayList

源码分析

1、ArrayList中维护了一个Object类型的数组elementData

transient：该属性不能被序列化 

2、当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
//第一步，判断是否添加成功
public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
//第二步，判断是否需要扩容
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
//第三步，进入扩容
private Object[] grow() {
        return grow(size + 1);
    }
//第四步
private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
//第五步，如果是第一次无参构造器扩容，则返回默认值10，之后返回容量值的1.5倍
private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

3、如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要再次扩容，则直接扩容elementData为1.5倍（扩容方式同无参构造器基本相同）

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

Vector：

1、Vector类的定义：

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

2、Vector底层也是一个对象数组

protected Object[] elementData;

3、Vector是线程同步的，即线程安全，Vector类的操作方法带有synchronized

4、在开发中，需要线程同步安全时，考虑使用Vector

//调用无参构造器的本质还是调用其有参构造器
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

5、扩容方式与ArrayList方式基本相同，但Vector默认为二倍的扩容或指定扩容大小

private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //capacityIncrement可以指定扩容大小，默认为0
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity <= 0) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

LinkedList：

1、LinkedList底层实现了双向链表和双端队列特点

2、可以添加任意元素（可重复），包括null

3、线程不安全，没有实现同步

底层操作机制：

1.LinkedList底层维护了一个双向链表

2.LinkedList中维护了两个属性first和last分别指向首节点和尾节点

3.每个结点（Node对象）里面又维护了prev、next、item三个属性，其中通过prev指向前一个节点，通过next指向后一个节点，最终实现双向链表

4、LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高

//添加节点
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
//删除指定位置节点
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
 
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
 
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
 
        x.item = null;
        size--;
        modCount++;
        return element;
    }