欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 国际 > 【数据结构】ArrayList的模拟实现--Java

【数据结构】ArrayList的模拟实现--Java

2024/11/1 0:22:41 来源:https://blog.csdn.net/2301_80543957/article/details/143375341  浏览:    关键词:【数据结构】ArrayList的模拟实现--Java

目录

 一、🍩简单了解ArrayList

二、🍩ArrayList的简单模拟实现

1.🍔IList接口

1.🍕IList接口

2. 🍕 MyArrayList 重写接口方法

2.🍔ArrayList方法

1.🥪增

1.add(添加元素):添加在末尾

 2.add(插入元素):插入元素在任意位置

2.🥪 查

1.contains(是否包含该元素)

2.get(获取下标元素)

3.indexOf (获取元素下标)

3.🥪删

 1.remove(删除元素)

2.clear(清空所有元素)

4.🥪改

1.set(更改元素):将元素进行替换


 一、🍩简单了解ArrayList

什么是ArrayList?

在集合框架中,ArrayList是一个普通的类,其内部基于数组实现,数据存储有序,实现的List接口。List是一个接口不能进行实例化,而ArrayList实现了这个接口。

  • List就是一个线性表,即具有n个相同类型元素的有限序列,在该序列上可以执行增删查改的功能以及变量等操作。 

二、🍩ArrayList的简单模拟实现

1.🍔IList接口

      首先,我们知道ArrayList实现了List的接口,所以我们要知道List接口中有哪些方法,并且ArrayLiat要重写List接口中的方法这里我们对其是简单模拟ArrayList,我们实现其一些常见的功能就好。

ArrayList常见方法:

增:
void add(int data)在数组最后添加元素
void add(int pos,int data)在数组某下标插入元素
删:
void remove(int toRemove)删除第一次出现的元素
void clear();清空所有元素
查:

boolean contains(int toFind)

查看是否包含该元素
int get(int pos)获取该下标元素
int indexOf(int toFind )获取该元素下标
改:
void set(int pos,int value)将下标元素进行更改

 这些常见方法就是增删查改的功能。

1.🍕IList接口

public interface IList {public void add(int data);public void add(int pos,int data);public void remove(int toRemove);public void clear();public boolean contains(int toFind);public int get(int pos);public int indexOf(int toFind);public void set(int pos,int value);
}

2. 🍕 MyArrayList 重写接口方法

public class MyArrayList implements IList{@Overridepublic void add(int data) {}@Overridepublic void add(int pos, int data) {}@Overridepublic void remove(int toRemove) {}@Overridepublic void clear() {}@Overridepublic boolean contains(int toFind) {return false;}@Overridepublic int get(int pos) {return 0;}@Overridepublic int indexOf(int toFind) {return 0;}@Overridepublic void set(int pos, int value) {}
}

我们知道,ArrayList内部是基于数组内部实现, 并且他是一个有限序列,所以我们需要在MyArrayList中加几个定义的变量

public class MyArrayList implements IList{public int[] array;//默认容量大小//这个为常量,所以可以使用static finalpublic static final int DEFULATE_CAPACITY=10;//以占用的数组空间大小public int usedsize;//构造方法public MyArrayList() {this.array = new int[DEFULATE_CAPACITY];}
}

2.🍔ArrayList方法

1.🥪增

1.add(添加元素):添加在末尾

注意事项:

  • 是否空间已满,如果满了进行扩容;
  • 添加了代码之后,使用空间增加。
public void add(int data) {//如果满了,进行扩容if(isFull()){grows();}//数组下标由0开始,在增加一个元素的时候,其下标在第usedsize的位置上array[usedsize]=data;usedsize++;}

判断空间是否已满(isFull):使用空间==空间大小

    public boolean isFull(){return this.usedsize==array.length;}

 扩容(grows):使用Arrays.copyOf进行扩容

   public void grows(){this.array= Arrays.copyOf(this.array,2*this.array.length);}

  为了更好的查看结果,我们需要加上一个打印方法

展示:注意这里的i是小于数组以使用的长度usedsize而不是数组的全部长度

 public void display(){for (int i = 0; i < usedsize; i++) {System.out.print(array[i]+" ");}

测试:

public class Test {public static void main(String[] args) {MyArrayList myArrayList=new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.display();}
}

结果: 

 46705e0757ed4c279d1061b15072cff4.png

 2.add(插入元素):插入元素在任意位置

注意事项:

1.插入元素的下标不能小于0以及不能大于usedsize,否则·报错;

2.插入空间是否已满,满了扩容;

3.已使用数组长度增加;

我们需要检查添加的下标位置是否合法,由于可能会出现位置不合法的情况,如果出现这种情况,要报错,所以我们需要自定义一个位置不合法异常

PosIlleagal类:继承运行时异常

public class PosIllegal extends RuntimeException{public PosIllegal() {super();}public PosIllegal(String message) {super(message);}
}

出现异常条件:插入元素的下标不能小于0以及不能大于usedsize

checkPos:检查插入元素的下标是否合法

  //throws:其提醒作用,可能存在的异常public void checkPos(int pos) throws PosIllegal{//如果下标位置不合法,报错if(pos < 0 || pos >= usedsize){throw new PosIllegal("位置不合法!!!");}}

既然可能会出现异常,我们需要对其进行try-catch捕获处理

    public void add(int pos, int data) {try{checkPos(pos);if(isFull()){grows();}}catch (PosIllegal e){System.out.println("下标插入位置不合法");e.printStackTrace();}catch(Exception e){e.printStackTrace();}}

 add(插入元素):我们可以从后往前,将前面的元素向后移动,直到移动到所需插入元素的下标为止,随即插入元素

   public void add(int pos, int data) {try{checkPos(pos);if(isFull()){grows();}for (int i = usedsize-1; i >=pos ; i--) {array[i+1]=array[i];}array[pos]=data;usedsize++;}catch (PosIllegal e){System.out.println("下标插入位置不合法");e.printStackTrace();}catch(Exception e){e.printStackTrace();}}

测试:

   public static void main(String[] args) {MyArrayList myArrayList=new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(3,11);myArrayList.add(6,5);myArrayList.display();}

结果: 

 fc59e73a8d8a4178b69fd65218e840f5.png

2.🥪 查

1.contains(是否包含该元素)

  contains:遍历所使用的数组大小,查找是否有该元素

    @Overridepublic boolean contains(int toFind) {for (int i = 0; i < usedsize; i++) {if(array[i]==toFind){return true;}}return false;}

2.get(获取下标元素)

 注意事项:

1.该数组是否为空,如果为空,报错

1.该下标是否合法,如果下标小于0或者下标大于等于usedsize,那么位置不合法;

  注意:这里的是大于等于,插入元素的不合法是大于

既然我们在使用get方法的时候会出现顺序表为空的情况下,那么我们需要一个顺序表为空时候的异常

EmptyException(顺序表为空异常):

public class EmptyException extends RuntimeException{public EmptyException() {}public EmptyException(String message) {super(message);}
}

checkEmpty(顺序表报错条件):

   public void checkEmpty() throws EmptyException{if(usedsize==0){throw new EmptyException("顺序表为空");}}

由于这样的位置不合法条件与插入元素的位置不合法条件不同,所以我们需要再写一个检查位置是否合法的方法

checkPos2(检查pos位置是否合法):

   public void checkPos2(int pos) throws PosIllegal{if(pos < 0 || pos >= usedsize){throw new PosIllegal("位置不合法!!!");}}

get:如果没有出现异常,直接返回下标元素

public int get(int pos) {try {checkEmpty();checkPos2(pos);return array[pos];}catch (PosIllegal e){System.out.println("Pos位置不合法");e.printStackTrace();}catch (EmptyException e){System.out.println("顺序表为空");e.printStackTrace();}catch (Exception e){e.printStackTrace();}return -1;}

3.indexOf (获取元素下标)

注意事项:

1.是否包含该元素,如果没有返回-1;

indexOf:遍历数组元素,查找是否有该元素,有则返回元素下标,没有返回-1 

 public int indexOf(int toFind) {if(contains(toFind)){for (int i = 0; i < usedsize; i++) {if(array[i]==toFind){return i;}}}return -1;}

 测试:

 public static void main(String[] args) {MyArrayList myArrayList=new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);//是否包含boolean b=myArrayList.contains(5);System.out.println(b);//false//获取下标元素int a=myArrayList.get(2);System.out.println(a);//3//获取元素下标int c=myArrayList.indexOf(0);System.out.println(c);//-1int d=myArrayList.indexOf(3);System.out.println(d);//2}

结果: 

f240ab6935054223bf12264339af1029.png

3.🥪删

 1.remove(删除元素)

注意事项:

1.顺序表是否为空;

2.是否有该元素;

3.如果删除完该元素,数组使用长度减小。

remove:获取下标,如果下标不存在,返回;如果下标存在,将下标从前往后遍历,将后面的元素向前移动 

public void remove(int toRemove) {try{checkEmpty();//获取下标int pos=indexOf(toRemove);if(pos==-1){System.out.println("没有该元素,移除失败");return;}//从前往后,将后面的元素向前移动//i是小于usedsize-1就好,因为当i=usedsize-2//将usedsize-1中的元素移到了usedsize-2中for (int i = pos; i < usedsize-1; i++) {array[i]=array[i+1];}usedsize--;}catch (EmptyException e){System.out.println("顺序表为空");e.printStackTrace();}catch(Exception e){e.printStackTrace();}}

2.clear(清空所有元素)

clear:直接将使用空间置0;

 public void clear() {this.usedsize=0;}

测试:

    public static void main(String[] args) {MyArrayList myArrayList=new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.display();System.out.println();//1 2 3//移除:myArrayList.remove(2);myArrayList.display();System.out.println();//1 3myArrayList.remove(5);//没有该元素,移除失败System.out.println();//清空:myArrayList.clear();myArrayList.display();myArrayList.add(1);myArrayList.display();//1}

c92016dd477e447bacf73d0d22e16471.png

4.🥪改

1.set(更改元素):将元素进行替换

注意事项:

1.顺序表是否为空;

2.进行更改的元素下标是否合法

set:直接将下标所对于的元素进行更改 

public void set(int pos, int value) {try{checkEmpty();checkPos2(pos);array[pos]=value;}catch (EmptyException e){System.out.println("顺序表为空");e.printStackTrace();}catch (PosIllegal e){System.out.println("下标位置不合法");e.printStackTrace();}catch(Exception e){e.printStackTrace();}}

测试:

public static void main(String[] args) {MyArrayList myArrayList=new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.display();//1 2 3System.out.println();myArrayList.set(2,11);//1 2 11myArrayList.display();System.out.println();myArrayList.set(5,11);//报错myArrayList.display();}

结果:

 1eed3f969c7941038993ccabb945c328.png

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com