纪念第一次手写源码

前几天看百度面试题，有一道题是手写Arraylist,于是一直在心中就想怎么实现，看自己能不能写出，于是翻源码看，感觉有些方法能看懂，但是有些确实需要很高深的数据结构的功底才能写出来，自己心里有点后怕。
但是我不服气啊哈哈！
今天就在java交流群里试探大家怎么看这件事，可是好多竟然都说很简单，我不知道那些是装逼的还是真的大神，可是我性格就是不愿意服输，于是下决心今天一定要把它写出来！！！

写Arraylist之前要先明白一些要素：
1.ArrayList的底层是Object类的数组，默认长度是10,超过10后，长度变为原长度的2倍。（这个数字可以变）
2.ArrayList底层是个动态数组实现的，长度不够时，调用Arrays.copyOf方法，拷贝当前数组到一个新的长度更大的数组。如果是数组比较大，那么使用System.arraycopy会比较有优势，因为其使用的是内存复制，省去了大量的数组寻址访问等时间，所以我实现的方法全部用System.arraycopy。
3.因为是自己实现，所以只能实现一些主要的方法，我实现了一下方法。

1.rangCheck(index)-----检查数组下标是否越界
2.ensureCapasity()------保证数组的有效容量
3.空参构造方法和提供初始化容量的构造方法
4.增方法（add(int index,Oject obj)）
5.删方法（remove()）
6.赋值方法（set(int index,Object obj）
7.查询方法（get(int index）
8.获取集合长度方法size()

展示代码之前先说明一下 System.arraycopy(src, srcPos, dest, destPos, length);的用法：
复制指定源数组src到目标数组dest。复制从src的srcPos索引开始，复制的个数是length，复制到dest的索引从destPos开始。
整体代码如下：

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个空元素不被计算。

整体写下来不是很简单，因为牵扯到一些数组元素移动的计算，写的时候一定要考虑仔细，不然容易出错！

纪念第一次手写源码

推荐阅读更多精彩内容