面试官 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;
- }
用一张图来表示就是这样的:
查询数据
- public Object get(int index){
- return elementData[index];
- }
删除数据
接着我们看一下删除的操作. 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 比较适合顺序添加, 随机访问的场景.
来源: https://www.cnblogs.com/marsitman/p/11204338.html