ArrayList

目录

ArrayList

无参构造函数：

 有参构造函数：

扩容：

插入：

ArrayList尾部插入：

ArrayList头部插入：

LinkedList

插入：

LinkedList尾部插入:

LinkedList头部插入：

---

ArrayList:顺序表，动态数组，随机访问。

无参构造函数：

使用无参构造函数初始化 ArrayList 后，它当时的数组容量为 0 。

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

如果使用了无参构造函数来初始化 ArrayList， 只有当我们真正对数据进行添加操作 add 时，才会给数组分配一个默认的初始容量 DEFAULT_CAPACITY = 10。

1.ensureCapacityInternal()点进这个方法

public boolean add(E e) {
        //判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2. calculateCapacity()点进这个方法

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

3.此时这才会分配默认的初始容量 DEFAULT_CAPACITY = 10。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

 有参构造函数：

ArrayList 的有参构造函数就是中规中矩了，按照用户传入的大小开辟数组空间。

我们往数组中新加入一个元素但是发现数组满了的时候，我们就要去扩容。

扩容：

add方法首先会判断是不是需要扩容，需要扩容的时候调用grow方法，扩容后的数组长度 = 当前数组长度 + 当前数组长度 / 2，也就是初始容量的1.5倍。最后使用 Arrays.copyOf 方法直接把原数组中的数组 copy 过来，需要注意的是，Arrays.copyOf 方法会创建一个新数组然后再进行拷贝。

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 扩容后数组是原来数组+原来数组的1/2 = 1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

插入：

ArrayList尾部插入：

public boolean add(E e) {
        // 检查是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 直接在尾部添加元素
        elementData[size++] = e;
        return true;
    }

可以看出，对ArrayList的尾部插入，直接插入即可，无须额外的操作。

ArrayList头部插入：

add(int index, E element)方法，可以看到通过调用系统的数组复制方法来实现了元素的移动。所以，插入的位置越靠前，需要移动的元素就会越多，实际上就是把原来数组中index位置开始的元素全部复制到index+1开始的位置，其实就是index后面的元素像后移动一位。

public void add(int index, E element) {
        rangeCheckForAdd(index);
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 把原来数组中的index位置开始的元素全部复制到index+1开始的位置（其实就是index后面的元素向后移动一位）
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 插入元素
        elementData[index] = element;
        size++;
    }

LinkedList

LinkedList:双向链表，增加和删除，是线程不安全的

插入：

LinkedList尾部插入:

public boolean add(E e) {
        linkLast(e);
        return true;
    }

linkLast(E e)方法，可以看出，在尾部插入的时候，并不需要从头开始遍历整个链表，因为已经事先保存了尾结点，所以可以直接在尾结点后面插入元素。

LinkedList头部插入：

add(int index, E element)方法，该方法先判断是否是在尾部插入，如果是调用linkLast()方法，否则调用linkBefore()。

在头尾以外的位置插入元素当然得找出这个位置在哪里，这里面的node()方法就是关键所在，这个函数的作用就是根据索引查找元素，但是它会先判断index的位置，如果index比size的一半(size >> 1,右移运算，相当于除以2)要小，就从头开始遍历。

否则，从尾部开始遍历。从而可以知道，对于LinkedList来说，操作的元素的位置越往中间靠拢，效率就越低。

Node node(int index) {
        // assert isElementIndex(index);
 
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

这个函数的工作就只是负责把元素插入到相应的位置而已，关键的工作在node()方法中已经完成了,所以头尾查找速度极快，越往中间靠拢效率越低。

void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

所以说，LinkedList查找第4个元素和查找第6个元素速度都是一样的。