前几天看百度面试题,有一道题是手写 Arraylist, 于是一直在心中就想怎么实现,看自己能不能写出,于是翻源码看,感觉有些方法能看懂,但是有些确实需要很高深的数据结构的功底才能写出来,自己心里有点后怕。
但是我不服气啊哈哈!
今天就在 java 交流群里试探大家怎么看这件事,可是好多竟然都说很简单,我不知道那些是装逼的还是真的大神,可是我性格就是不愿意服输,于是下决心今天一定要把它写出来!!!
写 Arraylist 之前要先明白一些要素:
1.ArrayList 的底层是 Object 类的数组,默认长度是 10, 超过 10 后,长度变为原长度的 2 倍。(这个数字可以变)
2.ArrayList 底层是个动态数组实现的,长度不够时,调用 Arrays.copyOf 方法,拷 贝当前数组到一个新的长度更大的数组。如果是数组比较大,那么使用 System.arraycopy 会比较有优势,因为其使用的是内存复制,省去了大量的数组寻址访问等时间,所以我实现的方法全部用 System.arraycopy。
3. 因为是自己实现,所以只能实现一些主要的方法,我实现了一下方法。
- .rangCheck(index)-----检查数组下标是否越界
- .ensureCapasity()------保证数组的有效容量
- .空参构造方法和提供初始化容量的构造方法
- .增方法(add(int index,Oject obj))
- .删方法(remove())
- .赋值方法(set(int index,Object obj)
- .查询方法(get(int index)
- .获取集合长度方法size()
展示代码之前先说明一下
的用法: 复制指定源数组 src 到目标数组 dest。复制从 src 的 srcPos 索引开始,复制的个数是 length,复制到 dest 的索引从 destPos 开始。
- System.arraycopy(src, srcPos, dest, destPos, length);
- package cn.baidu.list;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- /**
- * 自己实现一个Arraylist
- * @author kyy
- *在ArrayList中有个成员变量modCount,继承于AbstractList。
- 这个成员变量记录着集合的修改次数,也就每次add或者remove它的值都会加1。这到底有什么用呢?
- */
- public class MyArraylist {
- private Object[] elementData = null;
- private int size;
- //提供构造方法,默认长度为10
- public MyArraylist() {
- this(10);
- }
- //提供初始化长度的构造方法
- public MyArraylist(int initCpacity) {
- //如果集合长度小于初始化长度
- if (initCpacity < 0) {
- try {
- throw new Exception();
- } catch(Exception e) {
- e.printStackTrace();
- }
- }
- elementData = new Object[initCpacity];
- }
- public int size() {
- return size;
- }
- public boolean isEmpty() {
- return size == 0;
- }
- //判断数组下标是否越界
- public void rangeCheck(int index) {
- if (index < 0 || index >= size) {
- try {
- throw new Exception();
- } catch(Exception e) {
- e.printStackTrace();
- }
- }
- }
- public void ensureCapacity() {
- if (size >= elementData.length) {
- Object[] temp = new Object[elementData.length * 2];
- System.arraycopy(elementData, 0, temp, 0, size);
- elementData = temp;
- }
- }
- //增加元素
- public void add(Object obj) {
- ensureCapacity();
- elementData[size++] = obj;
- }
- public void add(int index, Object obj) {
- rangeCheck(index);
- ensureCapacity();
- System.arraycopy(elementData, index, elementData, index + 1, size - index);
- elementData[index] = obj;
- size++;
- }
- //根据索引查询元素
- public Object get(int index) {
- rangeCheck(index);
- return elementData[index];
- }
- //给指定索引赋值
- public Object set(int index, Object obj) {
- rangeCheck(index);
- Object oldObj = elementData[index];
- elementData[index] = obj;
- return oldObj;
- }
- //删除指定索引元素
- public void remove(int index) {
- rangeCheck(index);
- ensureCapacity();
- System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
- size--;
- }
- }
注意:集合的初始容量是 10 不是说集合一开始就有 10 的长度,因为 size() 方法,指的是" 逻辑 " 长度。
所谓 "逻辑" 长度,是指内存已存在的 "实际元素的长度" 而 "空元素不被计算"
即:当你利用 add() 方法,向 ArrayList 内添加一个" 元素 " 时,逻辑长度就增加 1 位。 而剩下的 9 个空元素不被计算。
整体写下来不是很简单,因为牵扯到一些数组元素移动的计算,写的时候一定要考虑仔细,不然容易出错!
来源: http://www.jianshu.com/p/b22c89ba3d7d