前言
- 开了一个新的系列,自己动手撸简化版的 Java 集合,在实践中学习数据结构
- 参考资料来自小码哥的数据结构和算法视频课,地址在文章尾部,感觉是最好的数据结构算法课了,手把手带我敲代码和优化代码,很多写法和 JDK 源码很相似,顺便把源码给看了,一举两得
数组
- 数组是一种顺序存储的线性表, 所有元素的内存地址都是连续的
- 在很多编程语言中,数组有个致命的缺点,无法动态修改容量
实现 ArrayList
希望实现一个动态数组,数组容量可以动态变化,并且实现增、删、改、查、插、遍历等操作
1. 属性
底层使用数组存储元素,size 记录当前已经存入的元素个数
| 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. 构造器
提供两个构造器,可以指定初始容量
| 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
| public void add(E ele) { add(size,ele); }
public void add(int index,E ele) { checkRangeForAdd(index);
ensureCapacity(size+1);
for(int i=size;i>index;i--) { elements[i] = elements[i-1]; } elements[index] = ele; size++; }
|
4.1 扩容机制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| private void ensureCapacity(int capacity) { int oldCapacity = elements.length; if(oldCapacity >= capacity) { return; }
int newCapacity = oldCapacity + (oldCapacity >> 1); E[] newElements = (E[]) new Object[newCapacity]; for(int i=0;i<size;i++) { newElements[i] = elements[i]; } elements = newElements; }
|
4. 删除元素
如果有需求,可以在删除元素后进行缩容,但是要注意,扩容的倍数和缩容的时机设计不合理(互为倒数),会导致复杂度振荡,也就是在缩容时机附近反复添加删除元素,会导致复杂度急剧上升
| public E remove(int index) { checkRange(index); E old = elements[index]; for(int i=index+1;i<size;i++) { elements[i-1] = elements[i]; } elements[--size] = null; trim(); return old; }
|
4.1 缩容机制
| 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 作为垃圾回收
| public void clear() { for(int i=0;i<size;i++) { elements[i] = null; } size = 0; }
|
6. 设置元素
| public E set(int index,E ele) { checkRange(index); E old = elements[index]; elements[index] = ele; return old; }
|
7. 获取元素
| public E get(int index) { checkRange(index); return elements[index]; }
|
8. 判断是否为空
| public boolean isEmpty() { return size==0; }
|
9. 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
| public int indexOf(E target) { 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. 是否包含元素
| public boolean contain(E target) { return indexOf(target) != MINUS_ONE; }
|
12. 打印
重写 toString 方法
| @Override public String toString() { StringBuilder str = new StringBuilder(); str.append("size=").append(size).append(", ["); 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
| private void indexOutOfBounds() { throw new IndexOutOfBoundsException("数组索引越界!"); }
private void checkRange(int index) { if(index<0||index>=size) { indexOutOfBounds(); } }
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)$ |
参考