面试题：Java中ArrayList与LinkedList在添加元素操作上的性能差异

Question

请阐述在Java中，ArrayList和LinkedList在向列表中间添加元素时，性能上有何不同，并说明原因。

Answer 1

1. 性能不同
   • ArrayList：在列表中间添加元素性能相对较差。
   • LinkedList：在列表中间添加元素性能相对较好。
2. 原因
   • ArrayList：它是基于数组实现的。当在中间位置添加元素时，需要将添加位置后面的所有元素向后移动一位，移动元素的时间复杂度为O(n)，n为移动元素的个数，所以整体时间复杂度为O(n)，性能较低。例如，若ArrayList中有100个元素，要在第50个位置添加元素，那么从第50到第99个元素都要向后移动。
   • LinkedList：它是基于链表实现的。在链表中间添加元素，只需修改添加位置前后节点的指针指向即可。找到要添加位置的节点时间复杂度可能为O(n)，但修改指针操作时间复杂度为O(1)，总体时间复杂度在找到位置后接近O(1)，所以在中间添加元素性能较好。比如双向链表，要在某个节点A和B之间添加节点C，只需让A的next指向C，C的prev指向A，B的prev指向C，C的next指向B。