性能优化-集合类(ArrayList和LinkedList)
性能优化-集合类(ArrayList和LinkedList)
集合类是日常开发经常使用的，而ArrayList和LinkedList是使用相当频繁的集合类,在面试中也是频繁出现，但是我们真的了解这里面的原理呢，
一提到这两个集合类，大多数的人都会说ArrayList的插入和删除性能优于LinkedList，而LinkedList的查找性能优于ArrayList,但是真的是这样吗？
今天我们就从数据结构，源码，以及实现原理验证一下上面的言论是否正确.
ArrayList和Vector,linkedList都继承AbstractList抽象类，而AbstractList实现了List接口,同时继承了AbstractCollection抽象类,
而ArrayList,Vector和LinkedList都有各自的实现，ArrayList和Vector都使用数组实现，LinkedList使用双向链表实现
ArrayList实现类
ArrayList实现List接口,继承了AbstractList抽象类,底层使用数组实现,实现动态扩容机制.
ArrayList实现了Cloneable接口和Serializable接口，所以实现克隆和序列化.
ArrayList还实现了RandomAccess接口，这个接口仅仅是一个空类，他的作用就是标识，只要实现了他的List接口，都可以实现快速访问。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.SerializableArrayList属性
//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//对象数组
transient Object[] elementData;
//数组长度
private int size;这三个属性没有任何的多线程关键字修饰,但是唯一特殊就是对象数组有一个transient修饰,他的作用就是该字段则标识该属性不能别序列化，但是我们发现Arraylist实现了序列化接口，这是怎么回事呢，
这是因为ArraList是基于数组实现的,而数组也是基于动态扩增的，并不是所有被分配的内存空间都存储了数据。
如果在使用外部序列化的时候,会序列化整个数组,但是为了防止序列化没有存储数据的内容空间被序列化，内部实现了两个私有方法writeObject和readObject开自我完成序列化和反序列化，从而在序列化与反序列化节省了内存，因此使用transient是为了防止外部序列化.
ArrayList新增元素
ArrayList新增元素的方法有两种，一种是直接将元素加到数组的末尾,另外一种就是添加元素到任何位置
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}两个方法的相同之处，就是在添加元素之前，先确认容量大小，如果容量够大，就不用进行扩容,如果不够,就会按照原来的数组的1.5倍大小进行扩展，扩展之后在将数组复制到新分配的内存地址.
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}当然，两个方法不同之处，添加任意位置的时候,都会进行元素的重新排序，而将元素添加数组的末尾，在没有发生扩容下,不会有元素复制排序的过程.
因此在添加大量新元素的时候，且容量不扩容的情况下,性能并不会变差.
ArrayList删除元素
删除元素和添加任意元素的方法是有些相同，Arraylist每一次删除，都会进行数组的重组，且删除越靠前的元素,数组的重组开销就越大.
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}ArrayList遍历元素
基于数组实现,所以获取元素的时候是非常快的，
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}LinkedList是如何实现的
LinkedList和ArrayList的实现差异比较大,LinkedList是基于双向链表数据结构实现的，LinkedList定义了一个Node结构，如下
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}元素内容item, 前指针prev,后指针next，有Node的节点对象连接成的双向链表,但是在1.7JDK之前是定义了一个Entry结构的header属性，默认创建一个空Entry用来做header属性,前后指针指向自己，形成一个双向链表，
而在1.7JDK之后就按照上面的node实现，但是去掉了header属性，而替代的是Node机构的first和last属性，这样做的好处就是
- first/last可以清楚的表达链表的链头和链尾
- first/last初始化LinkedList节省了new一个Entry
- first/last使删除和插入操作更加快捷
LinkedList实现类
Linkedlsit实现List接口Deque接口，同时继承了AbstractSequentialList,LinkedList既有List类型也有队列的特性，他也是想了Cloneable和Serializabe接口，同ArrayList一样可以实现克隆和序列化，但是没有实现RandomAccess,因此不能随机快速访问，且LinkedList存储的内存地址不是连续的，而是用指针实现定位不连续地址的.
LinkedList属性
transient int size = 0;
transient Node<E> first;
transient Node<E> last;上面三个属性都使用了transient修饰，说明不能被序列化，这样做是因为如果序列化不仅仅是对链头和链尾进行序列化，因此也会使用readObject和writeObject进行序列化和反序列化.
LinkedList新增新元素
默认add(E e) 是添加元素到队尾，首先是将last放到一个临时node,然后声明一个新的Node,将last引用指向新的元素，在把之前的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++;
}而LinkedList新增节点到任意位置时候，如果我们添加到两个元素之间，添加元素只会修改前后节点的前后指针,指针指向新的节点元素，索引LinkedList添加的元素的性能很明显比ArrayList好.
LinkedList删除元素
删除元素我们要进行循环遍历，如果是在链表的前半段或后半段的位置，就会在从前向后或从后向前查找，因此如果元素靠前或靠后，删除元素的效率非常高效，但是对于拥有大量元素，且删除的位置在中间，效率就比较低
LinkedList遍历元素
遍历元素和删除元素的操作基本类似，通过分前后半段循环查找对应的元素，所以这种情况找元素是非常低效的，特别是在for循环遍历的时候,每一次遍历都要遍历半个List,索引在LinkedList遍历的时候，我们可以使用iterator方式迭代遍历.
总结
- ArrayList是数组实现，而数组是一组内存空间连续的，添加到元素到头部的时候，需要重组头部以后的数据，效率较低，LinedList是基于链表实现，在添加元素的时候，如果查找的元素在前半段或后半段的时候，响应的从前或从后进行查找，因此LinkedList添加头部效率比较高
- Arraylist添加元素到中间位置的时候，也需要部分数据的重组，效率较低，但是LinkedList添加到中间位置的时候,需要遍历元素是最多的操作，效率是最低的
- 添加元素到尾部的时候，在没有扩容的情况下ArrayList效率高于LinkedList的，而LinkedList不需要查找元素，但是需要重新new一个对象，以及变化指针对象的过程，所以效率低于ArrayList
- LinkedList循环遍历每一次都会遍历整个List,所以影响遍历的效率，ArrayList是基于数组，且实现了RandomAccess，意味可以实现快速随机访问他，所以for循环效率非常高,linkelist的迭代循环和ArrayList迭代循环性能相当，所以LinkedList在切记使用for循环遍历