Java 中 ArrayList 和 LinkedList 的区别

Java 2月前 9

ava 中的 ArrayList 和 LinkedList 是两种常见的集合类，用于存储和操作多个对象。它们有着不同的内部实现和适用场景。本文将对 ArrayList 和 LinkedList 进行详细比较，并举例说明它们的区别，并提供一些使用时的注意事项。

内部实现方式：
- ArrayList：ArrayList 内部使用数组实现，可以动态增长和缩小。当数组容量不足时，ArrayList 会创建一个新的更大的数组，将旧数组中的元素复制到新数组中。
- LinkedList：LinkedList 内部使用双向链表实现，每个元素包含一个指向前一个和后一个元素的指针。当需要插入和删除元素时，只需要调整相邻元素的指针即可，不需要移动其他元素。
访问速度：
- ArrayList：由于使用数组实现，ArrayList 的访问速度比较快。根据索引访问元素的时间复杂度为 O(1)。
- LinkedList：由于使用链表实现，LinkedList 的访问速度相对较慢。根据索引访问元素的时间复杂度为 O(n)，需要遍历链表找到对应位置的元素。
插入和删除操作：
- ArrayList：对于尾部的插入和删除操作，ArrayList 的性能接近 O(1)。但是对于中间或开头的插入和删除操作，由于需要移动元素，性能较差，时间复杂度为 O(n)。
- LinkedList：对于任意位置的插入和删除操作，LinkedList 的性能接近 O(1)。因为只需要调整相邻元素的指针，不需要移动其他元素。
内存消耗：
- ArrayList：由于需要额外的空间存储扩展容量的数组，ArrayList 的内存消耗比较大。尤其是在容量较大时，但是元素较少的情况下，会浪费一定的内存。
- LinkedList：由于需要为每个元素额外存储前后指针，LinkedList 的内存消耗相对较小。但是链表的指针占用的内存空间也需要考虑。

示例：

假设我们需要存储一系列学生对象，并按照学号进行访问和排序。可以使用 ArrayList 或 LinkedList 来实现。如果只需要按照学号访问和排序，可以选择 ArrayList，因为它的访问速度快。但如果经常需要插入和删除操作，比如根据成绩插入一个新的学生，LinkedList 是更好的选择，因为它的插入和删除性能更好。