ArrayList 和 LinkedList 是两个常用的 List 集合实现类，如果需要频繁进行随机访问操作，那么应该选择 ArrayList。如果需要频繁进行插入和删除操作，那么应该选择 LinkedList。
数据结构
ArrrayList 底层的数据结构是数组，支持随机访问，而 LinkedList 的底层数据结构是双向循环链表，不支持随机访问。使用下标访问一个元素，ArrayList 的时间复杂度是 O(1)，而 LinkedList 是 O(n)。
ArrayList 内部实现：
LinkedList 内部实现：
上图中，Node 就是一个双向链表结构，next 指向下一个节点，prev 指向上一个节点。
面试题广告位
随机访问
ArrayList 支持快速的随机访问，因为它可以通过索引直接访问元素。
LinkedList 不支持快速的随机访问，因为它需要从头或尾开始遍历链表才能找到指定位置的元素。
插入和删除操作
在 ArrayList 中，插入和删除操作可能会导致数组的重新分配（扩容）和元素的移动（如果在数组中插入一个元素，则插入元素位置到数组末尾的已有元素需要向后移动一位），因此性能较低。
在 LinkedList 中，插入和删除操作只需要改变相邻节点的指针，因此性能较高。
内存占用
由于 ArrayList 使用数组存储元素，它的内存占用可能会比 LinkedList 小。而 LinkedList 使用节点存储元素，可能会占用更多的内存，每个元素需要单独保存指向前一个和后一个节点的地址。
