数据结构 动态数组ArrayList

前言

  • 开了一个新的系列,自己动手撸简化版的 Java 集合,在实践中学习数据结构
  • 参考资料来自小码哥的数据结构和算法视频课,地址在文章尾部,感觉是最好的数据结构算法课了,手把手带我敲代码和优化代码,很多写法和 JDK 源码很相似,顺便把源码给看了,一举两得

数组

  • 数组是一种顺序存储的线性表, 所有元素的内存地址都是连续的
  • 在很多编程语言中,数组有个致命的缺点,无法动态修改容量

数组

  • 实际开发中我们希望数组的容量是动态变化

实现 ArrayList

希望实现一个动态数组,数组容量可以动态变化,并且实现增、删、改、查、插、遍历等操作

1. 属性

底层使用数组存储元素,size 记录当前已经存入的元素个数

1
2
3
4
5
6
7
8
9
10
public class ArrayList<E> {
// 当前存储的数据的长度(元素个数)
private int size = 0;
// 用于存储数据的数组
private E[] elements ;
// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 10;
// 查询不存在时的返回值
private static final int MINUS_ONE = -1;
}

2. 构造器

提供两个构造器,可以指定初始容量

1
2
3
4
5
6
7
8
9
// 空参构造器,数组初始化长度为10;
public ArrayList() {
this(DEFAULT_INITIAL_CAPACITY);
}
// 指定容量的构造器,如果小于默认初始容量,则依旧使用默认初始容量
public ArrayList(int capacity) {
capacity = Math.max(DEFAULT_INITIAL_CAPACITY,capacity);
elements = (E[]) new Object[capacity];
}

3. 添加元素

  • 添加元素之前,要检查底层数组容量是否满足,如果容量不足,需要先进行扩容
  • 添加元素之前,插入位置之后的元素需要从后向前移动元素,如果从前向后移动元素,那么会进行元素覆盖, 最后出错
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 将元素添加至 ArrayList 尾部
public void add(E ele) {
add(size,ele);
}

// 将元素添加至指定 index 处
public void add(int index,E ele) {
checkRangeForAdd(index);

// 添加元素后,size+1,所以要保证数组至少有 size+1 的容量
ensureCapacity(size+1);

// 从后向前依次拷贝元素,tips:尽量减少 for 循环检查条件是有计算 (i>index 这句)
// 可以使用 System 类提供的数组拷贝方法代替,速度更快,这也是 IDEA 推荐的
// if (size - index >= 0) System.arraycopy(elements, index, elements, index + 1, size - index);
for(int i=size;i>index;i--) {
elements[i] = elements[i-1];
}
elements[index] = ele;
size++;
}

4.1 扩容机制

ArrayList扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 扩容机制,保证当前数组容量至少为capacity
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if(oldCapacity >= capacity) {
return;
}

// 位运算,效率更高,容量扩大为之前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 创建一个新的数组,大小为之前数组的 1.5 倍
E[] newElements = (E[]) new Object[newCapacity];
// 拷贝元素
// arraycopy 的机制是整块内存的拷贝
// if (size >= 0) System.arraycopy(elements, 0, newElements, 0, size);
for(int i=0;i<size;i++) {
newElements[i] = elements[i];
}
elements = newElements;
}

4. 删除元素

如果有需求,可以在删除元素后进行缩容,但是要注意,扩容的倍数和缩容的时机设计不合理(互为倒数),会导致复杂度振荡,也就是在缩容时机附近反复添加删除元素,会导致复杂度急剧上升

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 删除 index 位置上的元素,返回被删除的元素
public E remove(int index) {
checkRange(index);
E old = elements[index];
// 从前往后拷贝元素,依然可以用 arraycopy 优化
// if (size - index + 1 >= 0) System.arraycopy(elements, index + 1, elements, index + 1 - 1, size - index + 1);
for(int i=index+1;i<size;i++) {
elements[i-1] = elements[i];
}
// 先size减1,再将size位置上的元素置null
elements[--size] = null;
// 判断数组是否需要缩容
trim();
return old;
}

4.1 缩容机制

1
2
3
4
5
6
7
8
9
10
11
12
13
// 缩容机制
private void trim() {
int oldCapacity = elements.length;
// 如果元素个数大于当前容量的一半,或者容量已经小于默认初始容量,就不要继续缩容
if(size >= oldCapacity >> 1 || oldCapacity <= DEFAULT_INITIAL_CAPACITY) return;
// 缩容为之前的一半
int newCapacity = oldCapacity >> 1;
E[] newElements= (E[]) new Object[newCapacity];
for(int i=0;i<size;i++) {
newElements[i] = elements[i];
}
elements = newElements;
}

5. 清空

清空 ArrayList 需要将每个数组元素置空,再将 size 设置为 0,因为 ArrayList 中存的实际是对象的引用,如果没有引用指向对象,对象就会被 JVM 作为垃圾回收

ArrayList清空

1
2
3
4
5
6
7
// 清空元素
public void clear() {
for(int i=0;i<size;i++) {
elements[i] = null;
}
size = 0;
}

6. 设置元素

1
2
3
4
5
6
7
// 修改指定索引位置上的元素,并返回旧的元素
public E set(int index,E ele) {
checkRange(index);
E old = elements[index];
elements[index] = ele;
return old;
}

7. 获取元素

1
2
3
4
5
6
// 返回指定索引位置上的元素
public E get(int index) {
// 控制入参,如果非法,抛出异常
checkRange(index);
return elements[index];
}

8. 判断是否为空

1
2
3
4
// 判断当前 ArrayList 是否为空
public boolean isEmpty() {
return size==0;
}

9. ArrayList 长度

1
2
3
4
// 返回当前 ArrayList 的长度(元素数量,不是数组容量)
public int size() {
return size;
}

10. 元素的位置

对于 null 的判断需要特别处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 返回 target 元素的第一次出现的索引,如果不存在,返回-1
public int indexOf(E target) {
// 允许存入 null 值,注意不要空指针调用equals()
if(target==null) {
for(int i=0;i<size;i++) {
if(elements[i]==null) {
return i;
}
}
}else {
for(int i=0;i<size;i++) {
if(target.equals(elements[i])) {
return i;
}
}
}
return MINUS_ONE;
}

11. 是否包含元素

1
2
3
4
// 判断当前 ArrayList 是否包含某元素
public boolean contain(E target) {
return indexOf(target) != MINUS_ONE;
}

12. 打印

重写 toString 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append("size=").append(size).append(", [");
// StringBuilder 的 append 方法如果拼接的是对象,会调用其 toString 方法后拼接
for(int i=0;i<size;i++) {
if(i!=0) {
str.append(", ");
}
str.append(elements[i]);
}
str.append("]");
return str.toString();
}

13. 索引检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 入参 index 非法报错
private void indexOutOfBounds() {
throw new IndexOutOfBoundsException("数组索引越界!");
}

// 检查传入的 index 是否满足边界条件
private void checkRange(int index) {
if(index<0||index>=size) {
indexOutOfBounds();
}
}

// 针对 add 方法的索引合法检查,index 可以是 size,即添加至尾部
private void checkRangeForAdd(int index) {
if(index<0||index>size) {
indexOutOfBounds();
}
}

复杂度

对于 add 和 remove 操作,复杂度来自向后或向前移动元素的操作,扩容或缩容的复杂度是 $O(N)$,但是均摊后复杂度依然是 $O(1)$

操作 最好 最坏 平均
add(int index,E ele) $O(1)$ $O(N)$ $O(N)$
remove(int index) $O(1)$ $O(N)$ $O(N)$
set(int index,E ele) $O(1)$ $O(1)$ $O(1)$
get(int index) $O(1)$ $O(1)$ $O(1)$

参考