本文讨论的内容基于随机访问的情况下
- 1.数据结构
- 2.性能
- 3.代码实现
数据结构
JDK文档自行查看参考链接:
oracle JDK_1.8_API
中文谷歌版 JDK_1.8_API
ArrayList
基于动态数组的数据结构(顺序表)。
LinkedList
基于链表的数据结构(双向链表)。
两者性能差异
1.ArrayList是基于索引的数组动态结构,对于随机访问的get和set开销相对比较小,时间复杂度为O(1);而LinkedList是双向链表,指针都回去挨个遍历,每次随机的调用get或set时间复杂度为O(n)。
2.在执行add和remove操作时,LinkedList的双向链表体现出了指针优势,每次执行add或remove操作后不需要移动数据。
代码实现
//留个坑