《恋上数据结构与算法》第1季：动态数组原理实现（图文并茂，一文带你了解ArrayList底层实现）

一、数组（Array）

• 数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。

int[] array = new int[]{
    11,22,33};
1
2

在很多编程语言中，数组有个致命的缺点，无法动态修改容量；
实际开发中，我们希望数组的容量是动态变化的。

二、动态数组

1. 可以通过数组实现一个动态数组，动态数组的容量是动态变化的
2. 可以对动态数组进行增删改查等操作

// 元素的数量
int size(); 
// 是否为空
boolean isEmpty();
// 是否包含某个元素
boolean contains(E element); 
// 添加元素到最后面
void add(E element); 
// 返回index位置对应的元素
E get(int index); 
// 设置index位置的元素
E set(int index, E element); 
// 往index位置添加元素
void add(int index, E element); 
// 删除index位置对应的元素 
E remove(int index); 
// 查看元素的位置
int indexOf(E element); 
// 清除所有元素
void clear(); 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、动态数组的设计

• 创建类 ArrayList 如下图，创建 size 属性来管理数组中元素的个数，创建 elements 属性来管理存取的数据。
  

public class ArrayList<E> {
    
	private int size;
	private E[] elements;
}
1
2
3
4
5

• 添加初始化方法，创建 elements 数组，并指定 elements 默认的容量

public class ArrayList<E> {
    
	private int size;
	private E[] elements;
	// 设置elements数组默认的初始化空间
	private static final int CAPACITY_DEFAULT = 10;
	
	public ArrayList(int capacity) {
    
		// 如果当前数组长度小于默认容量，则设定为默认容量DEFAULT_CAPACITY 10，否则是capacity
		capacity = (capacity < CAPACITY_DEFAULT) ? CAPACITY_DEFAULT : capacity;
		elements = (E[]) new Object[capacity];// 进行动态确定数组容量
		// 注意：写成new E[capaticy]是错误的，必须写为其父类Object，然后再强制转换
	}
	// 默认情况
	public ArrayList() {
    
		this(CAPACITY_DEFAULT);// 调用有参构造方法，对数组进行定义
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

四、动态数组的实现

1. 添加元素

1. 我们知道，每当数组添加新元素时，都会在数组最后一个元素的后面添加新元素；
2. 这个 新元素需要添加到的索引 等于 当前数组元素的个数，在ArrayList 中 size 属性就是 当前数组元素的个数，所以就是将新元素添加到数组的 size 位置上，然后 size 加 1。
   

public void add(E element) {
    
	elements[size] = element;
	size++;
}
1
2
3
4
5

2. 数组扩容

1. 由于数组elements最大的容量只有10, 所以当数组存满元素时, 就需要对数组进行扩容
2. 因为数组是无法动态扩容的,所以需要创建一个新的数组,这个数组的容量要比之前数组的容量大
3. 然后在将原数组中的元素存放到新数组中, 这样就实现了数组的扩容
   

// 扩容
private void ensureCapacity(){
    
    // 获取数组当前容量(长度)
    int oldLength = elements.length;
    // 如果 当前存储的元素个数(size) < 当前数组容量，直接返回
    if(size < oldLength){
    
        return;
    }
    // 新数组的容量为原数组容量的1.5倍
    int newCapacity = oldLength + (oldLength >> 1);
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    //原数组中的元素存储到新数组中
    for(int i = 0; i < size; i++){
    
        newElements[i] = elements[i];
    }
    // 引用新数组(新数组的索引要指向旧数组的索引)
    elements = newElements;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. 此时，add 方法的实现如下，在添加新元素之前，先判断是否需要扩容

public void add(E element){
    
    // 添加新元素之前，先判断是否需要扩容
    ensureCapacity();
    elements[size] = element;
    size++;
}
1
2
3
4
5
6
7

3. 删除元素

1. 删除元素，实际上就是去掉 指定位置的元素，并将后面的元素 向前移动
2. 如下图，当删除索引为 2 的元素，只需要将后面的元素向前面移动，然后去掉最后一个元素，