数据结构进阶：链表原理与 Java 实现

数据结构进阶：链表原理与 Java 实现

1. ArrayList 的缺陷

通过源码可知，ArrayList 底层使用数组来存储元素。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // ...
    // 默认容量是 10
    private static final int DEFAULT_CAPACITY = 10;
    // ...
    // 数组：用来存储元素
    transient Object[] elementData;
    // non-private to simplify nested class access
    // 有效元素个数
    private int size;

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }
    // ...
}

由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后续元素整体往前或者往后搬移，时间复杂度为 O(n)，效率比较低。因此 ArrayList 不适合做任意位置插入和删除比较多的场景。为此，Java 集合中引入了 LinkedList，即链表结构。