【参考文档】
鲁班语雀ArrayList:[https://www.yuque.com/books/share/9f4576fb-9aa9-4965-abf3-b3a36433faa6/fua39n](https://www.yuque.com/books/share/9f4576fb-9aa9-4965-abf3-b3a36433faa6/fua39n)
java中的浅拷贝和深拷贝:[https://www.cnblogs.com/ysocean/p/8482979.html](https://www.cnblogs.com/ysocean/p/8482979.html)
Fail-Fast机制：[https://www.cnblogs.com/fanlinglong/p/6627393.html](https://www.cnblogs.com/fanlinglong/p/6627393.html)
一、通常ArrayList和LinkedList给人的感觉
ArrayList:读快，写慢
LinkedList:读慢，写快
二、而实际情况是什么呢？
1.先来看看ArrayList
【读分析】
ArrayList读之所以快，是因为ArrayList底层是维护的一个数组，数组在内存中是连续的，
并且每个数组元素分配的内存大小一致，所以程序在读取时只需知道数组下标，就可以
定位到数组元素的起始偏移量，读取效率相当快。
//elementData是arrylist中维护的数组
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//根据下标获取数组的元素
E elementData(int index) {
return (E) elementData[index];
}
【写分析】
创建ArrayList如果不指定长度，在add操作时，会通过Arrays.copyOf扩容到默认数组长度10，
如果写入的元素数远远大于数组长度10，那就会每隔一段时间进行一次数组扩容copy，每次扩容是原数组长度的1.5，
在扩容的时候，会进行数组copy，数组元素越多，copy所消耗的性能越大，这才是导致arraylist写操作慢的原因，如果在创建
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 void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//数组扩容
grow(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);
}
2.LinkedList分析
【读分析】
LinkedList的get(i)方法需要通过循环遍历查找i所在的节点对象，一旦涉及到循环，效率就不会
高。
有一种高效率的读取方式就是通过iterate，遍历读取，这种读取方式，只会遍历一次查找到遍历的
起点节点，后续的遍历调用iter.next()方法是通过当前节点维护的next
节点或者pre节点的指针进行循环。
【get(i)方法】
public E get(int index) {
//检查index是否合法
checkElementIndex(index);
//循环查找node返回node.item
//其中item就是我们存入的元素
return node(index).item;
}
//先判断index是跟起始节点近还是跟末尾节点近
//跟谁近就从哪头开始遍历
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
【迭代器的next()】
public ListIterator<E> listIterator(int index) { // 继承回调该方法
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned; // 使用node节点查找并缓存数据
private Node<E> next;
private int nextIndex; // 是否遍历结束
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() { // 支持前后两种遍历方法
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() { // 不带索引值的移除
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) { // 添加和重置元素值的功能
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
【写分析】
以add(str)为例，默认添加到队列末端，添加元素只是把新元素设置为
last，把新元素的prev元素设置成旧的末端元素，把旧的末端元素的
next元素设置成新元素；总之就是指针的一种切换，效率比较高。
/**
* Links e as last element.
*/
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++;
}
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
网友评论