ArrayList和LinkendList不是我们想的那样？
ArrayList和LinkendList不是我们想的那样？
戳这里，加关注哦～
集合作为我们日常开发中最常用的存储数据的容器，是开发过程中使用最频繁的对象类型之一，但是有多种集合类型，不同的集合类型的实现方式不同，使用的场景也不同。这里就比较一下ArrayList和LinkedList。
先通过一张图了解一下List集合类的接口和实现关系：
ArrayList、Vector和LinkedList集合都继承了AbstractList抽象类，然后AbstractList实现了List接口，同时继承了AbstractCollection抽象类。ArrayList、Vector和LinkedList各自的需求分别实现各种的功能。
ArrayList
ArrayList的实现：
先通过一个类图看一下ArrayList的继承关系:
ArrayList实现了List接口，继承了AbstractList抽象类，底层是数组实现的，并且实现了自增扩容数组大小。还实现了Cloneable接口he Serializable接口，所以它可以实现克隆和序列化。还实现了RandomAccess接口，这个接口通过代码我们可以发现是一个空接口，其实这个接口是一个标志接口，标志着实现了该接口的List类都能实现快速随机访问。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}ArrayList主要的几个属性：
//默认的初始化容量
private static final int DEFAULT_CAPACITY = 10;
//对象数组
transient Object[] elementData;
//数组长度
private int size;这里面的elementData对象数组被transient关键字修饰，就表示该属性不会被序列化。但是前边也说了ArrayList实现了Serializable接口实现了序列号，这个地方有不序列化，这就还得从ArrayList是基于数组实现的说起，由于ArrayList会动态扩容，所以并不是所有被分配的内存空间都存储了数据。
如果采用了外部序列化实现数组的序列化，会序列化整个数组，ArrayList为了避免这些没有存储数据的内存空间被序列化，内部提供了两个私有方法writeObject和readObject来自己完成序列化和反序列化，从而在序列化和反序列化的数组时节省了空间和时间。
ArrayList的构造函数：
ArrayList 类实现了三个构造函数，第一个是创建 ArrayList 对象时，传入一个初始化值；第二个是默认创建一个空数组对象；第三个是传入一个集合类型进行初始化。
//第一种：传入一个初始化值
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);
}
}
//第二种：默认创建一个空数组对象
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//第三种：传入一个集合类型进行初始化
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}当ArrayList新增元素时，会先判断存储的元素是否已经超过其已有大小，如果超过会计算元素大小后再进行动态扩容，数组的扩容导致整个数组进行一次内存复制，所以在初始化的时候可以通过第一个构造函数指定一个合理的初始化大小，这样可以减少数组的扩容次数，提高系统的性能。
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遍历元素：
由于ArrayList是基于数组实现的，所以随机获取元素的时候非常快。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}LinkedList：
虽然LinkedList和ArrayList都是List类型的集合，但是他们的实现方式还是差别很大的。
LinkedList的实现：
LinkedList是实现了List接口、Deque接口，同时继承了AbstractSequentialList抽象类，LinkedList既实现了List类型又有Queue类型的特点；LinkedList也实现了Cloneable和Serializable接口，可以实现克隆和序列化。
Linked是基于双向链表数据结构实现的，存储数据的内存地址是不连续的，是通过指针来定位不连续地址，因此LinkedList不支持随机快速访问，所以LinkedList不能实现RandomAccess接口。
LinkedList定义了一个Note结构，Node结构中包含了3个部分：元素内容item、前指针prev以及后指针next
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;
}
}LinkedList就是由Node结构对象连接而成的一个双向链表，在JDK1.7之前，LinkedList中只包含一个Entry结构Entry，用来做header，前后指针指向自己，形成一个循环双向链表。
在JDK1.7以后，LinkedList做了一个大的优化，链表的Entry结构换成了Node，内部组成基本没有改变，但是LinkedList里面的header属性去掉了，新增了一个Node结构的first属性和Node结构的last属性。这个改动的好处：
- first/last 属性能更清晰地表达链表的链头和链尾概念；
- first/last 方式可以在初始化 LinkedList 的时候节省 new 一个 Entry；
- first/last 方式最重要的性能优化是链头和链尾的插入删除操作更加快捷了。
LinkedList属性：
transient int size = 0;
transient Node<E> first;
transient Node<E> last;LinkedList中有两个重要的属性first和last属性，还有一个size属性。并且这三个属性都被transient关键字修饰，不能被序列化，因为我们在序列化的时候不会只对头尾进行序列化，所以LinkedList也是有自己的readObject和writeObject进行序列化和反序列化。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}Linked新增元素：
LinkedList添加元素的方式有很多，默认是将元素添加到链表的末尾，首先将last元素置换到临时变量中，生成一个新的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也是支持将元素添加到任意位置的，将元素添加到任意两个元素的中间，只会改变前后元素的前后指针，指针将会指向添加的新元素，所以比ArrayList的添加操作性能优势明显。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
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++;
}LinkedList删除元素：
在LinkedList删除元素的操作中，我们需要先通过循环找到要删除的元素，如果要删除的元素处于List的前半段，就从前往后找，如果位置处于后半段，就从后往前找。这样做如果要删除的元素比较靠前或者比较靠后的效率也非常高，但是如果List中的元素非常多，移除的元素又在中间部分，那效率就相对比较低。
LinkedList遍历元素：
LinkedList的获取元素的操作和删除元素的操作基本类似，都是分前后半段循环查找对应的元素，但是通过这个方法来查询元素是非常低效的，特别是for循环遍历的时候，每一次循环都要遍历半个List。
所有在遍历LinkedList的时候，推荐使用iterator方法迭代，直接拿到我们需要的元素，而不是通过循环查找的方法。
到这里我们对于ArrayList和LinkedList有了深入的了解，那么我们之前说的“ArrayList遍历效率高，LinkedList新增和删除效率高“ 这句话真的是对的吗？
我们可以做几个小实验：
- ArrayList和LinkedList新增元素操作测试(考虑三种不同的情况：从头部新增、中间新增、尾部新增)
结果（花费时间）：
- 从集合头部位置新增元素 ArrayList>LinkedList
- 从集合中间位置新增元素 ArrayList<LinkedList
- 从集合尾部位置新增元素 ArrayList<LinkedList
这里我们就可以看到LinkedList添加元素的效率未必高于ArrayList。这是由于ArrayList是基于数组实现的，而数组在内存中是一块连续的内存空间，从头部位置新增元素的时候需要对数据进行复制重排，所以导致效率不高，而LinkedList是基于链表实现的，在添加元素的时候，我们都知道从链表的两端插入是非常高效的。
从中间添加元素的时候，我们知道ArrayList需要对部分数据进行复制重排，效率不是很高，但是LinkedList将元素添加到中间位置是添加元素效率最低的，我们知道靠近中间位置在添加元素之前的循环查找是遍历元素最多的操作，这就影响了LinkedList插入元素到中间的效率。
从尾部添加元素的操作测试中，我们发现如果不需要扩容的情况下，ArrayList的效率比LinkedList的效率高，这是因为ArrayList从尾部添加元素的时候不需要重排数据，效率非常高，而LinkedList虽然也不用循环查找，但是LinkedList 中多了一个new对象以及变换指针指向对象的操作，这就导致效率低于ArrayList，这里的测试是基于ArrayList初始化容量足够，如果集合需要动态扩容，这里面就牵涉到了数据的复制重排，ArrayList的效率也会降低。
- ArrayList和LinkedList删除元素操作测试（也是测试三种不同的情况）
结果：
- 从集合头部位置删除元素 ArrayList>LinkedList
- 从集合中间位置删除元素 ArrayList<LinkedList
- 从集合尾部位置删除元素 ArrayList<LinkedList
删除元素和添加元素的原理相近，所以测试的结果是基本一致的
- ArrayList和LinkedList遍历元素操作测试
这里分别使用for(;;)循环和迭代器迭代循环
结果：
- for(;;)循环 ArrayList<LinkedList
- 迭代器迭代循环 ArrayList≈LinkedList
这里我们可以看到LinkedList使用for循环的时候效率是最低的，ArrayList使用for循环效率是最高的，这里面的原因就是因为LinkedList是基于链表实现的，在使用for循环的时候，每一次for循环都会遍历半个List，这就严重影响了遍历的效率，ArrayList是基于数组实现的，并且是实现了RandomAccess接口标志，所以ArrayList可以实现快速随机访问，所以for循环的效率非常的高。
综上，我们在遍历LinkedList的时候切忌使用for循环。
腾讯云开发者
