Java面试题：ArrayList 和 LinkedList 的区别是什么？

数据结构

ArrrayList 底层的数据结构是数组，支持随机访问，而 LinkedList 的底层数据结构是双向循环链表，不支持随机访问。使用下标访问一个元素，ArrayList 的时间复杂度是 O(1)，而 LinkedList 是 O(n)。

ArrayList 内部实现：

LinkedList 内部实现：

上图中，Node 就是一个双向链表结构，next 指向下一个节点，prev 指向上一个节点。

面试题广告位

随机访问

ArrayList 支持快速的随机访问，因为它可以通过索引直接访问元素。

LinkedList 不支持快速的随机访问，因为它需要从头或尾开始遍历链表才能找到指定位置的元素。

插入和删除操作

在 ArrayList 中，插入和删除操作可能会导致数组的重新分配（扩容）和元素的移动（如果在数组中插入一个元素，则插入元素位置到数组末尾的已有元素需要向后移动一位），因此性能较低。

在 LinkedList 中，插入和删除操作只需要改变相邻节点的指针，因此性能较高。

内存占用

由于 ArrayList 使用数组存储元素，它的内存占用可能会比 LinkedList 小。而 LinkedList 使用节点存储元素，可能会占用更多的内存，每个元素需要单独保存指向前一个和后一个节点的地址。