面试：ArrayList和LinkedList

ArrayList和LinkedList是什么？

• ArrayList： ArrayList是Java集合框架中的一个类，它实现了List接口，底层基于数组实现。ArrayList的特点是支持动态数组，可以自动扩容，适合顺序访问和随机访问。
• LinkedList： LinkedList也是Java集合框架中的一个类，同样实现了List接口，但底层基于链表实现。LinkedList的特点是支持高效的插入和删除操作，但随机访问的性能相对较差。

区别与优缺点对比

ArrayList和LinkedList区别

	ArrayList	LinkedList
获取指定元素	速度很快	需要从头开始查找元素
添加元素到末尾	速度很快	速度很快
在指定位置添加/删除	需要移动元素	不需要移动元素
内存占用	少	较大

集合	底层结构	增删效率	改查效率
ArrayList	可变数组	较低,数组扩容	快,索引定位
LinkedList	双向链表	较高.通过链表追加	慢

• **存储结构：**ArrayList使用数组作为底层数据结构，数据在内存中是连续存储的，因此支持随机访问非常快速。LinkedList则使用链表作为底层数据结构，每个元素都包含指向前后元素的指针，插入和删除操作非常高效。

• **插入与删除操作：**在ArrayList中，如果插入或删除元素，可能会导致数组元素的移动，从而影响性能。而LinkedList在插入和删除操作上具有明显优势，因为只需修改指针的指向，不需要移动大量元素。

• **随机访问性能：**由于ArrayList的数组连续存储特性，它在随机访问上具有很好的性能。通过索引即可直接访问元素。而LinkedList需要从头或尾开始遍历链表，随机访问性能较差。

• **内存占用：**由于LinkedList每个元素都需要存储前后指针，相对于ArrayList会占用更多的内存空间。如果需要存储大量数据，考虑内存占用也是一个重要因素。

• **迭代性能：**在迭代（遍历）操作上，ArrayList由于连续存储的特性，性能通常较好。而LinkedList在迭代操作上由于需要通过指针跳转，性能相对较差。

• 扩容机制：

  • ArrayList 当容量不足时，会进行扩容操作，涉及到复制元素，开销较大。
  • LinkedList 不需要扩容，按需添加节点。

使用ArrayList的场景：

• 需要频繁进行随机访问，例如根据索引获取元素。
• 数据集合相对固定，不需要频繁的插入和删除操作。
• 内存占用相对较少，不会造成严重的资源浪费。

使用LinkedList的场景：

• 需要频繁进行插入和删除操作，尤其是在中间位置。

• 不关心随机访问性能，而更关注插入和删除的效率。

• 可能需要更少的内存占用，尤其是在元素数量较少的情况下。

参考：《Think In Java》