一、ArrayList集合的原理
看过ArrayList源码的小伙伴都知道，ArrayList集合的底层是用的数组的结构实现的，那我们今天就尝试自己动手造一个属于自己的CommonList集合类，从而更好的理解ArrayList的底层是如何实现的。
二、CommonList集合的构成
首先我们需要构造两个成员变量，一个是Object[]数组，一个int类型的数组里面的元素个数。
我们要实现方法有：
加入方法：
/**
* 加入操作
*/
public void add(T t) ;
删除方法：
/**
* 删除操作
*/
public boolean remove(T t) ;
查询方法：
/**
* 查询操作
*/
public T get(int index) ;
包含方法：
/**
* 是否包含某一个元素操作
*/
public boolean isContain(T t) ;
获取集合元素个数的方法：
/**
* 获取集合长度的方法
*/
public int length()
三、开始代码实现：
/**
* @author:
* @date: 2022/3/7 10:03
* @description:
*/
public class CommonList<T> {
/**
* 数组成员变量
*/
private T[] elementData;
/**
* 数组元素个数
*/
private int elementCount;
/**
* 默认初始化长度
*/
private int default_capacity = 10;
/**
* 带参构造
*
* @param capacity
*/
public CommonList(int capacity) {
this.elementData = (T[]) new Object[capacity];
this.elementCount = 0;
}
/**
* 无参构造
*/
public CommonList() {
this.elementData = (T[]) new Object[default_capacity];
this.elementCount = 0;
}
/**
* 判断当前数组是否为空
*
* @return
*/
public boolean isEmpty() {
return this.elementCount == 0;
}
/**
* 加入操作
*
* @param t
*/
public void add(T t) {
// 当前数组元素个数等于数组的长度，需要扩容
if (elementCount == elementData.length) {
reSize(2 * elementCount);
}
// 当前位置插入一个对象
elementData[elementCount] = t;
// 数组长度+1
this.elementCount = this.elementCount + 1;
}
/**
* 加入指定位置操作
*
* @param index
* @param t
*/
public void add(int index, T t) {
// 校验参数和数组长度
if (index >= elementCount) {
throw new IllegalArgumentException("集合长度没有那么长");
}
// 当前数组元素个数等于数组的长度，需要扩容
if (elementCount == elementData.length) {
reSize(2 * elementData.length);
}
// 给数组增加一个空对象元素
elementData[elementCount] = null;
// 从数组增加的最后一个null位置开始遍历，然后将所有的元素向后挪一位，空出来位置我们插入我们的对象
for (int i = elementCount; i > index - 1; i--) {
elementData[i] = elementData[i - 1];
}
// 给空出来的这位赋值操作
elementData[index] = t;
// 当前数组长度+1
this.elementCount = this.elementCount + 1;
}
/**
* 获取集合长度的方法
*
* @return
*/
public int length() {
return elementCount;
}
/**
* 获取index位置的对象
*
* @param index
* @return
*/
public T get(int index) {
// 校验参数和数组长度
if (index >= elementCount) {
throw new IllegalArgumentException("集合长度没有那么长");
}
// index从0开始
return elementData[index];
}
/**
* 删除集合元素
*
* @param t
* @return
*/
public void remove(T t) {
for (int i = 0; i < elementCount; i++) {
if (elementData[i].equals(t)) {
remove(i);
}
}
// 如果删除后的元素个数小于数组的四分之一长度，数组长度缩容一半
if (elementCount < elementData.length / 4) {
reSize(elementData.length / 2);
}
}
/**
* 删除指定位置元素，并返回删除后的数组集合
*
* @param index
* @return
*/
private Object[] remove(int index) {
// 校验参数和数组长度
if (index >= elementCount) {
throw new IllegalArgumentException("集合长度没有那么长");
}
// 从准备删除的地方往后遍历
for (int i = index; i < elementCount; i++) {
T temp = elementData[i + 1];
elementData[i] = temp;
}
this.elementCount = this.elementCount - 1;
return elementData;
}
/**
* 校验当前集合中是否包含某一个元素
*
* @param t
* @return
*/
public boolean isContain(T t) {
// 遍历所有元素，比较元素与参数的值
for (int i = 0; i < elementCount; i++) {
if (elementData[i].equals(t)) {
return true;
}
}
return false;
}
/**
* 集合扩容，缩容
* 在新增，删除的时候需要加入扩容，缩容操作
*
* @param newCapacity
*/
private void reSize(int newCapacity) {
// 创建一个临时数组接收原来的数组
T[] temp = elementData;
// 新创建一个新的扩容数组指向原来的数组
elementData = (T[]) new Object[newCapacity];
// 将原来数组里面的数据给赋值到新的数组中
for (int i = 0; i < temp.length; i++) {
elementData[i] = temp[i];
}
}
}
里面好像没有遍历的方法，其实这个也是可以实现的。需要实现Iterable接口，并且还需要自己写一个iterator的实现类，去实现里面的接口方法。
四、测试：
public class CommonListTest {
public static void main(String[] args) {
CommonList<String> list = new CommonList<>(3);
list.add("嘿嘿");
list.add("哈哈");
list.add("嘻嘻");
list.add(1,"噢噢");
// 能这样写是因为CommonList实现了Iterable接口
for (String s: list) {
System.out.println(s);
}
System.out.println(list.isContain("啦啦"));
System.out.println("=======================");
list.remove("哈哈");
// 最原始的遍历方法
for(int i=0;i<list.length();i++){
System.out.println(list.get(i));
}
}
}
测试结果：
嘿嘿
噢噢
哈哈
嘻嘻
false
=======================
嘿嘿
噢噢
嘻嘻
五、总结：
以上就实现了我们自己的ArrayList了，里面包含了无参构造，有参构造，list集合的基本的增删查的操作，以及动态的扩容操作。
或许你会疑问，既然jdk给我们封装好了数据结构，我们为何要自己动手去实现，其实你自己实现一遍更加能体会到其中的设计原理，其次就是当我们的业务场景需要一种数据结构如果jdk自带的数据结构无法满足的时候，我们可以尝试自己去实现一个，更加贴近业务的数据结构，并解决问题。
网友评论