List接口——ArrayList学习笔记

2021-03-20  本文已影响0人  Levi_moon

ArrayList底层采用的是一个可以动态再分配的对象数组。

ArrayList学习的最好方法就是学习ArrayList的源码,通过学习源码,就可以知道它是怎么对数据进行增、删、改、查操作的。

(一)底层实现原理

如果想要探究ArrayList底层实现原理的话,那么,我们就需要通过解读源码来一探究竟。而解读源码的入口,就是构造器。

1. 从构造器入手

进入ArrayList类,找到默认构造器,我们发现默认构造器的代码是这样写的:

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

transient Object[] elementData;

private int size;

private static final int DEFAULT_CAPACITY = 10;

通过代码可以看到,当通过默认构造器实例化一个ArrayList对象时,一个空的对象数组(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)被赋值给元素集合(elementData)了。此时,一个空的ArrayList对象就被创造出来了,这个对象的值为null,长度是0,此时还不能往对象中添加任何元素。


2. 添加元素

当向集合中添加元素时,分为两种情况:一种是直接在集合已有元素后新增元素;另一种是在已有元素的情况下,根据索引值插入新元素。这两种新增元素的实现逻辑不同,因此需要分开学习。

2.1 新增元素

当给新创建的ArrayList对象添加元素时,一般是通过add()方法。那么add()方法的代码是怎么写的呢?

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

从最后一行代码可以看到,经过一番逻辑处理后,最后的返回值是true,代表着新元素被添加进元素集合了。那么,在返回true之前,元素集合内发生了什么呢?

我们从下往上看代码,看方法体的第二行elementData[size++] = e;,这行代码是向元素集合中,索引下标为size++的位置添加新元素e。如果此时是在ArrayList对象刚被创建出来后,第一次添加新元素,那么此时size++的值为0

需要注意的是,在创建ArrayList对象时,构造器只是将一个空数组对象给了元素集合,此时的元素集合为null,是无法向其中添加新元素的。那么Java又是怎么向空的元素集合中添加新元素的呢?原因就在第一行代码ensureCapacityInternal(size + 1);中。

(1)计算容纳量

当第一次向集合中添加元素时,需要对原本为空的集合对象进行扩容,而扩容的前置条件就是要先计算出集合需要多大的容量才合适。

此时的集合就像是一个还没开工建设的蓄水池,建设蓄水池的土地已经规划好,现在就差设计蓄水池的尺寸了,而集合的容量就是蓄水池的尺寸。

那么我们接下来看看Java是怎么计算集合容量的。

还是接着看代码,进入到ensureCapacityInternal()方法内,可以看到以下代码:

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

我们先从入参minCapacity看起,入参minCapacity的值为size + 1,此时size的值为0。因此,入参minCapacity的值为0 + 1 = 1

接着,我们进入到方法体中,第一行代码是个判断if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA),先判断元素集合elementData是否是空对象(DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值为{},空对象),如果为空的话,说明是第一次添加元素,需要先确定最小容纳量(minCapacity);如果不为空的话,直接使用入参的最小容纳量minCapacity。最小容纳量是取DEFAULT_CAPACITYminCapacity两值中的最大值,其中,minCapacity的值为1DEFAULT_CAPACITY的值为一个常量,从代码中可以看到其值为:

private static final int DEFAULT_CAPACITY = 10;

从这里就可以看出,ArrayList集合的初始的长度是10

现在元素集合的最小容纳量minCapacity的值已经知道了,那就是10。接下来就要确认这个最小容纳量minCapacity是否适合给集合使用。

(2)确认最小容纳量

最小容纳量已经确定值为10了,那么接下来就需要确认这个值是否真正适合集合使用。

接着看代码,进入ensureExplicitCapacity()方法中:

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

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

第一行代码是记录集合进行变长操作的次数,可以先不管它。

主要是看下面几行的代码,先判断给的最小容纳量minCapacity是否能包住集合内现有元素的个数,如果最小容纳量minCapacity大于此时集合内元素个数的话,那么就执行grow()方法,否则就不对集合进行操作。

确定计算出的最小容纳量minCapacity是适合集合的,那么就要对集合进行扩容了(此时的集合还为空)。

(3)扩容集合

进入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);
}

grow()方法的处理逻辑可以总结成以下几步:

自此,向集合中添加新元素的操作完成。

2.2 插入元素

插入新元素的话,需要使用add(index, element)方法。这个方法不仅仅需要传入新元素的值element,同时也要传入要插入的索引值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++;
}

tips:
需要额外解释的是第三、四、五步的逻辑:对数组进行重新拷贝System.arraycopy(elementData, index, elementData, index+1, size - index);System.arraycopy(初始数组, 初始数组中需要移动元素的开始索引值, 目标数组, 目标数组中需要移动元素的开始索引值, 需要移动元素的个数);将新元素的值赋值给集合中对应索引位置elementData[index] = element;集合的长度加一size++;

  1. 假设有一个长度为5的对象数组elementData,其元素分布为:
0 : [test1]
1 : [test2]
2 : [test3]
3 : [test4]
4 : [test5]
  1. 现在,我希望在索引值为1的元素位置上插入一个新的元素test100
  2. 那么我可以对原始数组elementData进行复制,这个新的数组我还是称它为elementData,其长度也为5,第一个元素的值同样是test1
  3. 不同的是,从第二个元素开始,此后的所有元素将要被往后移动一个索引值。也就是说,在原始数组中索引值是index的元素,在新数组中的索引值要变成index+1,总共要操作4size - index)个元素。
0 : [test1]
→ [test100]
1 : [test2] ↓
2 : [test3] ↓
3 : [test4] ↓
4 : [test5] ↓
  1. 由于插入了新的元素,因此,集合的长度要加一,由原来的5变成了6。那么,经过这一番操作后,新数组的元素分布为:
0 : [test1]
1 : [test100]
2 : [test2]
3 : [test3]
4 : [test4]
5 : [test5]

3. 修改元素

修改集合中的元素,可以通过ArrayList类本身的set()方法,也可以通过迭代器(ListItr)的set()方法修改。需要注意的是,通过迭代器修改元素的话,需要先遍历集合,而且只能修改被遍历过的最后一个元素,而且其底层的实现也是调用ArrayList类本身的set()方法,因此,这里只对ArrayList类本身的set()方法进行源码解读。

废话少说,上set()方法的代码。

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

可以看到方法的入参有两个,分别是要修改元素的索引index、被修改的元素element

方法体中第一行代码rangeCheck(index);是对索引进行检查,看看是否超过集合长度,如果超过了集合的长度就抛出IndexOutOfBoundsException的异常。

接下来是保存将要被修改元素的原始值,赋值给oldValue(最后将会被返回)。

最后是通过索引,将新元素赋值给索引对应的集合位置,完成元素的替换。


4. 查看元素

查看元素的值非常简单,同修改元素类似,也有两种查看方式。一种是通过ArrayList类自带的get()方法查看;另一种方法是通过迭代器的方式遍历查看。两种方法的处理逻辑类似,都是通过索引的方式获取元素并返回。

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

查看元素的逻辑非常简单,第一步还是先检查入参的索引`index是否超过了集合的长度;第二步是返回集合对应索引位置的元素。


5. 删除元素

当我们希望删除一个元素时,需要知道被删除的元素的索引或元素本身的值。通过使用remove()方法,入参可以是索引值,也可以是元素本身的值。

5.1 通过索引值删除元素

首先先解读通过索引值删除元素的代码。

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;

    return oldValue;
}

tips:
需要额外解释的是第四步和第五步的逻辑:获取需要被移动元素的个数int numMoved = size - index - 1;对数组进行重新拷贝System.arraycopy(elementData, index+1, elementData, index, numMoved);

  1. 假设有一个长度为5的对象数组elementData,其元素分布为:
0 : [test1]
1 : [test2]
2 : [test3]
3 : [test4]
4 : [test5]
  1. 现在,我希望移除索引值为1的元素,即第二个元素[test2]。那么我可以对原始数组elementData进行复制,这个新的数组我还是称它为elementData,其长度也为5,第一个元素的值同样是test1
  2. 不同的是,第二个元素将要被移除,从第三个元素(index+1)开始,往后的每个元素都要被往前挪一个位置。也就是说,在原始数组中索引值是index+1的元素,在新数组中的索引值要变成index,总共要操作3numMoved)个元素。
0 : [test1]
1 : [test2] ×
2 : [test3] ↑
3 : [test4] ↑
4 : [test5] ↑
  1. 最后一个元素直接置为空。那么,经过这一番操作后,新数组的元素分布为:
0 : [test1]
1 : [test3]
2 : [test4]
3 : [test5]
4 : []

5.2 通过元素值删除元素

也可以通过元素值来删除元素。

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;
}

通过元素值删除元素的逻辑是通过遍历的方式,找到元素值符合的元素,通过调用fastRemove()方法进行删除,如果方法不报错,则返回true,否则,返回false

fastRemove()方法的代码与通过索引值删除元素的逻辑差不多,具体代码如下:

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
}

可以看到,这段代码的逻辑与通过索引值删除元素的逻辑差不多,较大的差别是,通过索引值删除元素的返回值是被删除的元素,而这段代码没有返回值。


(二)总结

通过从默认构造器入手,到添加元素、修改元素、查看元素、删除元素这四中操作,可以说对ArrayList的实现原理有了基本的了解。

ArrayList就是通过操作可变数组来实现对数据的增、删、改、查操作。采用可变数组的方式擅长随机访问元素,但是在数组的中间插入和移除元素时较慢。所以,当我们在使用List时,需要根据实际情况,考虑是否选择ArrayList

上一篇下一篇

猜你喜欢

热点阅读