ArrayList和LinkedList综合性能对比与分析
1，两个list简单概括。
ArrayList数据结构就是数组（更确切的说是动态数组）
LinkedList数据结构是双向链表。
其他信息各位自行了解，随便在哪都能搜到。这篇文章注重对性能对比。
2，添加元素
(建议大家实测)
（1）从第一个位置添加
ArrayList<Integer> arrayList=new ArrayList<>();
LinkedList<Integer> linkedList=new LinkedList<>();
int times=100000;
long t1=System.nanoTime();
for (int i = 0; i < times; i++) {
arrayList.add(0,i);
}
long t2=System.nanoTime();
for (int i=0;i<times;i++){
linkedList.addFirst(i);
}
long t3=System.nanoTime();
System.out.println("arrayList:"+(t2-t1)/1000+" linkedlist:"+(t3-t2)/1000);
结果
截屏2020-04-11下午5.42.05.png
很明显，arraylist和linkedlist相比，在第一个位置添加元素 linkedlist要快很多。
分析：
linkedlist在头部添加最终是执行的这块代码
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
由于Linked维护了头结点（first），代码内容无非就是改变引用的指向实现插入节点。插入一个元素时间复杂度为O（1）。
而arrayList在头部添加代码实现：
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++;
}
方法内第一行代码是检查index位置是否合法，第三行则是检查是否要扩容。第四行代码是通过arrayCopy方法实现插入位置及插入位置之后的的元素后移一位。第五行代码则是插入元素。由于第四行代码源码我找不到，不过既然要后移一位，插入一个时间复杂度是O（n）。
由此便可知原因。
（2），在中间随机添加元素。
测试代码：
System.out.println("随机插入测试");
//testNanoTime();
//testMillinsTime();
// ArrayList<Integer> arrayList=new ArrayList<>();
// LinkedList<Integer> linkedList=new LinkedList<>();
//先填充五个元素
for (int i = 0; i < 5; i++) {
arrayList.add(i);
linkedList.add(i);
}
//次数
int times=150000;
//开始进行中间插入测试
long t1=System.currentTimeMillis();
for (int i = 0; i < times; i++) {
arrayList.add(arrayList.size()/2,i);
}
long t2=System.currentTimeMillis();
for (int i = 0; i < times; i++) {
linkedList.add(linkedList.size()/2,i);
}
long t3=System.currentTimeMillis();
System.out.println("arraylist:"+(t2-t1)+" linkedlist:"+(t3-t2)+" 两者倍数："+(t3-t2)/((t2-t1)*1.0));
结果
截屏2020-04-15上午12.59.22.png
分析：
(如果你自己尝试的话你会惊奇的发现当插入的数量越大时，耗时倍数越趋近于40倍)
很明显arraylist在中间插入相同数量的元素反而比linkedlist快，很奇怪是吗？当我们学数据结构的时候常识告诉我们链表插入比数组快。但是注意，数据结构中的插入是单纯的考虑插入这个动作，而linkedlist，执行remove，要通过这个方法：
截屏2020-04-15上午1.04.08.png
而这个方法的源码是：
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;
}
}
if判断条件是根据index与长度的二分之一比较，以此根据使用头结点或者尾结点来定位元素位置。以此来尽可能提高效率。这个过程每定位一个元素，时间复杂度为O(n).
而arraylist依然是通过arrayCopy进行移位，然后插入。对于每次操作时间复杂度依然为O(n)。虽然时间复杂度差不多，但是，arrayCopy方法的性能比linkedList中的定位过程效率高，如果你细心测试，你会发现插入的节点越多两者耗时倍数越接近40倍。以此得出结论，在中间插入arraylist比Linkedlist效率高。
（3）, 在尾结点进行插入。
贴上测试代码：
public static void endAddtest(){
System.out.println("尾部插入测试");
testNanoTime();
testMillinsTime();
ArrayList<Integer> arrayList=new ArrayList<>();
LinkedList<Integer> linkedList=new LinkedList<>();
int times=10000000;
long t1=System.nanoTime();
for (int i = 0; i < times; i++) {
arrayList.add(i);
}
long t2=System.nanoTime();
for (int i=0;i<times;i++){
linkedList.addLast(i);
}
long t3=System.nanoTime();
System.out.println("arrayList:"+(t2-t1)/1000+" linkedlist:"+(t3-t2)/1000);
}
截屏2020-04-15上午1.23.53.png
两者差距不大（通过多次尝试依然是arraylist较快），具体原因通过以上分析很容易理解。
arraylist，里面首先判断是否扩容，然后进行插入。linkedlist直接在尾结点插入。
贴上源码，不做过多赘述。
arraylist:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
linkedlist:
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++;
}
总结：arraylist在尾结点插入比linkedlist速度略快。
3,删除节点。
删除节点与添加节点一样。不做过多赘述。
删除第一个节点，arraylist比linekdlist慢
删除中间节点和在中间添加节点结论一样，arraylist比linkedlist快。
删除最后一个节点时间复杂度时间复杂度虽然一样，但是arraylist比linkedlist略快。
4，遍历
实测，结论，
arraylist中的遍历方式耗时比较：
fori<foreach<itreator，注意，这里foreach位置不一定，有时快有时慢，与环境和list长度有关。
linkedlist遍历耗时：
fori>foreach>iterator,注意foreach同上，耗时不稳定。
（网上有种说话：foreach底层也是用迭代器。对此我没有深入研究，先且相信这个结论）
最后贴上总结论：
image.png
