1. ArrayList 和 LinkedList 的区别是什么？

1.1 引言

在Java编程中，我们经常会使用到集合类来存储和操作数据。ArrayList和LinkedList是Java集合框架中两种常见的实现类，它们都实现了List接口，但在底层实现和使用方式上有所不同。本文将深入探讨ArrayList和LinkedList的区别，包括它们的底层数据结构、插入和删除操作的性能、随机访问的效率等方面，帮助读者更好地理解和选择合适的集合类。

1.2 ArrayList与LinkedList的简介

ArrayList和LinkedList分别属于Java集合框架中的List接口实现类，都是动态数组的变体。它们都支持动态增长和缩减，能够存储任意类型的对象，可以根据索引来直接访问元素。它们的主要区别在于底层数据结构和操作性能。

2. ArrayList的特点和使用方式

2.1 底层数据结构

ArrayList内部使用数组来存储元素，通过索引来访问和操作元素。当元素个数超过当前数组容量时，ArrayList会自动扩容，并重新分配一个更大的数组来存储元素。

2.2 优点

• 随机访问效率高：由于ArrayList是基于数组实现的，所以支持通过索引来直接访问元素，时间复杂度为O(1)。
• 内存占用相对较小：由于ArrayList的底层结构是数组，所以它只需要存储元素本身的值和一些必要的附加信息（例如数组长度），相比于LinkedList，内存占用较小。

2.3 缺点

• 插入和删除操作效率低：由于ArrayList是基于数组实现的，所以在数组中间插入或删除元素需要移动其他元素，时间复杂度为O(n)。当需要频繁进行插入和删除操作时，性能较差。
• 扩容性能开销：当ArrayList的元素个数超过当前容量时，需要进行扩容操作。扩容的过程中需要重新分配一个更大的数组，并将原有元素复制到新数组中，这个过程的时间开销是比较大的。

2.4 部分源码

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 添加元素 size+1
        elementData[size++] = e;
        return true;
}

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

// 扩容
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity); // 这里是复制
}

// 可以看到往指定位置添加元素则要把整个数组复制一份新的
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++;
}

3. LinkedList的特点和使用方式

3.1 底层数据结构

LinkedList内部使用双向链表来存储元素，每个节点包含了元素本身的值和对前后节点的引用。这种数据结构使得插入和删除操作更加高效。

3.2 优点

• 插入和删除操作效率高：由于LinkedList是基于链表实现的，它只需要调整节点的指针即可完成插入和删除操作，时间复杂度为O(1)。当需要频繁进行插入和删除操作时，性能较好。
• 内存分配更灵活：由于LinkedList的底层数据结构是链表，所以它的内存分配是更加灵活的，可以根据具体需求动态分配内存，不需要像ArrayList一样进行扩容操作。

3.3 缺点

• 随机访问效率低：由于LinkedList是基于链表实现的，所以需要通过遍历链表来访问指定索引的元素，时间复杂度为O(n)。当需要频繁进行随机访问操作时，性能较差。
• 内存占用相对较大：由于LinkedList的每个节点都需要存储元素本身的值和前后节点的引用，所以内存占用相对较大。

3.4 部分源码

class Node {
	Node next; // 下一个元素指针
    Node previous; // 上一个元素指针
    Object obj; // 当前元素
}	
// 可以看到它添加元素的时候只需要设置这个元素前后元素的指针就可以了
public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
}

4. 总结

ArrayList和LinkedList是Java集合框架中两种常见的List实现类，它们在底层数据结构、插入和删除操作的性能、随机访问效率等方面存在显著的差异。

• 如果需要频繁进行随机访问操作，应选择ArrayList，因为其通过索引直接访问元素的效率高。
• 如果需要频繁进行插入和删除操作，应选择LinkedList，因为其在链表节点调整的操作上更加高效。 根据具体的需求和使用场景，选择合适的集合类可以提高代码的性能和效率。