ArrayList和LinkedList的区别

1.顾名思义，前者底层数据结构采用数组结构，通过索引来实现快速随机访问元素；而后者采用双向链表结构，每个元素都包含一个指向前一个元素和后一个元素的引用，所以插入，删除元素效率很高。

2.时间复杂度不同，前者为O1，为常量复杂度，执行一次，后者为On，从头部或尾部开始执行N次。

3.前者占用的空间是连续的，可能产生内存碎片，后者使用链表来连接元素，每个元素都有两个引用，占用空间更大。