(1)ArrayList底层是动态数组,查询快、增删慢。存储空间是连续的,可以根据寻址方式直接找到对应的元素位置,所以查询时间复杂度是o(1)。
- 扩容:ArrayList支持动态扩容,在每次新增元素的时候会判断容量是否溢出,如果溢出则会进行扩容操作。当size=elementData.length时,表示数据数量已经超过了数组容量,需要扩容,扩容后的数组长度为原来数组长度的1.5倍。
- 复制:当扩容操作结束后,如果新增的元素不在数组尾部,则将索引后面的元素通过System.arraycopy往后移动一位。
- 赋值:将值赋给数组中对应的索引,并将size++。
(2)LinkedList底层是一个双向链表,查询慢、增删快。存储空间不连续,节点之间是通过指针进行关联的,在查询过程中需要不断跳转新的地址,没有初始化大小,也没有扩容机制。
add()、remove()的时间复杂度是o(1),get()、set()的时间复杂度是o(n)。
参考文献:https://blog.csdn.net/xingyu19911016/article/details/125049128标签:扩容,LinkedList,ArrayList,数组,复杂度,底层 From: https://www.cnblogs.com/wbbky/p/18072153