面试题：ArrayList和LinkedList的区别

ArrayList和LinkedList都是Java中实现List接口的集合类，用于存储和操作对象列表，但它们在内部数据结构、性能特性和适用场景上有所不同：

1.内部数据结构：

• ArrayList：基于动态数组实现。这意味着它在内存中是连续存储的，类似于传统的数组，但容量可以自动增长。
• LinkedList：基于双向链表实现。每个元素（节点）包含数据和两个指针，分别指向前一个和后一个节点，因此不需要连续的内存空间。

2.时间复杂度： 

• ArrayList：由于数据是连续存储的，可以通过索引直接访问元素，因此随机访问（如get和set操作）非常快，时间复杂度为O(1)。
• LinkedList：由于需要从头节点开始遍历链表到达指定位置，随机访问性能较差，时间复杂度为O(n)。

3.内存使用： 

• ArrayList：由于是连续存储，可能需要较大的连续内存空间，且在扩容时可能需要复制整个数组。
• LinkedList：每个节点除了存储数据外，还需要额外的空间来存储指针，因此在大量节点的情况下可能会消耗更多内存。

4.插入和删除： 

• ArrayList：在中间插入或删除元素时，需要移动后续元素以保持数组的连续性，这可能导致较慢的性能，时间复杂度为O(n)。
• LinkedList：插入和删除操作更快，只需更改相邻节点的指针即可，时间复杂度为O(1)，特别是当操作发生在列表的两端时。

 总结：如果应用中需要频繁地进行随机访问元素，而插入和删除操作较少，ArrayList可能是更好的选择。相反，如果经常需要在列表中间进行插入和删除操作，并且随机访问较少，LinkedList将提供更好的性能。根据具体的应用场景选择合适的集合类型，可以显著提高程序的运行效率。

查找效率：

①：随机访问---- ArrayList > LinkedList （ArrayList采用下标，LinkedList只能遍历全部进行查找）

②：增加和删除效率（非末尾）----- ArrayList < LinkedList 

③：内存空间的占用------ ArrayList < LinkedList (LinkedList除了存储数据还有两个引用，一个指向前面的元素，一个指向后面的元素)

总结：频繁读取集合元素时采用ArrayList，频繁删除和插入元素时采用LinkedList

 扩展：

1、为什么说ArrayList的插入和删除效率较慢

①：ArrayList的扩容机制

②：元素的移动问题 

 

2、ArrayList扩容机制：默认大小为10，扩容1.5倍