Java进阶（3）——手动实现ArrayList 源码的初步理解分析 数组插入数据和删除数据的问题

引出

---

1.ArrayList的结构分析，可迭代接口，是List的实现；
2.数组增加元素和删除元素的分析，何时扩容，如何扩容；
3.插入数据的复杂度O(N)；
4.数组特点：查找和修改容易O(1)；增加和删除复杂O(N)；

手动实现ArrayList

定义接口MyList<T>

package com.tianju.book.jpa.mlist;/*** 手工打造ArrayList*/
public interface MyList<T> {/*** 增加一个元素，涉及到容量的变化*/void add(T t);/*** 根据索引删除元素* @param index 要删除元素的索引，超过索引？索引不存在？*/void remove(int index);/*** 根据索引修改一个元素* @param index 要修改的索引* @param t 修改的值*/void set(int index,T t);/*** 根据索引获取元素* @param index 索引* @return 获取的元素*/T get(int index);int size();String toString();}

写ArrayList的实现类

增加元素

• 如果放不下怎么办？如何扩容？
• 扩容后如何操作？

扩容：每次为原来的1.5倍

如果放不下，就扩容；

扩容后把原来的数据一个一个再放回去；

删除元素

源码分析

• 删除头部，尾部，中间——最一般的就是中间元素被删除；
• 此时需要跳过被删除的元素，把没有被删除的放回去；

package com.tianju.book.jpa.mlist;public class MyArrayList<T> implements MyList<T> {private int size; // 不写初始值为0private Object[] elementData = new Object[5]; // 自己的ArrayList的默认大小是5@Overridepublic void add(T t) {// 如果放不下就要扩容if (size+1>=elementData.length){// >> 位运算，右移相当于除以2，所以新的长度是原来的1.5倍int newLen = elementData.length + (elementData.length>>1);// 这里相当于新建一个数组，把原来的一个一个放进去，然后把elementData指向新的数组
//            elementData = Arrays.copyOf(elementData, newLen); // arrays工具类的实现Object[] newElementData = new Object[newLen];for(int i=0;i<elementData.length;i++){newElementData[i] = elementData[i];}elementData = newElementData;System.out.println("扩容后长度"+elementData.length);}elementData[size] = t;//把新的元素放过来size = size + 1; // 新的size比原来加1}@Overridepublic void remove(int index) {// 删除怎么搞？// 删除头部？尾部？中间？// 这里采用新建一个数组，跳过要删除的那个元素，一个一个再放回去Object[] newElementData = new Object[elementData.length]; // 和原来大小一样int j = 0; // 新的索引for (int i=0;i<size;i++){if (i==index){System.out.println(index+"跳过: "+elementData[i]);continue;}newElementData[j] = elementData[i];j++; // 跳过被删除的那个索引}elementData = newElementData; // 再指向新的数组size--; // 删除元素后size-1}@Overridepublic void set(int index, T t) {// 修改的复杂度为O(1)if (index>=size){throw new IndexOutOfBoundsException("索引越界");}elementData[index] = t;}@Overridepublic T get(int index) {// 根据索引获取元素的复杂度也为O(1)// 需要判断索引是不是超了if (index>=size){throw new IndexOutOfBoundsException("索引越界");}return (T) elementData[index];}@Overridepublic int size() {return this.size;}@Overridepublic String toString(){String str ="[";for (int i =0;i<size;i++){str += elementData[i] + ",";}str +="]";return str;}
}

写测试类进行测试

package com.tianju.book.jpa.mlist;import java.util.ArrayList;
import java.util.List;public class MyListTest {public static void main(String[] args) {MyList<String> myList = new MyArrayList<>();System.out.println(myList.size());myList.add("Peter001");myList.add("Peter002");myList.add("Peter003");myList.add("Peter004");System.out.println(myList.size());myList.add("Peter005");System.out.println("目前List中元素的数量"+myList.size());System.out.println(myList);System.out.println("*******删除一个元素*******");myList.remove(1);System.out.println(myList);System.out.println("删除元素后list长度："+myList.size());myList.add("shirley");System.out.println("新增shirley元素后list："+myList);System.out.println("长度："+myList.size());System.out.println("*******修改一个元素*******");myList.set(0, "zgg");System.out.println(myList);System.out.println("*******查询一个元素*******");String s = myList.get(2);System.out.println("索引为2的元素为："+s);System.out.println("索引越界的情况");System.out.println(myList.get(10));List<String> strings = new ArrayList<>();System.out.println(strings.size());}
}

数组插入数据?

插人和删除的花费却潜藏着昂贵的开销，这要看插入和删除发生在什么地方。最坏的情形下，在位置0的插入（即在表的前端插入）首先需要将整个数组后移一个位置以空出空间来，而删除第一个元素则需要将表中的所有元素前移一个位置，因此这两种操作的最坏情况为O(N)。

平均来看，这两种操作都需要移动表的一半的元素，因此仍然需要线性时间。另一方面，如果所有的操作都发生在表的高端，那就没有元素需要移动，而添加和删除则只花费O(1)时间。

存在许多情形，在这些情形下的表是通过在高端进行插入操作建成的，其后只发生对数组的访问（即只有findKth操作）。在这种情况下，数组是表的一种恰当的实现。然而，如果发生对表的一些插入和删除操作，特别是对表的前端进行，那么数组就不是一种好的选择。另一种数据结构：链表(linked list)。

---

总结

1.ArrayList的结构分析，可迭代接口，是List的实现；
2.数组增加元素和删除元素的分析，何时扩容，如何扩容；
3.插入数据的复杂度O(N)；
4.数组特点：查找和修改容易O(1)；增加和删除复杂O(N)；