java List的4种实现类

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.

二分归并算法：

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