1.ArrayList和LinkedList的区别

• ArrayList总结

1.ArrayList的底层数据结构基于动态数组，连续内存存储，适合下标访问(随机访问)

2.扩容机制：因为数组长度固定，超出长度存数据时想要新建数组，然后把老数组中的数据拷贝到新数组

3.如果不是尾部插入数据还会涉及到元素的移动，使用尾插法并指定初始容量可以极大提升性能，甚至超过LinkedList(LinkedList插入元素需要创建大量的node对象)

ArrayList底层的数据结构是一个elementData数组

LinkedList总结

1. 基于双向链表，可以存储在分散的内存中，适合做数据插入及删除操作（尾部插入和ArrayList差不多）
2. LinkedList不存在扩容问题
3. 遍历LinkedList必须使用iterator不能使用for循环，因为每次for循环内部通过get(i)取得某一元素时都需要对LinkedList重新进行遍历，性能消耗极大。

LinkedList底层数据结构是双向链表，当我向LinkedList中添加元素的时候，元素会被包装成一个node对象，node中有一个next(下一个节点)和prev(上一个节点)的两个指针，被称为双向链表

区别

1.ArrayList存储的时候要求数据都是挨在一起的连续的，LinkedList的数据可东一块西一块，只要用指针串起来就好了

2.ArrayList可以下标访问，LinkedList不可以下标访问，最推荐通过迭代器进行访问，如果使用for性能消耗极大

3.⾸先，他们的底层数据结构不同，ArrayList底层是基于数组实现的，LinkedList底层是基于链表实现的

4.由于底层数据结构不同，他们所适⽤的场景也不同，ArrayList更适合随机查找，LinkedList更适合删除和添加，查询、添加、删除的时间复杂度不同

5.另外ArrayList和LinkedList都实现了List接⼝，但是LinkedList还额外实现了Deque接⼝，所以LinkedList还可以当做队列来使⽤