关于arraylist:Java经典笔试题可以手写一个ArrayList的简单实现吗

面试官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相干文章，学习材料都会在外面更新，整顿的材料也会放在外面。

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