java List的4种实现类

以下都是个人理解的描述

ArrayList

• ArrayList是我们在java开发过程中最常见的一种List实现类，属于线程不安全，读取速度快的一种List实现类。也是java入门时最常用的实现类。
• 其中最重要的三个参数即如下代码所示，初始数组增量和一个数组

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData; 
    private int size;
    ...
}

• 因为ArrayList采用的是数组的方式实现，所以其取值速度快，插入碰到扩容问题时速度会减慢，主要原因可以看如下代码

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
 }
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
 private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

初始化：

1.初始化数组长度，小于零就抛出异常，传0则与不传参是一样的

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

2.Collection子类初始化，存在空指针风险，数据利用Array.copyOf进行拷贝

   public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

3.无参初始化，就是赋予一个空数组，利用扩容做初始化长度

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

最大数组长度:

0x7fff ffff(即Integer的最大长度)或0x7fff ffff – 8

数组增长：

第一次默认增长10，一般情况下向右位移一1位，即以每次以当前数据长度的0.5倍增长
当数组长度达到临界点，增长超过了0x7fff ffff -8时，数组最大长度为0x7fff ffff

sort方法:

利用Array中采用的TimSort二分归并排序方法,注意实现 Comparable接口推荐区分1,-1,0三种情况

Vector

和ArrayList基本相似，利用数组及扩容实现List，但Vector是一种线程安全的List结构，它的读写效率不如ArrayList，其原因是在该实现类内在方法上加上了同步关键字，如

    public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        return elementData(index);
    }

其不同之处还在于Vector的增长速度不同，如下

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
    private void ensureCapacityHelper(int minCapacity) {
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

可以看出Vector在默认情况下是以两倍速度递增
所以capacityIncrement可以用来设置递增速度，因此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;
    }
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    public Vector() {
        this(10);
    }

LinkedList

• LinkedList是利用内部类Node为数据单元的双向链表，同样LinkedList是线程不安全的，其具有读效率低，写效率高，操作效率高等特性，适合用于频繁add,remove等操作的List,同时可以节省一定的内存，在clear的情况下推荐使用GC回收，并且没有最大长度限制。
• 可以看出双向链表的节点操作没有扩充的拷贝操作，在这种情况下操作相对于反复扩容效率要高，但也仅是相对的，但是有大量数据操作，特别是删除等，只需要做节点的横向移动，效率是很高的。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    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++;
    }
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    ...
}

当然LinkedList没有预留排序接口

Stack

• 继承于Vector,基本特性与Vector一致，线程安全，但效率低，实际就是利用Vector抽象成栈，使之拥有后进先出的特性

PS.

二分归并算法：

就是通过二分的方式将问题拆分到原子问题，然后通过问题的解决和归并，进行排序，例如将一组随机数拆分利用二分法拆分成多组进行排序，合并时排序，合并完成后，排序也就完成了