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