【数据结构】自写简易顺序表ArrayList

1024程序员节快乐！！！🎀🎁🎉

了解顺序表🍩

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

接口的实现🍩

ArrayList的底层就是一个动态的数组。

 // 打印顺序表
    public void display() { }
    // 新增元素,默认在数组最后新增
    public void add(int data) { }
    // 在 pos 位置新增元素
    public void add(int pos, int data) { }
    // 判定是否包含某个元素
    public boolean contains(int toFind) { return true; }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) { return -1; }
    // 获取 pos 位置的元素
    public int get(int pos) { return -1; }
    // 给 pos 位置的元素更新为value
    public void set(int pos, int value) { }
    //删除第一次出现的关键字key
    public void remove(int key) { }
    // 获取顺序表长度
    public int size() { return this.usedSize;; }
    // 清空顺序表
    public void clear() { }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

接下来我们将这些接口一一实现一下。

打印顺序表🍬

打印顺序表就是遍历这个数组，当然注意这里不能遍历elem.length。而是遍历当前的有效长度usedsize。

代码如下：

// 打印顺序表
    public void display() {
        for (int i = 0; i <this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }
 
1
2
3
4
5
6
7
8

新增元素,默认在数组最后新增🍫

要新增数据的话，首先应该先判断该数组是否放满了，放满的话需要先扩容才可以放入数据。之后再放入数据，放完数据也要注意usedsize要加加。

代码如下：

public void add(int data) {
        //1.判断是否满
        if(is_Full()){
            //2.扩容
           this.elem =  Arrays.copyOf(this.elem,this.elem.length*2);
        }
        //3.添加数据
        this.elem[this.usedSize]=data;
        //4.usedsize++
        this.usedSize++;
    }
    //判断数组是否满
  public boolean is_Full(){
        return size()>=this.elem.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

来实验一下add是否可行。

在 pos 位置新增元素🍮

pos的位置需要注意：
数组满的话需要扩容。而如果pos的位置是负数或者间隔的话，我们可以抛出一个pos位置不合法异常。

之后呢，我们就可以开始挪动数据，再插入数据，最后别忘了usedsize要加加。
挪动数据要注意我们要先把后面的数据挪开，再挪前一个数据，依次到pos位置。

代码如下：

 public void add(int pos, int data) throws PosWrongfulException{
        if (is_Full()){
            System.out.println("满了");
            this.elem =  Arrays.copyOf(this.elem,this.elem.length*2);
        }
        if (pos<0||pos>this.usedSize){
            throw new PosWrongfulException("Pos位置不合法");
        }
        //这里pos一定合法
        //1.挪动数据
        for (int i = this.usedSize-1; i < pos; i--) {
            this.elem[i+1]=this.elem[i];
        }
        //2.插入数据
        this.elem[pos]=data;
        //3、usedsize++
        usedSize++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

判定是否包含某个元素、查找某个元素对应的位置、获取 pos 位置的元素🍭

这三个方法比较简单，合并在一起讲。判定是否包含某个元素、查找某个元素对应的位置只需要遍历数组即可。但是如果这里是引用数据类型的话，就不能直接用等于比较而要用equals()方法。在获取 pos 位置的元素的方法中，我们要考虑pos位置是否合法及当前顺序表是否为空列表。

代码如下：

 // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i]==toFind){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i]==toFind){
                return i;
            }
        }
        return -1;
    }
    //判断是否为空
    public boolean is_Empty(){
        return size()==0; 
    }
    // 获取 pos 位置的元素
    public int get(int pos) throws EmptyException{
        if (is_Empty()){
            throw new EmptyException("当前顺序表为空");
        }
        if (pos<0||pos>this.usedSize){
            throw new PosWrongfulException("Pos位置不合法");
        }
        return this.elem[pos];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

给 pos 位置的元素更新为value🍬

还是要注意pos的位置是否合法，还要判断一次。

// 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        if (is_Empty()){
            throw new EmptyException("当前顺序表为空");
        }
        if (pos<0||pos>this.usedSize){
            throw new PosWrongfulException("Pos位置不合法");
        }
        this.elem[pos]=value;
    }

1
2
3
4
5
6
7
8
9
10
11
12

删除第一次出现的关键字key🍭

首先要想删除第一次出现的关键字的话，我们第一步要做的就是判断顺序表是否有东西，第二步要找到要删除的关键字，第三步才是挪动数据，第四步usedsize–。

代码如下：

public void remove(int key) {
        //1.判断顺序表是否为空
        if (is_Empty()){
            throw new EmptyException("当前顺序表为空");
        }
        //2.找到key
        int index = indexOf(key);
        if(index==-1){
            System.out.println("没有这个数字");
            return;
        }
        //3.挪动数据
        for (int i = index; i < this.usedSize; i++) {
            this.elem[i]=this.elem[i+1];
        }
        //4.usedsize--
        this.usedSize--;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

清空顺序表🍫

最后一个方法，清空顺序表，如果是引用数据类型的话，用完要置空，释放内存。但这里不是引用数据类型，所以我们可以直接把usedsize恢复成零即可。注意：如果之后要删除的数据是引用数据类型我们就要将它置空。

代码如下：

 // 清空顺序表
    public void clear() {
        this.usedSize = 0;

    }
1
2
3
4
5

写在最后🍎：码字不易，如果对你有帮助的话，给个三连或者关注一下吧🍰，感谢支持！📣