Array、ArrayList和LinkedList

底层原理见：Java集合进阶

1. Array和ArrayList的区别

• 类型：
  • Array是Java中的一种基本数据结构，可以存储基本数据类型或对象引用。
  • ArrayList是Java集合框架中的一个类，实现了List接口，只能存储对象引用。
• 大小可变性：
  • Array的大小是固定的，在创建时必须指定，不能动态调整。
  • ArrayList的大小是可变的，可以根据需要动态增加或减少元素。
• 性能：
  • Array在访问元素时性能较好，因为它是连续的内存块，支持快速索引。
  • ArrayList在添加或删除元素时可能更高效，尤其是在数组末尾操作时。
• 泛型支持：
  • Array可以是泛型的，也可以不是。
  • ArrayList必须是是泛型的，提供了类型安全。
• 方法：
  • Array提供的操作有限，主要是基本的数据访问和修改。
  • ArrayList提供了丰富的方法，如添加、删除、查找等操作

维度	Array	ArrayList
长度/容量	固定长度，一旦创建，长度不可变	长度可变，可根据需要自动扩容和缩容
元素类型	可存储基本数据类型和引用类型	只能存储引用类型，基本类型会自动装箱
API/操作	功能单一，通过[]运算符访问，无内置方法	提供了丰富的API方法(add(),remove(),get()等)
泛型支持	不直接支持泛型，编译时类型检查不如ArrayList严格	原生支持泛型，提供编译时类型安全
底层实现	语言内置的底层数据结构	基于动态数组实现，是集合框架的一部充分

• 面试官可能的追问：在Java中，当需要存储大量基本数据类型时，除了数组，还有其他什么选择吗？
  • Apache Commons Lang库： 这个库提供了ArrayUtils等工具类，以及PrimitiveIterator等，可以更方便地操作基本类型数组。
  • Guava库： 提供了Ints, Longs等工具类，以及ImmutableList的基本类型版本，用于处理基本类型的集合，避免装箱。
  • FastUtil或Trove库： 这些是专门为高性能基本类型集合设计的第三方库，它们提供了IntArrayList, LongHashSet等，直接在内部使用基本类型数组，完全避免了装箱拆箱，性能远超java.util包中的标准集合类，适用于大数据量和对性能要求比较高的场景。

2. ArrayList和LinkedList的区别

• 数据结构：
  • ArrayList是基于动态数组实现的，适合随机访问。
  • LinkedList是基于双向链表实现的，适合插入和删除操作。
• 性能：
  • ArrayList在随机访问元素时速度较快，因为它支持索引访问。
  • LinkedList在随机访问元素时速度较慢，需要遍历链表，但在插入和删除元素时更高效。
• 内存使用：
  • ArrayList由于是基于数组，它在存储大量元素时可能会更高效。
  • LinkedList每个元素都需要额外的内存空间来存储前驱和后继元素的引用。
• 扩容：
  • ArrayList在需要扩容时，会创建一个更大的数组并复制元素，可能会导致性能下降。
  • LinkedList不需要扩容，因为它通过链接节点来增加元素。
• 功能：
  • ArrayList提供了更快地随机访问和更高效的内存使用。
  • LinkedList提供了更高效的插入和删除操作，并且可以更有效的实现栈和队列等数据结构。