目标：手动实现一个动态数组，模拟ArrayList
ArrayList会自动扩容，先来看一下ArrayList扩容规律，size()方法只能得到存储元素的个数，得不到List的容量大小，我们要想办法：
public static void main(String[] args) throws Exception {
//构建一个初始容量为3的ArrayList对象
List<Integer> list = new ArrayList<>(3);
//通过源码可知ArrayList的元素存储在Object[] elementData成员数组中，通过反射可得到该成员变量
Class<? extends List> clazz = list.getClass();
Field f = clazz.getDeclaredField("elementData");
f.setAccessible(true);
//循环增加添加元素，同时通过反射得到elementData成员，并将每一次遍历的所得到的elementData数组长度添加到Set集合中（利用Set去重）
Set<Integer> addSet = new HashSet<>();
for (int i = 0; i < 100; i++) {
list.add(i);
Object[] objects = (Object[]) f.get(list);
addSet.add(objects.length);
}
//循环遍历Set，将Set元素转动到一个List中（因Set存储的元素无序，不方便查看）
List<Integer> addList = new ArrayList<>();
for (Integer i : addSet) {
addList.add(i);
}
//List排序并打印
Collections.sort(addList);
for (Integer i : addList) {
System.out.print(i + " ");
}
System.out.println();
//移除元素，查看elementData长度变化，思路同上
Set<Integer> removeSet = new HashSet<>();
for (int i = list.size() - 1; i >= 0; i--) {
list.remove(i);
Object[] objects = (Object[]) f.get(list);
removeSet.add(objects.length);
}
List<Integer> removeList = new ArrayList<>();
for (Integer i : removeSet) {
removeList.add(i);
}
Collections.sort(removeList);
for (Integer i : removeList) {
System.out.print(i + " ");
}
}
运行得到结果：
3 4 6 9 13 19 28 42 63 94 141
141
规律：
- 添加元素时，容量变化规律：扩容后容量 = 当前容量 * 3 / 2，再向下取整；改变初始容量后，发现规律相同
- 移除元素时，容量不会缩减
根据上面规律，实现一个具备相同扩容规律的动态数组（由于实现List接口，需重写方法太多，这里就不实现List接口了，只模拟增删改查的方法）：
public class MyList<E> {
//当前List的元素个数
private int size;
//默认容量
private static final int DEFAULT_INIT_CAPACITY = 10;
//数组
private Object[] elementData;
//默认构造器
public MyList() {
elementData = new Object[DEFAULT_INIT_CAPACITY];
}
//可指定容量的构造器
public MyList(int initCapacity) {
elementData = new Object[initCapacity];
}
//添加元素
public void add(E e) {
//添加元素前判断当前元素个数和数组长度是否相同，相同则需要扩容
if (size == elementData.length) {
Object[] dest = new Object[elementData.length * 3 / 2];
System.arraycopy(elementData, 0, dest, 0, elementData.length);
elementData = dest;
}
elementData[size++] = e;
}
//移除元素
public void remove(int index) {
System.arraycopy(elementData, index + 1, elementData, index, elementData.length - index - 1);
elementData[--size] = null;
}
//修改元素
public void modify(int index, E e) {
//检查下标是否超出范围
rangeCheck(index);
elementData[index] = e;
}
//查找元素
public E get(int index) {
//检查下标是否超出范围
rangeCheck(index);
return (E) elementData[index];
}
//范围检查
private void rangeCheck(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException("下标越界,index：" + index);
}
}
//获取当前存储元素个数
public int size() {
return size;
}
//打印（用于测试）
public void print() {
System.out.print("[");
for (int i = 0; i < size; i++) {
if (elementData[i] != null) {
if (i != size - 1) {
System.out.print(elementData[i] + ", ");
} else {
System.out.print(elementData[i]);
}
}
}
System.out.println("]");
}
}
测试结果：
public static void main(String[] args) {
MyList<String> myList = new MyList<>(10);
myList.add("a");
myList.add("b");
myList.add("c");
System.out.println(myList.size());//3
myList.print();//[a, b, c]
myList.remove(myList.size() - 1);
myList.print();//[a, b]
myList.modify(0, "aa");
myList.print();//[aa, b]
System.out.println(myList.get(1));//b
}
