乐趣区

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

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

退出移动版