Java ArrayList源码分析（有助于理解数据结构）

arraylist源码分析

1.数组介绍

数组是数据结构中很基本的结构，很多编程语言都内置数组，类似于数据结构中的线性表

在java中当创建数组时会在内存中划分出一块连续的内存，然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。当需要读取数组中的数据时，需要提供数组中的索引，然后数组根据索引将内

存中的数据取出来，返回给读取程序。在java中并不是所有的数据都能存储到数组中，只有相同类型的数据才可以一起存储到数组中。

  

 

 

 因为数组在存储数据时是按顺序存储的，存储数据的内存也是连续的，所以他的特点就是：寻址读取数据比较容易，插入和删除比较困难。

 

带参构造方法

public arraylist(int initialcapacity) {
        if (initialcapacity > 0) {
　　　　　　　//创建指定长度的数组
            this.elementdata = new object[initialcapacity];
        } else if (initialcapacity == 0) {
　　　　　　　//空数组
            this.elementdata = empty_elementdata;
        } else {
            throw new illegalargumentexception("illegal capacity: "+
                                               initialcapacity);} //如果既不大于零，也不小于零，就会报错抛出异常
    }

 

空参构造方法

    public arraylist() {
        this.elementdata = defaultcapacity_empty_elementdata; //给一个成员变量赋值
    }
　　private static final object[] defaultcapacity empty elementdata={}; //空参构造方法创建的数组就是一个空的

 

下面这个用的不多，能看懂即可

public arraylist(collection<? extends e> c) {
        elementdata = c.toarray(); //把collection这个集合也变成了一个数组，传给了当前数组elementdata
　　　　　//大于0，就拷贝数组
        if ((size = elementdata.length) != 0) { //判断当前elementdata数组的长度，如果不等于0
            if (elementdata.getclass() != object[].class) //判断类型是不是object数组类型，如果不是这个类型
                elementdata = arrays.copyof(elementdata, size, object[].class);  //拷贝一个数组，然后长度，然后把object[].class数组传进去，然后生成一个elementdata数组
　　　　　//不是大于0，就拷贝一个空的
        } else {
            // replace with empty array.
            this.elementdata = empty_elementdata; //设置为空数组
        }
    }

 

 

 添加元素

public boolean add(e e) {
　　　　//检测是否需要扩容
       下¹ensurecapacityinternal(mincapacity：size + 1);  // size是当前存的数据个数
　　　　//数组赋值

        elementdata[size++] = e;
        return true;
    }

 

 扩容的入口方法，计算容量

private void 上¹ensurecapacityinternal(int mincapacity){    //mincapacity最小值，传的时候就是+1后的
下下³ensureexplicitcapacity(下²calculatecapacity(elementdata,mincapacity)); //计算容量，传入一个数组elementdata，再传一个最小容量mincapacity

 

计算最小容量

private static int 上²calculatecapacity(object[] elementdata, int mincapacity){
//如果elementdata是空的
if(elementdata==defaul tcapacity empty el ementdat)|
//返回一个默认或者mincapacity，最后是返回其中最大的
return math. max(default_capacit mincapacity); 
//不是空，就返回size+1的值 
return mincapacity;
}

 

 

private void 上上³ensureexplicitcapacity(int mincapacityp{
//只要发生修改就+1
modcount++; 
//是否满足扩容的条件   最小容量（当前数组存值得容量？） - object数组的长度
if(mincapacity-elementdata. length〉0）//elementdata.lenth=10 （默认容量为10）
下¹grow(mincapacity);

 

 数组扩容方法

private void 上¹grow(int mincapacity){
　　　//计算当前数组容量，也就是老的容量
　 　int oldcapacity=elementdata. length;
　　　//新的数组容量 = 老容量 + 老容量/2  （老容量的1.5倍）
 　　int newcapacity=oldcapacity+(oldcapacity >>1);  >>1 除二

　　　　 // oldcapacity=10
　　　　// oldcapacity >>1
　　　　// 0000 1010 >> 1
　　　　// 0000 0101 = 5

　　　　//判断新的数组容量-之前最小容量

 　　if(newcapacity-mincapacity<0)
　　　　　　newcapacity=mincapacity;
　　 if (newcapacity - max_array_size>0)  //max_array_size：值特别大，如果新的数组比它还大，就越界了，或者直接返回最大长度
　　　　　　newcapacity = hugecapacity(mincapacity);
　　　elementdata=arrays. copyof(elementdata, newcapacity);

 

 

    public void add(int index, e element) {
　　　　　//判断下标是否越界
        下1rangecheckforadd(index);
　　　　　//检测是否需要扩容
        ensurecapacityinternal(size + 1); 
　　　　　//把index之后的所有元素向后移动一位

        system.arraycopy(elementdata, index, elementdata, index + 1,
                         size - index);
　　　　　//将index位置覆盖上新值

        elementdata[index] = element;
        size++;
    }

private void 上1rangecheckforadd(int index){
if(index>size || index<0)
throw new indexoutofboundsexception(outofboundsmsg(index));

 

system.arraycopy(elementdata, index, elementdata, index + 1,size - index); 举例

int[] elementdata = new int[10];
 for(int i=0;i<5;i++){ //数组的下标 0,1,2,3,4
elementdata[i]=i+1;  //数组的值 1,2,3,4,5
system. out. println("=="+arrays. tostring(elementdata)); 
int size=5; 
int index=1; //插入数组下标位置
 system. arraycopy(elementdata, index, elementdata, destpos: index+1, length: size-index);   原数组，插入指定的位置，又指定的数组，指定的位置为当前位置+1，到5-1=4的位置 >>从插入位置往后算
system. out. println("--"+arrays. tostring(elementdata));

打印结果

 ==  [1，2，3，4，5，0，0，0，0，0]
 一  [1，2，2，3，4，5，0，0，0，0]  2：是要插入的数值

 

 向arraylist添加对象时，原对象数目加1如果大于原底层数组长度，则以适当长度新建一个原数组的拷贝，并修改原数组，指向这个新建数组。

原数组自动抛弃（java垃圾回收机制会自动回收）。size则在向数组添加对象，自增1。

 

 

删除方法

指定位置删除

public e remove(int index) {
　　　　 检测当前下标是否越界
        下1rangecheck(index);

        modcount++;
        e oldvalue = elementdata(index);
　　　　 将index+1及之后的元素向前移动一位，覆盖被删除的值
        int nummoved = size - index - 1;
        if (nummoved > 0)
            下下2system.arraycopy(elementdata, index+1, elementdata, index,
                             nummoved);
　　　　 将最后一个位置的元素清空

        elementdata[--size] = null; 

        return oldvalue;
    }

 

private void 上1rangecheck(int index){
if(index >=size)
throw new indexoutofboundsexception(outofboundsmsg(index));

 

 

上上² system.arraycopy(elementdata, index+1, elementdata, index, nummoved); 举例int[] elementdata = new int[10];

for(int i=0;i<10;i++){ //数组的下标 0,1,2,3,4,5,6,7,8,9
elementdata[i]=i+1;  //数组的值 1,2,3,4,5,6,7,8,9,10
}
int size = elementdata.lengh;  //数组里有几个数，长度就是几    elementdata.lengh = 10
int index = 2;
int nummoved = size - index - 1;
system. out. println("==" + arrays. tostring(elementdata)); 
system. arraycopy(elementdata, srcpos: index+1, elementdata, index, nummoved);   原数组，指定的位置为要删除的下标往后一个位置，又指定的数组，删除位置的下标，10-2-1=7  >>从指定删除下标位置往后数，全部向前移动一位

system. out. println("--" + arrays. tostring(elementdata));

打印结果
 ==  [1，2，3，4，5，6，7,8,9,10]   3：要删除的数字
 一  [1，2，4,5,6,7,8,9,10,10]  

 

 

 指定元素删除

public boolean remove(object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementdata[index] == null) {
                    下1fastremove(index);
                    return true;} //从0开始遍历，大小为数组长度，找到后直接删除
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementdata[index])) {
                    fastremove(index);
                    return true;
                }
        }
　　　　　如果没有匹配元素，返回false
        return false;
    }

快速删除， 没有检测index下标的原因：因为之前需要指定下标删除，现在是直接指定删除某个元素，如果元素不存在，for语句遍历也不会找到这个元素，所有，只要能满足两个if语句其中一个，那这个元素一定在我的合理范围内的，所以就不需要检测有没有下标

 

 

快速删除，没有检测index下标

private void 上1fastremove(int index) {
        modcount++;
        int nummoved = size - index - 1;
        if (nummoved > 0)
            system.arraycopy(elementdata, index+1, elementdata, index,
                             nummoved);
        elementdata[--size] = null; // clear to let gc do its work
    }

 arraylist<integer> list=new arraylist（）；

1ist.add（10）；
1ist.add（11）；
1ist.add（12）；
1ist.add（13）；
1ist.add（15）；
for（integer num：1ist）{
　　if（num==12）{
　　　　1ist.remove（num）；
　　}
}i
//报错
//exception in thread"main"java.util.concurrentmodificationexception 

final void checkforcomodification）{

　　if（modcount != expectedmodcount）  //modcount：6   expectedmodcount：5   >> 使用迭代器时，同步了一下 expectedmodcount = modcount,迭代的时候一直在判断，如果此时调用了 arraylist.remove，modcount变化了，expectedmodcount还是初始同步的值，也就throw new concurrentmodificationexception();

　　　　throw new concurrentmodificationexception（）；
}

 

 

  modcount++ :  该字段表示list结构上被修改的次数。在对集合进行新增或移除操作时会使modcount+1,这是一个记录集合变化次数的变量。

 作用是在使用迭代器iterator对集合进行遍历时，用modcount来判断集合内数据没有发生变化，否则会抛出异常。

 

解决办法：用迭代器删除

//解决删除异常问题
iterator<integer> it = list.iterator（）；
while(it.hasnext()){  　　　　//hasnext（）方法 ： 检验后面还有没有元素。 从前往后查找。
　　integer num=it.next（）； //next（）方法：获取下一个元素
　　if（num == 12）{ 
　　//使用迭代器的删除方法
　　it.remove（）；
　　}
}

public void remove（）{
　　if（lastret<0）
　　　　throw new i1legalstateexception（）；
　　checkforcomodification（）；

　　try{
　　arraylist.this.remove（lastret）；
　　cursor=lastret；
　　1astret=-1；
　　//修改expectedmodcound 和 modcount一样
　　expectedmodcount = modcount；
}catch（indexoutofboundsexception ex）{
　　throw new concurrentmodificationexception（）；
}