java List的4种实现类-白红宇

java List的4种实现类

以下都是个人理解的描述

ArrayList

ArrayList是我们在java开发过程中最常见的一种List实现类，属于线程不安全，读取速度快的一种List实现类。也是java入门时最常用的实现类。

其中最重要的三个参数即如下代码所示，初始数组增量和一个数组

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

当然LinkedList没有预留排序接口

Stack

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

PS.

二分归并算法：

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