ArrayList
ArrayList内部是一个elementData的数组，该数组的默认初始化是EMPTY_ELEMENTDATA或DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组。
transient Object[] elementData;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
//初始化大小传小于0抛异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
可以看出，在初始化指定或不指定是，ArrayList的大小size=0
add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//第一次minCapacity=1，DEFAULT_CAPACITY=10
ensureExplicitCapacity(minCapacity);
}
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
ArrayList在第一次执行add的时候，会判断size + 1和DEFAULT_CAPACITY(10)的大小，所以，在第一次add的时候就进行了一次扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 第一次oldCapacity 为0
int oldCapacity = elementData.length;
//扩容大小=当前大小+当前大小/2(>>1)，为1.5倍扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//第一次扩容大小为0
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//数组超过了MAX_ARRAY_SIZE 后，大小位Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//调用Arrays.copyOf,赋值一个新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
所以在执行add的时候，如果数组大小<10就会进行扩容，所以当我们传入>=10的初始化大小即调用ArrayList(int initialCapacity)，传入>10的时候第一次将不会扩容，这里在第一次add的时候会节省性能。
add(E e)和add(int index, E element)对比
public boolean add(E e) {
ensureCapacityInternal(size + 1);
//最后一个赋值
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1);
//从当前index位置开始copy(size - index为数组index后的长度)当前数组数据并复制到index + 1
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//当前位置index赋值
elementData[index] = element;
size++;
}
由此可见，add index方法有一个arraycopy和数组挪移的过程，所以相对来说，插入效率较低，
同理，remove(int index)也是将数组前移，来达到删除的效果
remove(int index)
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//数组前移过后将最后一个位置赋值为null，并size-1来准确大小
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
数组的减容
ArrayList有扩容机制，每次扩容大小为数组大小的1.5倍，当数组的大小非常大时，那么扩容的大小就会很大，所以ArrayList提供了减容的函数，当我们已经不在为ArrayList添加数据的时候，可以调用trimToSize函数，来为ArrayList瘦身。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
所以数组的插入和删除有一个arraycopy的过程。
总结：
1.初始化ArrayList大小的时候，传入大于10的大小，可以在第一次add的时候防止扩容，可以提高插入数据的效率
2.数组每次扩容大小为1.5倍
3.ArrayList在插入和删除的时候，都会进行arraycopy的数组的挪移操作。
4.不再向数组进行插入操作时，应当进行trimToSize来为数组瘦身
5.ArrayList允许插入空值，并且会执行size++操作
6.ArrayList是线程不安全的，可以看到内部有modCount字段，这个字段，在序列化(writeObject)的时候会比较值，如果序列化前的modCount！=序列化后的modCount将抛出ConcurrentModificationException异常，这个异常是并发的异常，如果需要ArrayList这种数据结构做并发的话，有Vector，他是为每个方法加上synchronized内置锁来处理并发的，效率很低。
ArrayList插入和删除的过程
删除的位置赋值了原数组后一位的数据，原数组最后一位被赋值了null，当gc的时候将被回收。
LinkedList
LinkedList的成员变量有Node<E> first和Node<E> last，Node.class是LinkedList内部私有静态类，Node成员变量有item,next,prev
//指向第一个节点
transient Node<E> first;
//指向最后一个节点
transient Node<E> last;
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;
}
}
可以看出，每个node节点，都存储了上一个节点，当前节点，和下一个节点，所以LinkedList实际上是一个双向链接的数据结构。
上一个节点指向上一个元素的下一个节点，下一个节点指向下一个元素的上一个节点，这就是双向链表，可能有点绕，看下图
LinkedList.png
按照惯例，看看add方法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
//定义一个变量l，赋值为last，第一次add的时候last为null
final Node<E> l = last;
//new一个新的节点，传入l,e,null分别表示上一个节点，当前元素和下一个节点，所以在第一次add的时候，他的上一个节点
//和下一个节点指向均为null
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
//第一次add的时候，newNode作为链表的fist元素，目前他的上下节点都为null
first = newNode;
else
//下一次的add，则将上一个元素的next节点，赋值为新的newNode元素，而newNode的上一个节点l，就是上一个元素的
//next节点,这里有点绕，结合new Node<>(l, e, null)来细品
l.next = newNode;
size++;
modCount++;
}
所以，LinkedList的插入就是移动节点的指向，我们再看add(int index, E element)
add(int index, E element)
public void add(int index, E element) {
//检查数组越界
checkPositionIndex(index);
if (index == size)
//插入到末尾
linkLast(element);
else
//插入到中间
linkBefore(element, node(index));
}
void linkLast(E e) {
//定义变量l并赋值为最后一个节点
final Node<E> l = last;
//创建一个node节点，并且他的上一个节点为last节点
final Node<E> newNode = new Node<>(l, e, null);
//再将当前的last节点赋值为newNode节点，更新last节点
last = newNode;
if (l == null)
//如果是第一次插入，赋值first 为newNode节点，相当于创建了一个first元素，他的下一个节点为null，上一个节点也为null
first = newNode;
else
//如果不是，就将l节点(现在的last的上一个节点，也就是newNode的pre节点)的next节点赋值newNode
l.next = newNode;
//大小+1
size++;
//操作次数+1
modCount++;
}
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
linkBefore函数同理，但是linkBefore在创建时，寻找节点的位置调用了node(int index)函数
Node<E> node(int index) {
if (index < (size >> 1)) {
//如果index是小于链表长度的一半定义x变量为first元素
Node<E> x = first;
// 从first元素开始，遍历index次，将所有i位置的元素的item赋值为他的下一个节点，来达到元素节点的查找
for (int i = 0; i < index; i++)
//找到当前index位置的节点的元素
x = x.next;
return x;
} else {
//同理，这里从后面来遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
节点查找.png
接下来，就是找到了index位置的元素，就是插入当前的元素了
void linkBefore(E e, Node<E> succ) {
//获取当前index那个元素的上一个节点
final Node<E> pred = succ.prev;
//创建一个新的元素，上一个节点就是index元素的上一个节点，下一个节点就是index元素
final Node<E> newNode = new Node<>(pred, e, succ);
//改变index元素节点上一个节点，指向newNode
succ.prev = newNode;
if (pred == null)
//如果插入到头
first = newNode;
else
//插入到之中，赋值下一个节点
pred.next = newNode;
size++;
modCount++;
}
完整的插入动作
完整的插入过程.png
简单点来说，就是插入创建newNode的过程，定义prev和next时候，赋值了原来index位置的上下节点，也就是移动指针
插入过程.png
再来看get函数
get(int index)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
可见，get函数也是通过一个for循环，去循环遍历，拿到index位置的节点的item
再看删除：
public E remove(int index) {
checkElementIndex(index);
//进行node遍历查找
return unlink(node(index));
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//挪移指针
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
删除也大同小异，也就是挪移指针，将index的item=null
总结
1.LinkedList是一个双向链表，内部维护了Node节点，分别指向prev上一个节点和item当前节点，next下一个节点
2.LinkedList就插入(add(index))，删除(remove(index))，查找(get(index))都要进行循环遍历节点，去获取index位置的节点，这里采用的node函数判断了长度的一半，进行前后遍历才节省遍历时间
对比：
ArrayList：就插入，和删除，都要进行数组的System.arrayCopy操作，进行数组的挪移，插入还要校验扩容
所以相比于LinkedList，ArrayList的插入和删除效率较低，查找是根据下边查找，get(int index)
LinkedList:插入和删除只是遍历节点，改变pre，next的指向，遍历又有长度/2的优化，所有相比于ArrayList，LinkedList的插入和删除效率较高，但是查找也要遍历节点，查找性能较差。
注意：性能上只是相对，当ArrayList不进行扩容操作时，数据量又特别大时候，，链表的一半长度，和数组插入到最后几个位置，挪移的速度肯定远大于遍历/2长度的速度。
我的刀呢.jpg
网友评论