面试题：Java中List集合的性能对比

Question

请对比Java中ArrayList和LinkedList在添加元素、删除元素以及随机访问元素时的性能特点，并说明原因。

Answer 1

添加元素

• ArrayList：
  • 性能特点：在列表末尾添加元素性能较好，时间复杂度为O(1)；在中间或开头添加元素性能较差，时间复杂度为O(n)。
  • 原因：ArrayList是基于数组实现的。在末尾添加元素时，若数组容量足够，直接在末尾插入即可；若容量不足，需要进行数组扩容，虽然扩容操作时间复杂度较高，但分摊到每次添加操作上，平均时间复杂度仍接近O(1)。而在中间或开头添加元素时，需要将后续元素整体向后移动，移动元素的时间复杂度为O(n)。
• LinkedList：
  • 性能特点：在任何位置添加元素性能都较好，时间复杂度均为O(1)。
  • 原因：LinkedList是基于链表实现的。在链表的任何位置添加元素，只需修改相关节点的指针指向，无需移动大量元素，所以时间复杂度为O(1)。

删除元素

• ArrayList：
  • 性能特点：删除末尾元素性能较好，时间复杂度为O(1)；删除中间或开头元素性能较差，时间复杂度为O(n)。
  • 原因：删除末尾元素时，若不考虑数组缩容，直接移除末尾元素即可，时间复杂度为O(1)。若删除中间或开头元素，需要将后续元素整体向前移动，移动元素的时间复杂度为O(n)。
• LinkedList：
  • 性能特点：删除任何位置元素性能都较好，时间复杂度均为O(1)。
  • 原因：在链表中删除元素，只需修改相关节点的指针，将待删除节点从链表中分离，无需移动大量元素，时间复杂度为O(1)。但实际中可能需要先查找要删除的节点，查找操作时间复杂度为O(n)，整体删除操作时间复杂度会受到查找影响。

随机访问元素

• ArrayList：
  • 性能特点：随机访问性能好，时间复杂度为O(1)。
  • 原因：ArrayList基于数组，数组支持通过下标直接访问元素，根据下标可以直接定位到内存中的位置，所以随机访问时间复杂度为O(1)。
• LinkedList：
  • 性能特点：随机访问性能差，时间复杂度为O(n)。
  • 原因：LinkedList是链表结构，要访问特定位置的元素，需要从链表头或尾开始遍历，直到找到目标元素，遍历操作的时间复杂度为O(n)。