数据结构学习系列之从源码来看ArrayList

我不是女神ヾ 2022-03-16 11:22 129阅读 0赞

## 引导 ##

`ArrayList`是List大家族的一份子，祖先是`Collection`，也是我们最常用的数据结构之一，它的实现原理正如其名，其内部是一个对象数组：

transient Object[] elementData;
    复制代码

ArrayList使用一个变量来控制当前的游标，当我们做add或者remove操作的时候就会移动游标：

private int size;
    复制代码

`ArrayList`大部分的基本操作都是围绕这两个变量展开的。

### add方法 ###

public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // A
       elementData[size++] = e; // B
       return true;
    }
    复制代码

当我们向ArrayList添加一个元素的时候，在`A`这一步会检测是否需要扩容，扩容的检测机制也很简单：

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

如果发现`size + 1`大于数组长度，则认为数组不够用，需要扩容，扩容的过程在`grow`方法中进行：

private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       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);
    }
    复制代码

扩容时，首先会计算出新的容器大小，然后使用`Arrays.copyOf`复制数组。扩容检测结束，则执行

elementData[size++] = e; // B
    复制代码

元素赋值并移动下标！

### remove方法 ###

ArrayList中的remove操作有两种方式，第一种通过下标移除：

public E remove(int index) {
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;  
        if (numMoved > 0) //A
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved); //B
        elementData[--size] = null; // C
    
        return oldValue;
    }
    复制代码

首先会在`A`处判断要移除的元素是否是当前尾部元素，如果是，则直接执行`C`，否则，会将该元素之后的所有元素向前移移位，这里同样使用的是`Arrays.copyOf`。

另一种移除方式是通过判断是否是同一个对象来决定是否移除：

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    复制代码

这里很简单，通过遍历`elementData`然后依次判断是否和被移除的元素相等，如果相等则移除，并返回`true`。通过代码可以看到，如果将一个元素执行多次`add`，那么需要执行同样次数的`remove`才可以删干净!

### subList方法 ###

首先说明一下，这个方法要慎用，从方法名字和方法参数来看，让人感觉是将List截取一部分供大家使用，就像String的`subString`方法一样，其返回值是一个新的对象，然而其内部实现却并非如此：

public List<E> subList(int fromIndex, int toIndex) {
       subListRangeCheck(fromIndex, toIndex, size);
       return new SubList(this, 0, fromIndex, toIndex);
    }
    复制代码

通过源码可以看到，首先会进行范围检测，之后会返回一个`SubList`对象，貌似没什么问题，别急，我们进一步看一下`SubList`这个类：

SubList(AbstractList<E> parent,
                    int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
    复制代码

该类的构造方法需要传入一个List对象并将其赋值给SubList的parent变量，毋容置疑，这个对象就是当前的ArrayList对象，还有`offset`、`fromIndex`、`toIndex`。

此时我们会发现有些不妙，为啥一个新的List还会有from和to这种东西？于是我们带着好奇心去看一看它的`add`方法：

public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        parent.add(parentOffset + index, e); //A
        this.modCount = parent.modCount;
        this.size++;
    }
    复制代码

注意`A`这一步，parent不就是我们构造方法中传进来的`ArrayList`对象吗！！这里竟然操作的是原来的ArrayList对象，而并非快照！

由此看来，subList方法获取的SubList对象的操作是基于原ArrayList对象内部的`elementData`数组的，如果只读的情况下，这个方法人畜无害，如果想要对其操作，就要慎重使用，因为它会影响原来的ArrayList对象内部元素！

## 总结 ##

ArrayList的实现是通过数组加游标配合完成，原理很简单，`subList`方法要慎用，必要时我们可以使用另一种方式避免对原ArrayList的读写：

ArrayList<Integer> list = new ArrayList();
    list.add(1);
    list.add(2);
    ArrayList<Integer> subList = new ArrayList();
    subList.addAll(list.subList(1,2));
    复制代码