您的位置 首页 java

Java自定义一个数组类和动态数组类

智云科技发布于 2023年3月27日评论关闭阅读(100)

我之前在看《Java数据结构和算法》这本书，文中第二章也详细讲解了数组,所以自己也动手完成了自定义一个数组内和动态数组类，于是乎就有了这篇文章去温故而知新。

####数组 数组是应用最广泛的数组存储结构。 优点 :插入快，如果知道下标，可以非常地存取 缺点 :查找慢,删除慢，大小固定。

####动态数组 Java 也提供了顺序结构的动态数组类ArrayList,数组采用的是顺序结构来存储数据,可以有效利用空间，可用于存储大量的数据，数组不适合动态的改变它所存储的数据，如增加，删除一个单元等。由于数组采用顺序结构存储数据，数组获得第n单元中的数据的速度要比链表获得第n单元中的数据快。

####写一个数组类 这个数组类肯定有insert(),find(),delete(),display()这些基础方法。 insert() ：插入一个元素，然后数组长度+1，返回true。 

 public void insert(long value){
a[count]=value;
count++;
}
复制代码

find() :根据元素的值，遍历整个数组的元素，找到返回true,没有找到返回false 

 public boolean find(long searchValue){
int j;

for(j=0;j<count;j++){

if(a[j]==searchValue){
break;
}
}

if(j==count){
return false;
}else{
return true;
}
}

delete() :根据元素的值，遍历整个数组的元素，没有找到对应的元素值，返回flase， 找到了该元素存储在数组的位置，让该位置后面的所有元素向前移动一个位置，返回true。 

 public boolean delete(long deleteValue){

int j;
for(j=0;j<count;j++){

if(a[j]==deleteValue){

break;
}

}

if(j==count){

return false;
}else{

for(int k=j;k<count;k++){

a[k]=a[k+1];
}

count--;
return true;
}
}

display() :遍历整个数组的元素，打印数组。 

 public void display(){
int j;
for(j=0;j<count;j++){
System.out.print(a[j]+" ");
}
System.out.print("\n");

}

####写一个简单的动态数组类 其实这还是比较难的，但是看了一下ArrayList的源码后，写一个带有基本功能的类还是没有问题的。基本方法:add(),remove(),contain(),toString(),toArray(),removeRange(),get()等。

首先是 构造器 ，有2个构造器，分别一个是有参和无参的。有参的构造器需要传入的参数是所需初始化数组的容量大小，如果这个容量大小>0,那么创建一个数组，数组容量大小为传入的参数。如果这个容量大小=0,那么把EMPTY_ELEMENTDATA这个空数组对象赋给elementData这个数组变量。如果这个容器大小<0,那么抛出参数异常。对于无参构造器而言，直接把elementData数组变量引用这个DEFAULT_CAPACITY_ELEMENTDATA数组对象。 

 public CmazList1(int inititalCapcacity){

if(inititalCapcacity>0){

this.elementData=new Object[inititalCapcacity];

}else if(inititalCapcacity==0){
this.elementData=EMPTY_ELEMENTDATA;
}else{

throw new IllegalArgumentException("参数错误");
}
}

public CmazList1(){

this.elementData=DEFAULT_CAPACITY_ELEMENTDATA;
}

**contain()：**调用indexOf()方法，如果indexOf返回的int值大于0就说明此对象在数组中找到对应存储的位置，那么返回true,否则返回false。 

 public boolean contain(Object object){

return indexOf(object)>=0;

**indexOf():**通过遍历整个数组元素，判断该数组的某个单元是否包含这个对象，如果找到了这个对象，返回其存储在数组的下标，否则返回-1。 

 public int indexOf(Object object){

if(object==null){

for(int i=0;i<size;i++){

if(elementData[i]==null){

return i;
}
}
}else{

for(int i=0;i<size;i++){

if(elementData[i].equals(object)){

return i;

}
}
}

return -1;
}

add() :先调用 ensureCapacityInternal()方法，进行相关扩容等处理操作。然后添加元素，size加1。size用于记录在数组中元素的个数。 

 public  boolean  add(Object object){

ensureCapacityInternal(size+1);

elementData[size++]=object;

return true;
}

ensureCapacityInternal() :首先看整个英文的意思是确保内部容量。首先要判断这个数组是哪一个构造器初始化的。如果这个数组是无参构造器初始化的，那么这个数组肯定没有设置 初始化数组的容量大小 ，是一个空数组。然后把minCapacity的值在传入的minCapacity的值和默认容器大小的值中取出最大的一个值，即为minCapacity的值。然后调用ensureExplicitCapacity()。 

 private void ensureCapacityInternal(int minCapacity){


if(this.elementData==DEFAULT_CAPACITY_ELEMENTDATA){

minCapacity=Math.max(minCapacity, DEFAULT_CAPACITY);
}

ensureExplicitCapacity(minCapacity);
}

ensureExplicitCapacity() ：这个方法进行的操作，去判断是否要进行扩容。如果 minCapacity 大于数组的长度，说明这个数组需要进行扩容了，因为数组的空间容不下即将添加的元素。接下来调用grow()去进行扩容。 

 private void ensureExplicitCapacity(int minCapacity){

modCount++;

if(minCapacity-elementData.length>0){

grow(minCapacity);
}
}

**grow(): 进行扩容的操作,扩容后的大小是原来大小的1.5倍。>>1是右移1位，移动后的值是移动前的值的0.5倍。如果扩容后的大小比 minCapacity**小，那么就把minCapacity的值赋给newCapacity。如果newCapacity的值比我们之前定义的MAX_ARRAY_SIZE还要大的话，那么就调用hugeCapacity()方法。MAX_ARRAY_SIZE我们定义的大小是Integer.MAX_VALUE-8，也就是Integer型数值的最大值-8。补充:**原码是直接将一个数值换算成二进制数，但计算机以补码的形式保存所有的整数。**一般情况下，不会出现newCapacity>MAX_ARRAY_SIZE的情况。 

 private void grow(int minCapacity){

int oldCapacity=elementData.length;

int newCapacity=oldCapacity+(oldCapacity>>1);

if(minCapacity-newCapacity>0){

newCapacity=minCapacity;
}

if(newCapacity-MAX_ARRAY_SIZE>0){

newCapacity=hugeCapacity(minCapacity);
}

this.elementData=Arrays.copyOf(elementData,newCapacity);
}

**remove():**遍历整个数组元素，如果发现该数组包含这个对象，那么调用fastRemove()删除存储此对象的单元。 

 public boolean  remove(Object object){

if(object==null){

for(int i=0;i<size;i++){

if(elementData[i]==null){

fastRemove(i);
return true;
}
}
}else{

for(int i=0;i<size;i++){

if(elementData[i].equals(object)){
fastRemove(i);
return true;
}
}
}

return false;

}

**remove():**首先调用get()方法，通过下标得到此单元存储的元素值。这个方法返回就是这个元素值。计算出删除此元素需要挪动的元素个数。如果挪动的元素个数>0,那么调用System.arraycopy()方法，得到一个移动后的数组。elementData[–size]=null，移动后的数组剩余一个存储没有任何元素的单元，那么size–，把没有存储任何元素的单元置为null，通知GC清除无用的内存。 讲解 :System.arraycopy(src, srcPos, dest, destPos, length) src:源数组 srcPos：源数组要复制元素的起始位置 dest：目的数组 destPos：目的数组把复制的元素放置的起始位置 length:复制元素的长度 

 public E remove(int index){
rangeCheck(index);
modCount++;
E oldValue=get(index);
int movedNum=size-1-index;

if(movedNum>0){

System.arraycopy(elementData,index+1, elementData, index, movedNum);
}

elementData[--size]=null;

return oldValue;
}

removeRange() :需要注意的是toIndex指的是要删除的最后一个元素的下一个元素的下标。思路和remove()是一样的，只是remove()是删除一个元素，removeRange()删除的是多个元素。 

 public void removeRange(int fromIndex,int toIndex){

modCount++;

//int movedNum=size-1-(toIndex-1);
int movedNum=size-toIndex;

if(movedNum>0){

System.arraycopy(elementData, toIndex, elementData, fromIndex, movedNum);
}

int newSize=size+fromIndex-toIndex;

for(int i=newSize;i<size;i++){

elementData[newSize]=null;
}

size=newSize;

}

源码附上 

 public class CmazList1<E> {

private static final Object[] DEFAULT_CAPACITY_ELEMENTDATA={};

private static final Object[] EMPTY_ELEMENTDATA={};

private static final int MAX_ARRAY_SIZE=Integer.MAX_VALUE-8;

private static int DEFAULT_CAPACITY=10;

private Object[] elementData;

private int modCount=0;

private int size;

public CmazList1(int inititalCapcacity){

if(inititalCapcacity>0){

this.elementData=new Object[inititalCapcacity];

}else if(inititalCapcacity==0){
this.elementData=EMPTY_ELEMENTDATA;
}else{

throw new IllegalArgumentException("参数错误");
}
}

public CmazList1(){
this.elementData=DEFAULT_CAPACITY_ELEMENTDATA;
}

public boolean contain(Object object){

return indexOf(object)>=0;
}

public int indexOf(Object object){

if(object==null){

for(int i=0;i<size;i++){

if(elementData[i]==null){

return i;
}
}
}else{

for(int i=0;i<size;i++){

if(elementData[i].equals(object)){

return i;

}
}
}

return -1;
}

public  boolean  add(Object object){

ensureCapacityInternal(size+1);

elementData[size++]=object;

return true;
}

private void ensureCapacityInternal(int minCapacity){


if(this.elementData==DEFAULT_CAPACITY_ELEMENTDATA){

minCapacity=Math.max(minCapacity, DEFAULT_CAPACITY);
}

ensureExplicitCapacity(minCapacity);
}


private void ensureExplicitCapacity(int minCapacity){

modCount++;

if(minCapacity-elementData.length>0){

grow(minCapacity);
}
}

private void grow(int minCapacity){

int oldCapacity=elementData.length;

int newCapacity=oldCapacity+(oldCapacity>>1);

if(minCapacity-newCapacity>0){

newCapacity=minCapacity;
}

if(newCapacity-MAX_ARRAY_SIZE>0){

newCapacity=hugeCapacity(minCapacity);
}

this.elementData=Arrays.copyOf(elementData,newCapacity);
}

private int hugeCapacity(int minCapacity){

if(minCapacity<0){

throw new OutOfMemoryError();
}
return minCapacity>MAX_ARRAY_SIZE?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
}

public boolean  remove(Object object){

if(object==null){

for(int i=0;i<size;i++){

if(elementData[i]==null){

fastRemove(i);
return true;
}
}
}else{

for(int i=0;i<size;i++){

if(elementData[i].equals(object)){
fastRemove(i);
return true;
}
}
}

return false;

}


private  void fastRemove(int index){
modCount++;
int movedNum=size-1-index;
if(movedNum>0){

System.arraycopy(elementData, index+1, elementData, index, movedNum);
}

elementData[--size]=null;

}

public E remove(int index){
rangeCheck(index);
modCount++;
E oldValue=get(index);
int movedNum=size-1-index;

if(movedNum>0){

System.arraycopy(elementData,index+1, elementData, index, movedNum);
}

elementData[--size]=null;

return oldValue;
}

public E get(int index){
rangeCheck(index);
return (E) elementData[index];
}

@Override
public String toString() {
// TODO Auto-generated method stub

StringBuilder sb=new StringBuilder();
for(int i=0;i<size;i++){
sb.append(elementData[i]+" ");
}
return sb.toString();
}

public Object[] toArray(){

return Arrays.copyOf(this.elementData, size);
}

/**
 * toIndex是指要删除的最后一个元素的下一个元素的下标
 * 比如我要删除下标为5的元素，那么toIndex=6
 * @param fromIndex
 * @param toIndex
 */public void removeRange(int fromIndex,int toIndex){

modCount++;

//int movedNum=size-1-(toIndex-1);
int movedNum=size-toIndex;

if(movedNum>0){

System.arraycopy(elementData, toIndex, elementData, fromIndex, movedNum);
}
//
int newSize=size+fromIndex-toIndex;

for(int i=newSize;i<size;i++){

elementData[newSize]=null;
}

size=newSize;

}

private  void rangeCheck(int index){

if(index>=size||index<0){

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}


private String outOfBoundsMsg(int index){
return "index:"+index+",size="+size;
}
}

####尾言 数据结构和算法的复利性远，对于程序员来说， 打好牢固的基础，一定是没有错的。

标签:
打赏 点赞(0)

文章来源：智云一二三科技

文章标题：Java自定义一个数组类和动态数组类

文章地址：https://www.zhihuclub.com/188694.shtml

关于作者: 智云科技

相关文章

热门文章

1分享新浪图床上传接口源码

点赞(939)阅读(61,087)

2PHP简单实现路由Route功能

点赞(1.15K)阅读(35,962)

3Tideways、xhprof 和 xhgui 打造 PHP 非侵入式监控平台

点赞(365)阅读(4,289)

4centos系统如何查看是否安装了mysql

点赞(538)阅读(3,787)

5curl 工具简述

点赞(513)阅读(2,979)
网站地图