【数据结构】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();}
}

结果： 

 

 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();}

结果： 

 

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}

结果： 

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}

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();}

结果：