数组容器ArrayList设计与Ja - 竹笋 - Powered by Discuz!NT Archiver

TUhjnbcbe - 2024/8/24 0:47:00

本篇文章主要跟大家介绍我们最常使用的一种容器ArrayList、Vector的原理，并且自己使用Java实现自己的数组容器MyArrayList，让自己写的容器能像ArrayList那样工作。在本篇文章当中首先介绍ArrayList的一些基本功能，然后去分析我们自己的容器MyArrayList应该如何进行设计，同时分析我们自己的具体实现方法，最后进行代码介绍！！！

ArrayList为我们提供了哪些功能？

我们来看一个简单的代码，随机生成个随机数，查看生成随机数当中是否存在50这个数。

publicclassMyArrayList{publicstaticvoidmain(String[]args){Randomrandom=newRandom();ArrayListIntegerlist=newArrayList();for(inti=0;i;i++){list.add(random.nextInt());}for(inti=0;i;i++){if(list.get(i)==50){System.out.println("包含数据50");}}list.set(5,0);//设置下标为5的数据为list.remove(5);//删除下标为5的数据list.remove(newInteger());//删除容器当中的第一个值为5的数据}}

上述代码包含了ArrayList最基本的一个功能，一个是add方法，向数组容器当中加入数据，另外一个方法是get从容器当中拿出数据，set方法改变容器里的数据，remove方法删除容器当中的数据。ArrayList的很多其他的方法都是围绕这四个最基本的方法展开的，因此我们在这里不仔细介绍其他的方法了，后面我们自己实现的时候遇到问题的时候自然会需要设计相应的方法，然后我们进行解决即可。

现在我们就需要去设计一个数组容器实现“增删改查”这四个基本功能。

设计原理分析

首先明白一点我们需要使用什么工具去实现这样一个容器。我们手里有的工具就是Java提供给我们的最基本的功能——数组（这个好像是废话，我们的标题就是数组容器）。

当我们在Java当中使用数组去存储数据时，数据在Java当中的内存布局大致如下图所示。

我们在设计数组容器这样一个数据结构的时候主要会遇到两个问题：

我们申请数组的长度是多少。

当数组满了之后怎么办，也就是我们的扩容机制。

对于这两个问题，首先我们数组的初始大小可以有默认值，在我们自己实现的MyArrayList当中设置为10，我们在使用类时也可以传递一个参数指定初始大小。第二个问题当我们的数组满的时候我们需要对数组进行扩容，在我们实现的MyArrayList当中我们采取的方式是，新数组的长度是原数组的两倍（这个跟JDK的ArrayList方式不一样，ArrayList扩容为原来的1.5倍）。

代码实现

为了让我们的类实现的更加简单我们在代码当中就不做很多非必要的逻辑判断并且抛出异常，我们的代码只要能表现出我们的思想即可。

首先定义一个接口MyCollection，表示我们要实现哪些方法！

publicinterfaceMyCollectionE{/***往链表尾部加入一个数据*

paramo加入到链表当中的数据*

return*/booleanadd(Eo);/***表示在第index位置插入数据o*

paramindex*

paramo*

return*/booleanadd(intindex,Eo);/***从链表当中删除数据o*

paramo*

return*/booleanremove(Eo);/***从链表当中删除第index个数据*

paramindex*

return*/booleanremove(intindex);/***往链表尾部加入一个数据，功能和add一样*

paramo*

return*/booleanappend(Eo);/***返回链表当中数据的个数*

return*/intsize();/***表示链表是否为空*

return*/booleanisEmpty();/***表示链表当中是否包含数据o*

paramo*

return*/booleancontain(Eo);/***设置下标为index的数据为o*

paramindex*

paramo*

return*/booleanset(intindex,Eo);}折叠

我们的构造函数，初始化过程。

publicMyArrayList(intinitialCapacity){this();//增长数组的空间为initialCapacity，即申请一个数组//且数组的长度为initialCapacitygrow(initialCapacity);}publicMyArrayList(){this.size=0;//容器当中的数据个数在开始时为0this.elementData=EMPTY_INSTANCE;//将数组设置为空数组}

我们需要实现的最复杂的方法就是add了，这个方法是四个方法当中最复杂的，其余的方法都相对比较简单。

进入add方法之后，我们需要找到符合要求的最小数组长度，这个值通常是容器当中元素的个数size+1，也就是图中的minCapacity首先先比较这个值和现在数组的长度，如果长度不够的话则需要进行扩容，将数组的长度扩大到原来的两倍。

如果不需要扩容，则直接讲元素放入到数组当中即可。

Overridepublicbooleanadd(Eo){//这个函数的主要作用就是确保数组的长度至少为size+1ensureCapacity(size+1);//新增加了一个数据，容器的大小需要+1elementData[++size]=o;returntrue;}/***这个函数的主要作用就是确保数组的长度至少为capacity*

paramcapacity*/publicvoidensureCapacity(intcapacity){intcandidateCapacity=findCapacity(capacity);if(elementData.lengthcandidateCapacity)grow(candidateCapacity);}/***这个函数的主要目的就是找到最终数组长度需求的容量*

paramminCapacity*

return*/privateintfindCapacity(intminCapacity){/***如果if条件为true即elementData还是初始化时设置的空数组*那么返回默认大小和需要大小的最大值*否则直接返回minCapacity*/if(elementData==EMPTY_INSTANCE){returnMath.max(DEFAULT_CAPACITY,minCapacity);}returnminCapacity;}折叠

我们为什么需要将ensureCapacity的访问限制权限设置为public？因为我们想让用户尽量去使用这个函数，因为如果我们如果写出下面这样的代码我们会一直申请内存空间，然后也需要将前面的数组释放掉，会给垃圾回收器造成更大的压力。

ArrayListIntegerlist=newArrayList();for(inti=0;i0000;i++){list.add(i);}

下面我们对ArrayList的方法进行测试：

importjava.util.ArrayList;classPerson{Stringname;publicStringgetName(){returnname;}publicvoidsetName(Stringname){this.name=name;}

OverridepublicStringtoString(){return"Person{"+"name="+name+\+};}}publicclassArrayListTest{publicstaticvoidmain(String[]args){ArrayListPersono1=newArrayList();o1.ensureCapacity(00000);longstart=System.currentTimeMillis();for(inti=0;i00000;i++){o1.add(newPerson());}longend=System.currentTimeMillis();System.out.println("end-start:"+(end-start));ArrayListPersono2=newArrayList();start=System.currentTimeMillis();for(inti=0;i00000;i++){o2.add(newPerson());}end=System.currentTimeMillis();System.out.println("end-start:"+(end-start));}}//输出结果end-start:end-start:折叠

从上面的测试结果我们可以看出提前使用ensureCapacity方法之后，程序执行的时间更加短。

插入数据的add方法。

Overridepublicbooleanadd(Eo){//这个函数的主要作用就是确保数组的长度至少为size+1ensureCapacity(size+1);//新增加了一个数据，容器的大小需要+1elementData[size]=o;size++;returntrue;}

add在指定下标插入数据。

首先将插入下标后的数据往后移动一个位置

然后在将数据放在指定下标的位置。

/***在下标index位置插入数据o*首先先将index位置之后的数据往后移动一个位置*然后将index赋值为o*

paramindex*

paramo*

return*/

删除数据的方法remove。

首先先删除指定下标的数据。

然后将指定下标后的数据往前移动一个位置

在实际的操作过程中我们可以不删除，直接移动，这样也覆盖被插入位置的数据了。

/***移除下标为index的数据*

paramindex*

return*/

Overridepublicbooleanremove(intindex){//需要被移动的数据个数intnumMoved=size-index-1;if(numMoved0)System.arraycopy(elementData,index+1,elementData,index,numMoved);elementData[--size]=null;returntrue;}

移除容器当中具体的某个对象。

/***这个方法主要是用于溢出容器当中具体的某个数据*首先先通过for循环遍历容器当中的每个数据，*比较找到相同的数据对应的下标，然后通过下标移除方法*

paramo*

return*/

Overridepublicbooleanremove(Eo){if(o==null){for(intindex=0;indexsize;index++)if(elementData[index]==null){remove(index);returntrue;}}else{for(intindex=0;indexsize;index++)if(o.equals(elementData[index])){remove(index);returntrue;}}returnfalse;}

set方法，这个方法就很简单了。

Overridepublicbooleanset(intindex,Eo){elementData[index]=o;returntrue;}

重写toString方法。

OverridepublicStringtoString(){if(size=0)return"[]";StringBuilderbuilder=newStringBuilder();builder.append("[");for(intindex=0;indexsize;index++){builder.append(elementData[index].toString()+",");}builder.delete(builder.length()-2,builder.length());builder.append("]");returnbuilder.toString();}

测试代码

publicstaticvoidmain(String[]args){MyArrayListIntegerlist=newMyArrayList();for(inti=0;i15;i++){list.add(-i);}System.out.println(list.contain(5));System.out.println(list);list.remove(newInteger(-6));System.out.println(list);System.out.println(list.elementData.length);//容器会扩容两倍，而默认容器长度为10，因此这里是20list.add(5,);System.out.println(list);System.out.println(list.contain());}//代码输出false[0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14][0,-1,-2,-3,-4,-5,-7,-8,-9,-10,-11,-12,-13,-14]20[0,-1,-2,-3,-4,,-5,-7,-8,-9,-10,-11,-12,-13,-14]true

完整代码

importjava.util.ArrayList;importjava.util.Arrays;publicclassMyArrayListEimplementsMyCollectionE{/***容器当中存储数据的个数*/privateintsize;/***容器中数组的默认长度*/privatestaticfinalintDEFAULT_CAPACITY=10;/***存放具体数据的数组，也就是我们容器当中真正存储数据的地方*/Object[]elementData;/***当容器当中没有数据将elementData设置为这个值，这个值是所有实例一起共享的*/privatestaticfinalObject[]EMPTY_INSTANCE={};publicMyArrayList(intinitialCapacity){this();//增长数组的空间为initialCapacity，即申请一个数组//且数组的长度为initialCapacitygrow(initialCapacity);}publicMyArrayList(){this.size=0;//容器当中的数据个数在开始时为0this.elementData=EMPTY_INSTANCE;//将数组设置为空数组}/***这个函数的主要作用就是确保数组的长度至少为capacity*

paramminCapacity*

paramminCapacity数组的最短长度*/privatevoidgrow(intminCapacity){intoldCapacity=elementData.length;//新的数组长度为原来数组长度的两倍intnewCapacity=oldCapacity1;//如果数组新数组的长度newCapacity小于所需要的长度minCapacity//新申请的长度应该为minCapacityif(newCapacityminCapacity){newCapacity=minCapacity;}//申请一个长度为newCapacity的数组，在将原来数组//elementData的数据拷贝到新数组当中elementData=Arrays.copyOf(elementData,newCapacity);}

Overridepublicbooleanadd(Eo){//这个函数的主要作用就是确保数组的长度至少为size+1ensureCapacity(size+1);//新增加了一个数据，容器的大小需要+1elementData[size]=o;size++;returntrue;}/***在下标index位置插入数据o*首先先将index位置之后的数据往后移动一个位置*然后将index赋值为o*

paramindex*

paramo*

return*/

Overridepublicbooleanadd(intindex,Eo){//确保容器当中的数组长度至少为size+1ensureCapacity(size+1);//将elementDataindex位置之后的数据往后移动一个位置//做一个原地拷贝System.arraycopy(elementData,index,elementData,index+1,size-index);//移动的数据个数为size-indexelementData[index]=o;size++;returntrue;}/***这个方法主要是用于溢出容器当中具体的某个数据*首先先通过for循环遍历容器当中的每个数据，*比较找到相同的数据对应的下标，然后通过下标移除方法*

paramo*

return*/

paramindex*

return*/

Overridepublicbooleanappend(Eo){returnadd(o);}

Overridepublicintsize(){returnsize;}

OverridepublicbooleanisEmpty(){returnsize==0;}

Overridepublicbooleancontain(Eo){if(o==null){for(intindex=0;indexsize;index++)if(elementData[index]==null){returntrue;}}else{for(intindex=0;indexsize;index++)if(o.equals(elementData[index])){returntrue;}}returnfalse;}

Overridepublicbooleanset(intindex,Eo){elementData[index]=o;returntrue;}publicstaticvoidmain(String[]args){MyArrayListIntegerlist=newMyArrayList();for(inti=0;i15;i++){list.add(-i);}System.out.println(list.contain(5));System.out.println(list);list.remove(newInteger(-6));System.out.println(list);System.out.println(list.elementData.length);list.add(5,);System.out.println(list);System.out.println(list.contain());}}

本篇文章我们介绍了ArrayList的内部原理，并且我们实现了一个自己的简单数组容器MyArrayList，但是我们还有一些内容没有涉及，比如clone、equals和迭代器，这些内容我们下期分析ArrayList源码再进行分析，我是LeHung，我们下期再见！！！

来源：