企业官网建设流程全解析

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)。

添加流程

1. add(E e)调用ensureCapacity()检查是否需要扩容。
2. 如果不需要扩容，将元素添加到数组的最后一个位置，并增加size。

LinkedList

• 插入元素的时间复杂度为O(1)，因为只需要修改前后节点的指针。

添加流程

1. add(E e)调用linkLast(E e)方法，将元素插入到链表的尾部。
2. 创建新节点并更新前后节点的指针，最后增加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

• 适用场景：

• • 适合频繁插入和删除操作的场景，尤其是操作链表两端时。
  • 在大量访问元素时性能较差，因为需要逐个节点遍历。