面试官Q1：能够手写一个ArrayList的简略实现吗？

咱们都晓得ArrayList是基于数组实现，如果让你实现JDK源码ArrayList中add()、remove()、get()办法，你晓得如何实现吗？这一节，咱们不看源码，咱们想想如何简略的实现ArrayList几个根本办法？

确定数据结构

咱们晓得，ArrayList中无论什么数据都能放，是不是意味着它是一个Object类型，既然是数组，那么是不是Object[]数组类型的？所以咱们定义的数据结构如下：

private Object[] elementData;  private int size;

设置自定义的MyArrayList的长度为10

public MyArrayList(){         this(10);     }      public MyArrayList(int initialCapacity){         if(initialCapacity<0){            try {                 throw new Exception();             } catch (Exception e) {                e.printStackTrace();            }        }        elementData = new Object[initialCapacity];    }

有了存放数据的地位，接下来，咱们想想如何将数据放入数组？

增加数据

public void add(Object obj){        elementData[size++]=obj;}

每增加一个元素，size就会自增1，咱们定义的数组长度为10，当咱们增加到11个元素的时候，显然没有中央寄存新增加的数据，这个时候咱们须要对数组进行扩容解决

对下面代码做如下批改：

 public void add(Object obj){         if(size==elementData.length){            //创立一个新的数组，并且这个数组的长度是原数组长度的2倍             Object[] newArray = new Object[size*2];            //应用底层拷贝，将原数组的内容拷贝到新数组             System.arraycopy(elementData, 0, newArray, 0, elementData.length);            //并将新数组赋值给原数组的援用             elementData = newArray;         }        //新来的元素，间接赋值        elementData[size++]=obj;}

用一张图来示意就是这样的：

查问数据

接着咱们看一下删除的操作。ArrayList反对两种删除形式：

  • 依照下标删除
  • 依照元素删除，这会删除ArrayList中与指定要删除的元素匹配的第一个元素

对于ArrayList来说，这两种删除的办法差不多，都是调用的上面一段代码：

 public void remove(int index){         //删除指定地位的对象         //a b d e         int numMoved = size - index - 1;         if (numMoved > 0){             System.arraycopy(elementData, index+1, elementData, index,                     numMoved);         }         elementData[--size] = null; // Let gc do its work}

其实做的事件就是两件:

  • 把指定元素前面地位的所有元素，利用System.arraycopy办法整体向前挪动一个地位
  • 最初一个地位的元素指定为null，这样让gc能够去回收它

用图示意是这样的：

指定地位增加数据

把从指定地位开始的所有元素利用System,arraycopy办法做一个整体的复制，向后挪动一个地位（当然先要用ensureCapacity办法进行判断，加了一个元素之后数组会不会不够大），而后指定地位的元素设置为须要插入的元素，实现了一次插入的操作。

public void add(int index,Object obj){        ensureCapacity();  //数组扩容        System.arraycopy(elementData, index, elementData, index + 1,                 size - index);        elementData[index] = obj;        size++;}

用图示意这个过程是这样的：

总结一下

从下面的几个过程总结一下ArrayList的特点：

  • ArrayList底层以数组实现，是一种随机拜访模式，通过下标索引定位数据，所以查找十分快
  • ArrayList在程序增加一个元素的时候十分不便，只是往数组外面增加了一个元素而已(这里指的开端增加数据)
  • 当删除元素的时候，波及到一次元素复制移位，如果要复制的元素很多，那么就会比拟消耗性能
  • 当插入元素的时候，波及到一次元素复制移位，如果要复制的元素很多，那么就会比拟消耗性能

因而，ArrayList比拟适宜程序增加、随机拜访的场景。

写在最初

欢送大家关注我的公众号【惊涛骇浪如码】，海量Java相干文章，学习材料都会在外面更新，整顿的材料也会放在外面。

感觉写的还不错的就点个赞，加个关注呗！点关注，不迷路，继续更新！！！