【数据结构中链表常用的方法实现过程】

线性表

• 线性表包括:顺序表、链表、栈，队列等，本节我们先学习顺序表。

顺序表

利用新的数据类型——顺序表，操作数组

顺序表的本质就是对数组的增删改查。

    /**
     * 打印顺序表中的所有元素
     */
    @Override
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.println(elem[i]+" ");
        }
        System.out.println();
    }

往数组末尾添加元素

    /**
     * 添加元素：默认添加到数组的最后位置
     * @param data
     */
    @Override
    public void add(int data) {
        //1.如果满了，要进行扩容
        if(isFull()){
            //二倍扩容 -> 拷贝完之后让elem指向一个新的数组对象
            elem = Arrays.copyOf(elem , 2*elem.length);
        }
        //将元素放入数组中
        elem[usedSize] = data;
        usedSize++;
    }
    
    //判断数组是否满了
    @Override
    public boolean isFull() {
        return usedSize == elem.length;
    }

通过debug可以看到，当数组元素超出其所能承载的容量大小时，可以通过copyOf进行扩容，从而将第六个元素放进去。

在指定位置添加新元素

• 1.首先从后往前移动元素

• 2.将元素放进指定位置，并且更新元素个数。
  

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

        //1.先挪动元素，将最后面元素逐个往前挪
        //i >= pos 时元素才会往前移
        for (int i = usedSize - 1; i >= pos; i--) {

            elem[i+1] = elem[i];
        }//挪完将指定元素插入到位置中
         elem[pos] = data;
        usedSize++;

        }

    @Override
    public String toString() {
        // 数组的话是没有toString的，可以使用它的工具类去打印
        return Arrays.toString(elem);
//        刚刚写的是return elem.tostring
        // 当这个是list类型，不是普通的数组类型的时候，是可以直接调用toString打印的，但是普通数组是不可以直接toString打印的
//        return elem.toString(); // 这个打印的是这个数组的地址
    }

• 但是上面的分析还是有些不够严谨，对于插入元素的位置还需要考虑，这个位置的正负以及是否会造成空间浪费（eg：隔空插入元素）；此外，数组是否会发生越界异常也需要考虑。

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

        //1.pos位置的判断 -> pos 不能为负的 或 pos不能隔空插元素
        checkPosOfAdd(pos);
        //1.先挪动元素，将最后面元素逐个往前挪
        //i >= pos 时元素才会往前移
        for (int i = usedSize - 1; i >= pos; i--) {

            elem[i+1] = elem[i];
        }//挪完将指定元素插入到位置中
         elem[pos] = data;
        usedSize++;

        }

    @Override
    public String toString() {
        // 数组的话是没有toString的，可以使用它的工具类去打印
        return Arrays.toString(elem);
//        刚刚写的是return elem.tostring
        // 当这个是list类型，不是普通的数组类型的时候，是可以直接调用toString打印的，但是普通数组是不可以直接toString打印的
//        return elem.toString(); // 这个打印的是这个数组的地址
    }

    //1.pos位置的判断 -> pos 不能为负的 或 pos不能隔空插元素
    public void checkPosOfAdd(int pos){
        if(pos <0 || pos > usedSize){
            throw new PosException("pos位置是" + pos);
        }
    }

• ⚠️如果当这个数组满了插入元素，可看到报越界异常。
  
  ✅️解决方案：判段这个要插入的数组是否满了，满了可以通过扩容来解决越界问题。

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

        //1.pos位置的判断 -> pos 不能为负的 或 pos不能隔空插元素
        checkPosOfAdd(pos);
        //2.如果这个数组是满的，则需要对数组进行扩容才能插入新元素
        isFulling();


        //1.先挪动元素，将最后面元素逐个往前挪
        //i >= pos 时元素才会往前移
        for (int i = usedSize - 1; i >= pos; i--) {
            elem[i+1] = elem[i];
        }//挪完将指定元素插入到位置中
         elem[pos] = data;
        usedSize++;

        }

    @Override
    public String toString() {
        // 数组的话是没有toString的，可以使用它的工具类去打印
        return Arrays.toString(elem);
//        刚刚写的是return elem.tostring
        // 当这个是list类型，不是普通的数组类型的时候，是可以直接调用toString打印的，但是普通数组是不可以直接toString打印的
//        return elem.toString(); // 这个打印的是这个数组的地址
    }

    //1.pos位置的判断 -> pos 不能为负的 或 pos不能隔空插元素
    public void checkPosOfAdd(int pos){
        if(pos <0 || pos > usedSize){
            throw new PosException("pos位置是" + pos);
        }
    }

    //2.如果这个数组是满的，则需要对数组进行扩容才能插入新元素
    public void isFulling(){
        elem = Arrays.copyOf(elem,2*elem.length);
    }

查找当前元素是否存在

    /**
     * 查找当前元素是否存在
     * @param toFind
     * @return
     */
    @Override
    public boolean contains(int toFind) {
        for(int i = 0 ; i < usedSize ; i++){
            if(elem[i] == toFind){
                return true;
            }
        }
        return false;
    }

如果这里的元素是引用类型，需要通过equals进行比较。

查找当前元素的下标

    /**
     * 查找当前元素的下标
     * @param toFind
     * @return
     */
    @Override
    public int indexOf(int toFind) {
        for(int i = 0 ; i < usedSize ; i++){
            if(elem[i] == toFind){//如果这里是引用数据类型需要用equals进行比较
                return i;
            }
        }
        return -1;
    }

获取对应下标对应元素的数值

    /**
     * 获取pos位置的值
     * @param pos
     * @return
     */
    @Override
    public int get(int pos) {

        //1.判断pos合法性
        checkPosGet(pos);
        //2.pos为空的异常处理
        if(isEmpty()){
            throw new EmptyException("数组为空，无法获取元素" );
        }
        return elem[pos];
    }

    //1.判断pos合法性
    public  void checkPosGet(int pos){
        if(pos < 0 || pos >= usedSize){
            throw new PosException("Pos 不合法 ， 位置是：" + pos);
        }

    }
    //2.pos为空的异常处理 -> 此时pos正好符合>=usedSize(为0)的情况，算是1的一种。  
    public boolean isEmpty(){
        return  usedSize == 0;
    }

更新对应下标的元素值

    /**
     * 更新pos位置的值为 value
     * @param pos
     * @param value
     */
    @Override
    public void set(int pos, int value) {
        //1.检查pos位置的合法性
        checkPosOfSet(pos);
        //2.pos为空的异常处理
        if(isEmpty()){
            throw new EmptyException("顺序表为空");
        }
        elem[pos] = value;
    }
    public void checkPosOfSet(int pos){
        if(pos < 0 || pos >= usedSize){
            throw  new PosException("Pos 位置不合法位置是 ："+ pos);
        }
    }

获取顺序表的大小

    /**
     * 获取顺序表的大小
     * @return
     */
    @Override
    public int size() {
        return this.usedSize;
    }

删除指定元素

   /**
     * 删除toRemove这个数字
     * 删除指定元素
     * @param toRemove
     */
    @Override
    public void remove(int toRemove) {
        //首先，找到元素下标
        //因为刚刚已经实现过通过元素寻找下标的方法了，现在只要调用这个方法即可找到对应元素的下标
        int index = indexOf(toRemove);
        //然后，将这个位置前面的元素往后移动覆盖掉即可删除
        for(int i = index ; i < usedSize - 1  ; i++){
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

释放内存

• 在源码中是先将元素置为null之后，再将空间置为0进行释放的。

    /**
     * 清空顺序表，防止内存泄漏
     */
    @Override
    public void clear() {
        usedSize = 0;
    }

• 因为示例中的数据都是int类型不是引用类型，所以如果需要释放内存，直接将其赋值为0即可，而对于引用类型由于他们有内存地址所以需要将它们置为null才能释放内存。