Java ArrayList 和 LinkList 原理对比

Java 中的 ArrayList 和 LinkedList 都是实现了 List 接口的集合类它们都允许添加、删除和修改元素。但是它们的底层实现原理不同导致它们在不同的场景下拥有不同的优劣势。

操作的区别

ArrayList 的底层是通过数组实现的因此它具有数组的特性。它允许快速随机访问元素但是在插入和删除元素时速度较慢。当向 ArrayList 中添加元素时如果数组的长度不够容纳新的元素就需要创建一个新的更大的数组并将原来数组中的元素拷贝到新数组中。
优点

快速随机访问元素访问时间复杂度为 O(1)；
可以预先设定集合的大小避免多次扩容。
缺点

插入和删除元素时需要移动元素时间复杂度为 O(n)；
当数组长度不够时需要重新创建一个更大的数组拷贝原有元素开销较大。
LinkedListLinkedList 的底层是通过链表实现的因此它具有链表的特性。它不支持快速随机访问元素但是在插入和删除元素时速度更快。当向 LinkedList 中添加元素时只需要修改指针的指向即可不需要像 ArrayList 那样创建新数组并拷贝元素。
优点

插入和删除元素时只需要修改指针时间复杂度为 O(1)；
不需要预先设定集合的大小节省空间。
缺点

不支持快速随机访问元素访问时间复杂度为 O(n)；
占用空间较大因为需要为每个元素保存指针。
3.适用场景ArrayList适合于随机访问元素的场景比如需要频繁地读取集合中的元素而不需要频繁地插入和删除元素的情况。

LinkedList适合于频繁的插入和删除元素的场景比如实现栈和队列等数据结构或者需要经常对集合进行排序的情况。

空间纬度

ArrayList 是基于数组实现的动态数组它的内部是一个 Object[] 数组通过不断扩容实现可变长度。当数组已满时ArrayList会创建一个新的更大的数组将原数组中的元素拷贝到新数组中并使用新数组替换原数组。
ArrayList 的优点是访问元素快速因为它可以通过索引直接访问元素而不需要像 LinkedList一样遍历整个链表。缺点是插入和删除元素相对较慢因为在数组中插入或删除一个元素时需要将该位置后面的元素都向后或向前移动一个位置。

ArrayList适用于频繁访问元素但很少进行插入和删除操作的场景。

LinkedListLinkedList 是基于链表实现的双向链表它的内部是由一个个节点组成的每个节点包含一个值和指向前一个和后一个节点的指针。
LinkedList 的优点是插入和删除元素相对较快因为只需要修改相邻节点的指针即可而不需要像 ArrayList一样移动大量元素。缺点是访问元素相对较慢因为需要遍历整个链表找到指定位置的元素。

LinkedList适用于经常进行插入和删除操作的场景但不适用于频繁访问元素的场景。

综上所述ArrayList 和 LinkedList 的使用场景不同需要根据具体情况选择合适的集合类型。

以下是ArrayList的add()方法源码实现原理的简要描述：

1、判断当前元素个数是否达到底层数组的容量，如果达到了则需要进行扩容。

2、将待添加元素添加到底层数组的末尾，并将ArrayList的元素个数加1。

3、如果需要在指定位置添加元素，则需要将该位置后面的所有元素都向后移动一个位置，以腾出位置给新元素。

4、添加完成后，ArrayList的修改次数（modCount）会自增1，用于迭代器检测ArrayList是否被修改过。

具体源码实现如下：

public boolean add(E e) {
 ensureCapacityInternal(size  1); // 判断容量是否足够，不够则进行扩容
 elementData[size  ] = e; // 将元素添加到末尾
 return true;
}

private void ensureCapacityInternal(int minCapacity) {
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 如果底层数组未初始化，则进行初始化
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 ensureExplicitCapacity(minCapacity); // 确保容量足够
}

private void ensureExplicitCapacity(int minCapacity) {
 modCount  ; // 修改次数加1
 if (minCapacity - elementData.length >0)
 grow(minCapacity); // 扩容
}

private void grow(int minCapacity) {
 int oldCapacity = elementData.length;
 int newCapacity = oldCapacity   (oldCapacity >>1); // 扩容为原来的1.5倍
 if (newCapacity - minCapacity <0)
 newCapacity = minCapacity;
 if (newCapacity - MAX_ARRAY_SIZE >0)
 newCapacity = hugeCapacity(minCapacity);
 elementData = Arrays.copyOf(elementData, newCapacity); // 扩容底层数组
}

private E elementData(int index) {
 return (E) elementData[index];
}

public void add(int index, E element) {
 rangeCheckForAdd(index); // 检查下标是否越界
 ensureCapacityInternal(size  1); // 判断容量是否足够，不够则进行扩容
 System.arraycopy(elementData, index, elementData, index  1, size - index); // 将指定位置后面的元素向后移动一位
 elementData[index] = element; // 在指定位置添加元素
 size  ; // 元素个数加1
}

private void rangeCheckForAdd(int index) {
 if (index > size || index <0)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

这篇好文章是转载于：学新通技术网