JAVASE-＞数据结构|顺序表底层逻辑

✅作者简介：大家好，我是橘橙黄又青，一个想要与大家共同进步的男人😉😉

🍎个人主页：再无B～U～G-CSDN博客

目标：

1. 什么是List 2. List常见接口介绍 3. List的使用本章主要学习顺序表底层逻辑，大致是一样的，不差多少。

 1. 什么是List

在集合框架中，List是一个接口，继承自Collection。

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示： 

Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下：

List 的官方文档  

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。 【面试题】Collection中有那些方法？

2. 常见接口介绍

 List中提供了好的方法，具体如下：

虽然方法比较多，但是常用方法如下：

3.简单实现List顺序表的底层逻辑

目的：为了更加清楚的了解顺序表的使用

相应的级别关系：

把所有的顺序表方法都定义在IList接口：

这里不带多讲，结构上跟c语言差不多。

我们说一下异常这一块：

梳理一下异常的应用，比如说：

实现代码：

相应的解释代码里面都有：

 src/arrayList/IList接口

package arrayList;

public interface IList {
    // 新增元素,默认在数组最后新增
    void add(int data);

    // 在 pos 位置新增元素
    void add(int pos, int data);

    // 判定是否包含某个元素
    boolean contains(int toFind);

    // 查找某个元素对应的位置
    int indexOf(int toFind);

    // 获取 pos 位置的元素
    int get(int pos);

    // 给 pos 位置的元素设为 value -> 更新
    void set(int pos, int value);

    //删除第一次出现的关键字key
    void remove(int toRemove);

    // 获取顺序表长度
    int size();

    // 清空顺序表
    void clear();

    // 打印顺序表，
    // 注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    void display();
}

src/arrayList/MyArrayList类

package arrayList;

import java.util.Arrays;

public class MyArrayList implements IList {

    public int[] elem;
    public int usedSize;

    //调用构造方法，初始化顺序表长度
    public MyArrayList() {
        this.elem = new int[2];
    }
    //判断顺序表满不满
    public boolean isFull() {
        return elem.length == usedSize;
    }

    //添加一个元素
    @Override
    public void add(int data) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        this.elem[usedSize] = data;
        this.usedSize++;
    }


    //该方法来 判断 添加元素时 pos是否合法
    private void checkPosOfAdd(int pos) throws PosNotLegalException {
        if (pos < 0 || pos > usedSize) {
            throw new PosNotLegalException("pos位置不合法!");
        }
    }

    // 在 pos 下标位置新增元素
    @Override
    public void add(int pos, int data) {
        //判断是不是正确引用
        try {
            checkPosOfAdd(pos);
        } catch (PosNotLegalException e) {
            e.printStackTrace();
        }
        if (isFull()) {
            //扩容
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        //移动元素
        for (int i = usedSize - 1; i >= pos; i--) {
            elem[i + 1] = elem[i];
        }
        //插入元素
        this.elem[pos] = data;
        this.usedSize++;
    }

    //判断顺序表是否有改元素
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    //查找某个元素对应的下标位置
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    //判断pos位置是否合法
    private void checkPosOfGetAndSet(int pos) throws PosNotLegalException{
        if(pos < 0 || pos >= usedSize) {
            throw new PosNotLegalException("get/set获取元素的时候" +
                    "pos位置不合法！");
        }
    }
    // 获取 pos 位置的元素
    @Override
    public int get(int pos) {
        //判断pos位置是否合法
        try {
            checkPosOfGetAndSet(pos);
        }catch (ClassCastException e){
            e.printStackTrace();
        }
        return this.elem[pos];
    }

    // 给 pos 位置的元素设为 value -> 更新
    @Override
    public void set(int pos, int value) {
        //判断pos位置是否合法
        try {
            checkPosOfGetAndSet(pos);
        }catch (ClassCastException e){
            e.printStackTrace();
        }
        this.elem[pos] = value;
    }

    //删除第一次出现的关键字key
    @Override
    public void remove(int toRemove) {
        //1、要查找是否存在要删除的关键字 toRemove
        int pos = indexOf(toRemove);
        if(pos == -1) {
            System.out.println("没有要删除的数字！");
            return;
        }
        for (int i = pos; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

    //返回数据长度
    @Override
    public int size() {
        return this.usedSize;
    }

    //释放顺序表
    @Override
    public void clear() {
        this.elem = null;
        this.usedSize = 0;
    }
    //打印顺序表
    @Override
    public void display() {
        System.out.print("[ ");
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");

        }
        System.out.println("]");
    }
}

src/arrayList/PosNotLegalException类

package arrayList;

public class PosNotLegalException extends RuntimeException{
    //不带参数的构造方法
    public PosNotLegalException() {

    }
    //带参数的构造方法
    public PosNotLegalException(String msg) {
        super(msg);
    }

}

src/arrayList/Test测试类

package arrayList;

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

//        list.add(1,24);
//        boolean temp = list.contains(24);
//        if(temp){
//            System.out.println("有");
//        }else{
//            System.out.println("没有");
//        }
        // 打印链表
        list.display();
//        int is =list.indexOf(2);
//        if (is >= 0) {
//            System.out.println("有,在下标:" + is);
//        } else {
//            System.out.println("没有");
//        }

        // 获取 pos 位置的元素
//        int a = list.get(3);
//        System.out.println(a);
//        list.set(2, 6);
//        System.out.println(a);
        list.remove(3);
        // 打印链表
        list.display();

    }
}

今天就到这里了，感谢观看。