JavaArrayList与LinkedList：实现原理与性能对比
ArrayList和LinkedList都实现了List接口，提供了有序的集合操作，但它们的底层数据结构和操作实现方式完全不同，因此在性能和使用场景上有很大差异。通过对比两者的实现，可以帮助我们在不同场景下做出更合适的选择。
1.ArrayList和LinkedList的设计思想
ArrayList和LinkedList都是List接口的实现类，但它们的设计思想和适用场景有所不同：
ArrayList：
- 基于动态数组实现，适合频繁访问元素的场景。
- 底层存储是一个数组，访问元素的时间复杂度为O(1)。
- 插入和删除元素时可能需要移动数组中的元素，时间复杂度为O(n)。
LinkedList：
- 基于双向链表实现，适合频繁插入和删除元素的场景。
- 每个元素是一个节点，包含指向前后节点的引用。
- 插入和删除元素时不需要移动其他元素，时间复杂度为O(1)。
- 访问元素时需要遍历链表，时间复杂度为O(n)。
2.ArrayList源码实现
ArrayList底层基于数组实现，支持动态扩容。
初始化与扩容
ensureCapacity：用于判断当前数组的容量是否足够，如果不够则调用grow方法扩容。grow：通过Arrays.copyOf创建一个更大的数组，并将原有数组的元素拷贝过去，扩容后的容量为原容量的1.5倍。
示例代码：ArrayList扩容
java复制
private void ensureCapacityInternal(int minCapacity) { if (minCapacity > elementData.length) { grow(minCapacity); } } private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原容量的1.5倍 elementData = Arrays.copyOf(elementData, newCapacity); }3.LinkedList源码实现
LinkedList底层基于双向链表实现，每个节点包含数据和指向前后节点的指针。
节点定义
java复制
private static class Node<E> { E item; // 数据 Node<E> next; // 指向下一个节点 Node<E> prev; // 指向前一个节点 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }节点插入操作
linkLast：将新元素插入到链表的末尾。- 链表的头节点
first和尾节点last用于维护链表的开始和结束。
示例代码：LinkedList插入
java复制
public void add(E e) { linkLast(e); } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; }4. 添加元素的性能比较
ArrayList
- 在末尾添加元素时，时间复杂度为O(1)。
- 如果数组满了，会进行扩容，扩容的时间复杂度为O(n)。
添加流程
add(E e)调用ensureCapacity()检查是否需要扩容。- 如果不需要扩容，将元素添加到数组的最后一个位置，并增加
size。
LinkedList
- 插入元素的时间复杂度为O(1)，因为只需要修改前后节点的指针。
添加流程
add(E e)调用linkLast(E e)方法，将元素插入到链表的尾部。- 创建新节点并更新前后节点的指针，最后增加
size。
5. 查找元素的性能比较
ArrayList
- 查找元素时，时间复杂度为O(1)，直接通过索引访问数组元素。
LinkedList
- 查找元素时，时间复杂度为O(n)，需要从头到尾遍历链表。
6. 删除元素的性能比较
ArrayList
- 删除元素时，删除位置之后的所有元素需要向前移动，时间复杂度为O(n)。
删除流程
java复制
public boolean remove(Object o) { if (o == null) { for (int i = 0; i < size; i++) { if (elementData[i] == null) { fastRemove(i); // 调用fastRemove移除元素 return true; } } } else { for (int i = 0; i < size; i++) { if (o.equals(elementData[i])) { fastRemove(i); // 调用fastRemove移除元素 return true; } } } return false; }LinkedList
- 删除元素时，只需修改前后节点的指针，时间复杂度为O(1)。
- 但需要遍历链表找到要删除的节点，查找的时间复杂度为O(n)。
删除流程
java复制
public E remove(int index) { checkElementIndex(index); // 索引越界检查 Node<E> x = node(index); // 找到要删除的节点 E element = x.item; unlink(x); // 移除节点 return element; } void unlink(Node<E> x) { final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) first = next; else prev.next = next; if (next == null) last = prev; else next.prev = prev; x.item = null; size--; }7. 适用场景总结
ArrayList
- 适用场景：
- 适合频繁访问元素的场景，尤其是需要随机访问时。
- 在大量插入和删除操作时性能较差，因为需要移动数组元素。
LinkedList
- 适用场景：
- 适合频繁插入和删除操作的场景，尤其是操作链表两端时。
- 在大量访问元素时性能较差，因为需要逐个节点遍历。
