当前位置：首页 > article >正文

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

article 2024/11/1 0:21:19

一、🍩简单了解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{
    @Override
    public void add(int data) {

    }
    @Override
    public void add(int pos, int data) {

    }
    @Override
    public void remove(int toRemove) {

    }
    @Override
    public void clear() {

    }
    @Override
    public boolean contains(int toFind) {
        return false;
    }
    @Override
    public int get(int pos) {
        return 0;
    }
    @Override
    public int indexOf(int toFind) {
        return 0;
    }
    @Override
    public void set(int pos, int value) {

    }
}

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

public class MyArrayList implements IList{
    public int[] array;
    //默认容量大小
    //这个为常量，所以可以使用static final
    public 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：遍历所使用的数组大小，查找是否有该元素

    @Override
    public 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);//-1
        int 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 3
        myArrayList.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 3
        System.out.println();
        myArrayList.set(2,11);//1 2 11
        myArrayList.display();
        System.out.println();
        myArrayList.set(5,11);//报错
        myArrayList.display();
    }

结果：