add()方法重写,在具体位置增加元素
// 在具体位置增加元素 public void add(int index, int element){ // 首先判断索引,index可以等于size，相当于在末尾添加元素 if (index < 0 || index > size){ throw new IndexOutOfBoundsException("index=" + index + ",size=" + size); } // 要在指定索引增加元素，要现将这个索引位置及之后的元素往后移动一个索引，腾出位置 // 挪动元素，从最后一个开始挪动，否则后一个元素会被前一个元素覆盖 for (int i = size - 1; i > index; i--) { elements[i + 1] = elements[i]; } elements[index] = element; // 增加size size ++; } 复制代码
测试
@Test public void add() { System.out.println(arrayList.toString()); arrayList.add(9); System.out.println(arrayList.toString()); arrayList.add(2,11); System.out.println(arrayList.toString()); } 复制代码
0表示数组中空闲的位置
add(int element)可以优化为
public void add(int element){ // 数组末尾添加元素 add(size,element); } 复制代码
解决数组的致命弱点-无法动态扩容
如果数组的容量快被占满，则需要向内存申请一块空间用来保存数据，让变量指向新的内存空间，原来的内存空间没有变量指向，将会被回收，回收前需要将原数组中的数据拷贝到新的数组中，并且新数组的容量相应扩展2倍或者一个根据使用情况适合的倍数
增加一个扩容函数
// 扩容方式一，使用指定扩容，方法中自行作判断何时需要扩容，调用时传入扩容的大小 private void expansionCapacity(int newCapacity){ int oldCapacity = elements.length; if (oldCapacity >= size + 1) return; // 创建一个新的容量的数组 // newCapacity = oldCapacity + (oldCapacity >> 1); int[] newElements = new int[newCapacity]; // 拷贝元素 for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } // 指向新的内存空间 elements = newElements; System.out.println("扩容成功,由" + oldCapacity + "扩展至" + newCapacity); } 复制代码
在add(int index, int element)方法中判断完index之后加入该方法
// 在具体位置增加元素 public void add(int index, int element){ // 首先判断索引,index可以等于size，相当于在末尾添加元素 if (index < 0 || index > size){ throw new IndexOutOfBoundsException("index=" + index + ",size=" + size); } // 如果容量到达临界点会自动扩容，容量扩为原来的1.5倍 expansionCapacity(elements.length + (elements.length >> 1)); // 挪动元素，从最后一个开始挪动，否则后一个元素会被前一个元素覆盖 for (int i = size - 1; i > index; i--) { elements[i + 1] = elements[i]; } elements[index] = element; // 增加size size ++; } 复制代码
再次进行优化
将判断索引抽取为工具类中的静态方法，新建utils包，增加工具类CheckUtils
public class CheckUtils { private static void outOfBoundary(int index,int size){ throw new IndexOutOfBoundsException("index=" + index + ",size=" + size); } public static void checkIndex(int index, int size){ if (index < 0 || index >= size){ outOfBoundary(index, size); } } public static void checkIndex4Add(int index, int size){ if (index < 0 || index > size){ outOfBoundary(index, size); } } } 复制代码
最终BasicArrayList的代码为
public class BasicArrayList { // 元素的个数 private int size; // 数组 private int[] elements; private static final int DEFAULT_CAPATICY = 10; private static final int ELEMENT_NOT_FOUND = -1; public BasicArrayList(int capaticy){ // 如果capaticy < 10 就使用默认的容量，否则使用自定义的容量 capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy; elements = new int[capaticy]; } public BasicArrayList(){ elements = new int[DEFAULT_CAPATICY]; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } public int get(int index){ CheckUtils.checkIndex(index,size); return elements[index]; } public int set(int index, int element){ CheckUtils.checkIndex(index,size); int old = elements[index]; elements[index] = element; return old; } public int indexOf(int element){ for (int i = 0; i < size; i++) { if (elements[i] == element) return i; } return ELEMENT_NOT_FOUND; } public boolean contains(int element){ return indexOf(element) != ELEMENT_NOT_FOUND; } // 清空即无法访问任何一个元素 public void clear(){ size = 0; } public int remove(int index){ // 首先判断index CheckUtils.checkIndex(index,size); int old = elements[index]; // 只遍历需要挪动的部分，不需要遍历整个数组 for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } size --; return old; } public void add(int element){ // 数组末尾添加元素 add(size,element); } // 在具体位置增加元素 public void add(int index, int element){ // 首先判断索引,index可以等于size，相当于在末尾添加元素 CheckUtils.checkIndex4Add(index,size); // 增加一个元素，如果超过容量就扩容 // 如果容量到达临界点会自动扩容，扩容1.5倍 expansionCapacity(elements.length + (elements.length >> 1)); // 挪动元素，从最后一个开始挪动，否则后一个元素会被前一个元素覆盖 for (int i = size - 1; i > index; i--) { elements[i + 1] = elements[i]; } elements[index] = element; // 增加size size ++; } // 方法中自行作判断，调用时传入扩大的容量 private void expansionCapacity(int newCapacity){ int oldCapacity = elements.length; if (oldCapacity >= size + 1) return; // 创建一个新的容量的数组 // newCapacity = oldCapacity + (oldCapacity >> 1); int[] newElements = new int[newCapacity]; // 拷贝元素 for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } // 指向新的内存空间 elements = newElements; System.out.println("扩容成功,由" + oldCapacity + "扩展至" + newCapacity); } private void ensureCapacity(int capacity){ int oldCapacity = elements.length; if (oldCapacity >= capacity) return; // 创建一个新的容量的数组 int newCapacity = oldCapacity + (oldCapacity >> 1); int[] newElements = new int[newCapacity]; // 拷贝元素 for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } // 指向新的内存空间 elements = newElements; System.out.println("扩容成功,由" + oldCapacity + "扩展至" + newCapacity); } @Override public String toString() { return "ArrayList{" + "size=" + size + ", elements=" + Arrays.toString(elements) + '}'; } } 复制代码
测试add
@Test public void add() { System.out.println(arrayList.toString()); arrayList.add(9); System.out.println(arrayList.toString()); arrayList.add(2,11); System.out.println(arrayList.toString()); arrayList.add(12); System.out.println(arrayList.toString()); } 复制代码
