Arraylist

底层是基于动态数组

根据下标访问数组元素的效率高，向尾部添加元素的效率高
删除数组中元素以及向数组中间添加数据的效率低，因为需要移动数组
最坏情况是删除第一个元素，那就要把第2-第n个元素都往前移动一位

之所以称之为动态数组，是因为Arraylist在数组容量超过上限后可以扩容（JDK1.8之后数组扩容后是之前的1.5倍）
Arraylist源码中最大的数组容量是Integer.MAX_VALUE-8，对于空出的8位，目前解释是：①存储Headerwords；②避免一些机器内存溢出，减少出错几率，所以少分配③最大还是能支持到Integer.MAX_VALUE（当Integer.MAX_VALUE-8依旧无法满足需求时）

Linkedlist

Linkedlist基于链表的动态数组

数据添加删除效率高，只需要改变指针指向即可，但是访问数据的平均效率低，需要对链表进行遍历。

总结

1、对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
2、各自效率问题：

ArrayList是线性表(数组)
get()直接读取第几个下标，复杂度0(1)
add(E)添加元素,直接在后面添加,复杂度O ( 1 )
add(index, E)添加元素,在第几个元素后面插入,后面的元素需要向后移动,复杂度O (n)
remove ( )删除元素,后面的元素需要逐个移动,复杂度0O(n)

LinkedList是链表的操作
get()获取第几个元素,依次遍历,复杂度O(n)
add(E)添加到末尾,复杂度O(1)
add(index, E)添加第几个元素后,需要先查找到第几个元素,直接指针指向操作,复杂度O(n)
remove ( )删除元素,直接指针指向操作,复杂度O(1)

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/152954.html