ArrayList
Java的ArrayList是一个动态扩容的数组，开发中最常用的数据结构之一；
特点
1.具有数组的快速随机访问能力，根据索引查找访问元素只需O(1);
2.ArrayList中的操作不是线程安全的，多线程请考虑Vector或者CopyOnWriteArrayList.
3.关于ArrayList重点关注下新增元素引起的扩容或者删除、插入元素引发的数组元素移位逻辑：
//先看下数组的末尾追加add函数如何处理扩容：
public boolean add(E e) {
//新增元素首先需要计算当前数组的容量是否够再塞入一个元素(size为当前数组实际元素个数)
ensureCapacityInternal(size + 1);
elementData[size++] = e; //容量保证之后，直接末尾新增
return true;
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//这里的判断体现了默认构造的数组初始容量为DEFAULT_CAPACITY=10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//数组没有足够的空间，需要调用grow扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 扩容逻辑是每次增加原有容量的一半即到1.5*oldCapacity；
* 1.5倍还是不够则直接扩容到申请的minCapacity大小，最后安全判断容量是否超出上限
*/
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);
}
//最终使用Arrays copyOf函数，创建新容量的数组并且将原有数组整个copy到新数组
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
//再看下数组指定位置插入：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//前面容量保证逻辑跟上面一致
//多一次copy为将index及其后的所有元素，整体后移到index+1，空出index这个位置给新增元素
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//删除元素对象，会使用元素的equal方法进行比较查找
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
ArrayList总结：
ArrayList默认构造容量为10，可指定容量构造或者通过集合构造相应容量的数组；
新增元素可能引起的扩容逻辑：尝试1.5倍扩容，若是1.5倍依然够则直接扩容到新增元素所需的最小容量，扩容引发创建新的容量大小数组并且将数组元素整体copy到新数组的开销。
删除或者指定位置新增：引发额外的数组元素整体copy移位开销。
删除元素对象使用equal方法进行比较.
LinkedList
LinkedList也是非常常用的数据结构，在java的实现是一个双向的链表：
LinkedList结构图
1.双向链表，快速增删，查询&随机访问效率低
2.线程不安全
3.遍历操作，推荐使用foreach & 迭代器Iterator遍历，get(int index)效率低
//从节点的结构看出来包含next、prev两个分别指向前一节点和后一节点的引用可以看出LinkedList是一个双向链表的实现.
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;
}
}
//持有了链表的头结点、尾结点方便快速访问操作链表的头、尾
transient Node<E> first;
transient Node<E> last;
linkList.addFirst(e);
linkList.addLast(e);
linkList.removeFirst();
linkList.removeLast();
linkList.getLast();
linkList.getFirst();
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
//看下指定位置插入node的实现：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//这个node(index)函数返回index处的node节点
Node<E> node(int index) {
//如果index<0.5*size从头结点往后查找,否则从尾结点往前查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
为何通过get(index)效率低？
//对于数组使用这种for + i的遍历非常常见而且也没啥毛病，数组随机索引访问O(1)
for(int i=0; i<length; i++) {
arrayList[i];
}
//若是用于LinkedList，看看linkedList的get(i)实现就会发现每次都需要从头指针或尾指针开始往计算索引值，list越长效率越低
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
foreach在编译的时候编译器会自动将对for这个关键字的使用转化为对目标的迭代器的使用
三种遍历方式效率分析：https://www.cnblogs.com/gsm340/p/9243916.html
LinkedList总结：
LinkedList就是一个线程不安全的双向链表，并且记录了链表的头和尾，提供了大量的头和尾的操作方法。在首位节点插入、删除时间复杂度O(1)，指定位置插入或者访问查找指定元素都需要O(n)
