# 线性表之顺序表ArrayList

# 写在前面

数据结构在面试中基本都是常问的,但是一般开发中基本上都是在使用没有去关心过怎么实现的。

在数据结构中,链表是一种线性存储结构,也就是常说的线性表。

概念:线性表,是数据结构中的一种数据存储结构,数据元素之间具有“一对一”的逻辑关系。可以理解为把所有数据用一根线串起来,在存储到物理空间中

# 顺序表ArrayList

概念:将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表)。类似下图用一个线把他们连接起来,形成一条线性的结构。

ArrayList就是属于这样的一种。

ArrayList是基于数组实现的,数组是一种最简单的数据结构,在使用时必须要给它创建大小,在日常开发中,往往我们是不知道给数组分配多大空间的,如果数组空间分配多了,内存浪费,分配少了,装不下。而ArrayList在使用时可以添加多个元素切不需要指定大小,因为ArrayList是动态扩容的。

# 类的继承关系

image-20210619170015101

# 源码分析

# 类的属性

/**
 * 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 *ArrayList 实际数据存储的一个数组
 *存储ArrayList的元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。
 *添加第一个元素时,任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。
 */
transient Object[] elementData;

/**
 * 共享的空数组实例,用于默认大小的空实例
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * elementData 的大小
 */
private int size;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 类的构造函数

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3

# new ArrayList()做了什么

public class TestClient {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        Integer capacity = getCapacity(list);
        System.out.println("没添加元素时的容量:" + capacity);
        System.out.println("没添加元素时的大小:" + list.size());
        list.add("添加元素");
        capacity = getCapacity(list);
        System.out.println("添加1个元素时的容量:" + capacity);
        System.out.println("添加1个元素时的大小:" + list.size());
    }

    /**
     * 通过反射获取list的容量
     *
     * @param list
     * @return
     */
    public static Integer getCapacity(List<String> list) {
        Integer length = null;
        Class c = list.getClass();
        Field f;
        try {
            f = c.getDeclaredField("elementData");
            f.setAccessible(true);
            Object[] o = (Object[]) f.get(list);
            length = o.length;
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
        return length;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

打印结果

没添加元素时的容量:0
没添加元素时的大小:0
添加1个元素时的容量:10
添加1个元素时的大小:1
1
2
3
4

因此,当new ArrayList()时,默认会有一个空的Object空数组,在没有添加有元素的时候,其初始化容量是0,只有当添加第一个元素的时候,容量才会设置成10。

# 基本方法

# 添加元素add(E e)

/**
 * 将指定的元素追加到此列表的末尾
 */
 public boolean add(E e) {
     ensureCapacityInternal(size + 1);
     //直接赋值
     elementData[size++] = e;
     return true;
}
1
2
3
4
5
6
7
8
9

# add(int index, E element)

在指定索引位置添加元素

image-20210619170102556

String[] elementData = {"1", "2", "3", "4", "5", "6", "7", "8"};
int index = 4;
//从下标为4的位置开始复制,复制的长度为8-4=4(复制"5", "6", "7", "8"),从下标为4+1=5的位置开始替换为"5", "6", "7", "8"
System.arraycopy(elementData, index, elementData, index+1, elementData.length-index);
1
2
3
4

# ArrayList 扩容机制

# ensureExplicitCapacity(int minCapacity)

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

        //如果其元素数量大于其容量,则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
1
2
3
4
5
6
7

# grow(int minCapacity)

    /**
     * 扩容
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        //原来的容量
        int oldCapacity = elementData.length;
        //新的容量  通过位运算右移一位  如,默认为10 10>>1=5  右移过程:10的二进制为  1010   右移1位->0101 转十进制->5
        //可以理解为oldCapacity >> 1 == oldCapacity/2 再加上原来的长度就扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果大于ArrayList 可以容许的最大容量,则设置为最大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

想了解位运算的可以看看这篇文章

Java中的位运算 (opens new window)

ArrayList 的内部实现,其实是用一个对象数组进行存放具体的值,然后用一种扩容的机制,进行数组的动态增长。

其扩容机制可以理解为,如果元素的个数,大于其容量,则把其容量扩展为原来容量的1.5倍。

# 拓展延伸

  • ArrayList的大小是如何自动增加的?
  • 什么情况下你会使用ArrayList?
  • 在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?
  • ArrayList如何顺序删除节点?
  • ArrayList的遍历方法?