ArrayList与LinkedList的区别是什么？
ArrayList与LinkedList是Java集合框架中实现List接口的两种常见类，它们各自具有独特的数据结构和特点，适用于不同的应用场景。
一、底层数据结构
ArrayList和LinkedList的底层数据结构是它们之间最本质的区别。
-
ArrayList：
ArrayList是基于数组实现的。它使用了一个动态数组来存储元素，这个数组的大小会根据需要自动增长。当向ArrayList中添加元素时，如果数组已满，就会创建一个更大的新数组，并将旧数组中的元素复制到新数组中。这种实现方式使得ArrayList在随机访问元素时非常高效，因为可以通过索引直接定位到元素的位置。然而，在插入和删除元素时，特别是当插入或删除位置靠近数组开头时，可能需要移动大量的元素，导致性能下降。 -
LinkedList：
LinkedList是基于链表实现的，具体来说，是双向链表。每个元素（节点）都包含数据部分和两个指针，一个指向前一个节点，一个指向后一个节点。这种结构使得LinkedList在插入和删除元素时非常高效，因为只需要修改相邻节点的指针即可，而不需要移动其他元素。然而，在随机访问元素时，LinkedList需要从头节点开始遍历链表，直到找到目标元素，因此效率较低。
二、性能差异
由于底层数据结构的不同，ArrayList和LinkedList在性能上表现出显著的差异。
-
随机访问性能：
对于随机访问操作（如get和set），ArrayList的性能优于LinkedList。因为ArrayList底层是数组结构，可以通过索引直接定位元素，时间复杂度为O(1)。而LinkedList需要遍历链表才能找到指定位置的元素，时间复杂度为O(n)。因此，在需要频繁进行随机访问的场景中，ArrayList是更好的选择。 -
插入和删除性能：
对于插入和删除操作（如add和remove），LinkedList的性能优于ArrayList。因为LinkedList是链表结构，插入和删除元素时只需要修改相邻节点的指针即可，时间复杂度为O(1)（在已知位置的情况下）。而ArrayList在插入或删除元素时，可能需要移动大量的元素（特别是在插入或删除位置靠近数组开头时），时间复杂度为O(n)。因此，在需要频繁进行插入和删除操作的场景中，LinkedList是更好的选择。
三、内存占用
ArrayList和LinkedList在内存占用方面也有所不同。
-
ArrayList：
ArrayList的内存占用主要取决于数组的大小和元素的数量。由于数组是连续存储的，因此ArrayList在内存中的布局相对紧凑。然而，当ArrayList需要扩容时，会创建一个更大的新数组，并将旧数组中的元素复制到新数组中，这会导致一定的内存开销。此外，ArrayList还需要额外的空间来存储数组的长度和容量等信息。 -
LinkedList：
LinkedList的内存占用相对较高。因为每个节点都需要存储数据部分和两个指针（指向前一个节点和后一个节点），这增加了节点的内存占用。此外，由于链表是分散存储的，因此在遍历链表时可能会涉及更多的内存访问操作。然而，LinkedList不需要像ArrayList那样在扩容时复制整个数组，因此在某些情况下可能会减少内存开销。
四、使用便利性
在使用便利性方面，ArrayList和LinkedList各有优缺点。
-
ArrayList：
ArrayList的使用相对简单方便。它提供了动态的增加和减少元素的功能，并实现了ICollection和IList接口等好处。此外，ArrayList还支持通过索引直接访问元素和修改元素的值。这使得ArrayList在编写代码时更加直观和易于理解。然而，由于ArrayList在插入和删除元素时可能需要移动大量的元素，因此在某些情况下可能会导致性能问题。 -
LinkedList：
LinkedList的使用相对复杂一些。由于它是链表结构，因此在插入和删除元素时需要处理指针的修改。此外，LinkedList还提供了在头部和尾部添加/删除元素的方法等额外功能。这使得LinkedList在某些特定场景中（如实现队列和栈等数据结构）更加灵活和高效。然而，由于LinkedList在随机访问元素时需要遍历链表，因此在某些情况下可能会导致性能下降。
五、应用场景
根据ArrayList和LinkedList的特点和性能差异，它们适用于不同的应用场景。
- ArrayList应用场景：
- 需要频繁进行随机访问的场景，如查找、修改和遍历元素等。
- 元素数量相对稳定或变化不大的场景，以减少扩容和复制数组的开销。
- 对内存占用要求较高的场景，因为ArrayList的内存布局相对紧凑。
- LinkedList应用场景：
- 需要频繁进行插入和删除操作的场景，如动态添加和删除元素等。
- 元素数量变化较大的场景，以减少移动元素的开销。
- 需要实现队列、栈等数据结构的场景，因为LinkedList提供了额外的操作方法。
六、示例代码
以下是一个示例代码，展示了ArrayList和LinkedList在插入和删除操作以及随机访问操作方面的性能差异。
import java.util.ArrayList; | |
import java.util.LinkedList; | |
import java.util.List; | |
public class ListExample { | |
public static void main(String[] args) { | |
// 创建一个ArrayList和一个LinkedList | |
List<Integer> arrayList = new ArrayList<>(); | |
List<Integer> linkedList = new LinkedList<>(); | |
// 向两个列表添加10000个元素 | |
for (int i = 0; i < 10000; i++) { | |
arrayList.add(i); | |
linkedList.add(i); | |
} | |
// 在第5000个位置插入一个新元素 | |
arrayList.add(5000, 9999); | |
linkedList.add(5000, 9999); | |
// 删除第5000个元素 | |
arrayList.remove(5000); | |
linkedList.remove(5000); | |
// 测量插入和删除操作的时间 | |
long arrayListInsertTime = measureInsertTime(arrayList); | |
long linkedListInsertTime = measureInsertTime(linkedList); | |
long arrayListRemoveTime = measureRemoveTime(arrayList); | |
long linkedListRemoveTime = measureRemoveTime(linkedList); | |
// 打印结果 | |
System.out.println("ArrayList insert time: " + arrayListInsertTime + "ms"); | |
System.out.println("LinkedList insert time: " + linkedListInsertTime + "ms"); | |
System.out.println("ArrayList remove time: " + arrayListRemoveTime + "ms"); | |
System.out.println("LinkedList remove time: " + linkedListRemoveTime + "ms"); | |
} | |
// 测量在列表的中间插入元素的时间 | |
public static long measureInsertTime(List<Integer> list) { | |
long startTime = System.currentTimeMillis(); | |
for (int i = 0; i < 10000; i++) { | |
list.add(list.size() / 2, i); | |
} | |
long endTime = System.currentTimeMillis(); | |
return endTime - startTime; | |
} | |
// 测量删除列表的元素的时间 | |
public static long measureRemoveTime(List<Integer> list) { | |
long startTime = System.currentTimeMillis(); | |
for (int i = 0; i < 10000; i++) { | |
list.remove(list.size() / 2); | |
} | |
long endTime = System.currentTimeMillis(); | |
return endTime - startTime; | |
} | |
} |
运行以上代码，可以看到LinkedList在插入和删除操作方面比ArrayList更高效，但在随机访问和遍历方面ArrayList相对更高效一些。这验证了ArrayList和LinkedList在性能方面的差异。
七、总结
综上所述，ArrayList和LinkedList是Java集合框架中实现List接口的两种常见类。它们各自具有独特的数据结构和特点，适用于不同的应用场景。ArrayList基于数组实现，适用于需要频繁进行随机访问的场景；而LinkedList基于链表实现，适用于需要频繁进行插入和删除操作的场景。在选择使用哪个类时，需要根据具体的应用场景和需求进行权衡和选择。