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

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