ArrayList与顺序表（1）

前言~🥳🎉🎉🎉

hellohello~，大家好💕💕，这里是E绵绵呀✋✋ ，如果觉得这篇文章还不错的话还请点赞❤️❤️收藏💞 💞 关注💥💥，如果发现这篇文章有问题的话，欢迎各位评论留言指正，大家一起加油！一起chin up！👍👍

💥个人主页：E绵绵的博客
💥所属专栏：JAVA知识点专栏 JAVA题目练习 c语言知识点专栏 c语言题目练习

❤️❤️这篇文章我们就正式开始数据结构的学习，学习其中的顺序表结构。出发吧！

参考文章：Java【顺序表】详细图解模拟实现 + 【ArrayList】常用方法介绍_java顺序表逻辑图-CSDN博客

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。并且顺序表是一个动态数组，可以存储不同的元素，还可以根据需要自动调整大小。

顺序表的模拟实现

❤️❤️为什么要模拟实现：
自己模拟实现简易版的顺序表的增删查改等主要功能，大致理解顺序表的设计思想
再对比学习 Java 提供的集合类当中的 ArrayList ，在学习 Java 的 ArrayList 常用方法的同时，也能学习源码的思想。

成员属性

Java 中的 ArrayList（顺序表）是集合框架中的一个类，要模拟实现顺序表，也得自己实现一个类，首先要考虑这个类中的成员属性。

之前就已经说过，顺序表底层是基于数组实现的，那么成员属性就需要：
1️⃣数组 array：来存放数据
2️⃣变量 capacity ：来记录数组的容量，当数组中的存放的数据满了就需要增大容量
3️⃣变量 useSize：来记录数组已经存放了几个数据

❤️❤️为了体现封装思想，成员属性全部设置为 private
public class SeqList {private int[] array;// 数组private int capacity;// 容量private int useSize;// 当前数组存放的数据的个数
}

⚠️顺序表的模拟实现重在理解理想，为了简便，我们不使用泛型🙅，数组中存放 int 类型

成员方法

❤️❤️如下是模拟顺序表的成员方法，我们通过这些成员方法来模拟顺序表的功能，我们现在来一一实现这些方法。

// 新增元素,默认在数组最后新增
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 toRemove) { }// 获取顺序表长度
public int size() { return 0; }// 清空顺序表
public void clear() { }// 打印顺序表，注意：ArrayList 没有这个方法，为了方便看测试结果给出的
public void display() { }

1.构造方法

构造方法的作用：初始化成员属性，useSize 无需初始化，编译器默认初始化为 0

    // 将顺序表的底层容量设置为capacitypublic SeqList(int capacity){this.capacity = capacity;// 为数组开辟内存空间 this.array = new int[this.capacity];}

    public SeqList() {this.capacity=10;this.array=new int[10];//当无参数时，默认创建一个为容量为10的数组}

2，add——新增元素，默认在数组末尾新增

❗️❗️在末尾新增数据之前，必须考虑：顺序表是否已🈵️，如果满了，则需要扩容之后再添加元素。

所以我们需要分别写出判满和扩容这两个方法：

2.1， isFull——判断顺序表是否已满

    public boolean isFull() {return this.useSize == this.capacity;}

2.2， expandCapacity——扩容

  public  void expandCapacity(){this.array =Arrays.copyOf(this.array,capacity*2);capacity*=2;}
}
利用 copyOf 方法，拷贝数组并将新数组容量扩大两倍，让 this.array 引用新的数组。

✅所以 add 方法的写法为：

    public void add(int data) {// 判满if (isFull()) {// 满了就扩容expandCapacity();}this.array[this.useSize] = data;this.useSize++;}

最后记得，增加数据之后，**useSize 也要++**❗️❗️

3.add——在 pos 位置新增元素

❗️❗️这个方法是：在指定位置新增元素，新增之前必须考虑：
1️⃣顺序表是否已满
2️⃣pos 位置是否合法

3.1， judgeAddPos——判断 add 时pos 位置合法性

判满的方法以及写过了，现在我们需要补充： 判断 pos 位置合法性 的方法
需要思考，pos 在什么位置才是合法呢？

这就要提一个知识点了：在数据结构中，我们每次往一个数据结构里存储数据时，该数据必须有一个前驱信息(前驱是指该元素的前一个元素)，否则不能存放。

所以我们举个例子，如下：

像该情况我们的pos自然不能小于0，而又因为数组中存储数据时，该数据必须要有前驱信息，所以不能大于3。所以pos不能小于0或大于3.

所以在这我们可以得出以下代码
public void judgeAddPos(int pos){if(pos<0||pos>useSize){throw new ArrayListIndexOutOfException("pos位置不合法");}}
}
如果 pos 参数不合法，就不能执行下面的代码，抛出一个异常，所以我们可以自定义一个异常类：
// 继承于运行时异常
public class ArrayListIndexOutOfException extends RuntimeException {public ArrayListIndexOutOfException(String str) {super(str);}
}
这样，当我们 add 时的 pos 参数不合法时，就会抛出异常。

“准备工作” 做足之后，我们需要考虑，如何实现在 pos 位置新增，也就是如何去插入？

🚗🚗🚗
就是把 pos 下标以及之后 的数据 向后依次 覆盖，最终把 pos 位置“空出来”，放入新数据：
  public void add(int pos, int data) {try{judgeAddPos(pos);}catch(Exception e){e.printStackTrace();return;}if(isFull()){expandCapacity();}for (int i = useSize-1; i >pos-1 ; i--) {array[i+1]=array[i];}array[pos]=data;useSize++;}
我们之所以在这用try-catch是为了防止出现这个错误后就直接导致程序崩溃，运行不了后面的程序，所以我们用try-catch捕获它，就能在发生这个错误后依然能运行这个程序。

⚠️注意：
要先移动 3，再移动 2 ——从后往前的顺序移动
如果先移动 2 ，则会把 3 覆盖掉，丢失数据。

最后不要忘记 useSzie++ ❗️❗️

4.contains——判定是否包含某个元素

比较简单，遍历整个数组即可
public boolean contains(int toFind) {for (int i = 0; i <useSize ; i++) {if(array[useSize]==toFind)return  true;}return false;}
因为这里我们存放的是 int 类型的变量，但 ArrayList 当中可以存放引用数据类型的
⚠️⚠️⚠️当表中是引用类型时，就不可以用“等号”比较，应该用 equals 方法

5， indexOf——查找某个元素对应的位置

还是遍历数组，不过这里如果没找到该元素，则要抛出异常，我们上面讲过类似的，这里就不重复讲了。在这我们又自定义了一个异常类。
class  NotFindPos extends RuntimeException{public  NotFindPos(String message){super(message);}
}
    public int indexOf(int toFind) {for (int i = 0; i <useSize ; i++) {if(array[i]==toFind)return i;}try{throw  new NotFindPos("不存在该数"+toFind);   }catch (Exception e){return -1;}}
因为这里我们存放的是 int 类型的变量，但 ArrayList 当中可以存放引用数据类型的
⚠️⚠️⚠️当表中是引用类型时，就不可以用“等号”比较，应该用 equals 方法

6.get——获取 pos 位置的元素

在获取 pos 之前必须保证 pos 位置合法性，但此时的 pos 判断合法性和 add 时的判断规则不一样❗️❗️

🚗🚗🚗
获取 pos 位置的元素，前提是 pos 位置上有数据
此时 pos 的合法性判断规则是：pos 不能小于 0 或不能大于 useSize - 1

6.1，judgePos——判断 pos 位置合法性

    public  void judgePos(int pos){if(pos<0||pos>useSize-1){throw new ArrayListIndexOutOfException("pos位置不合法");}
}}

如果pos 不合法，抛出异常❌

做好 “准备工作” 之后， get 方法就很简单了
  public int get(int pos) {try {judgePos(pos);} catch (Exception e) {e.printStackTrace();return -1;}return array[pos];
}

7， set——给 pos 位置的元素设为 value

老规矩，pos 作为参数时，就要判断合法性❗️❗️代码很简单。
 public void set(int pos, int value) {try{judgePos(pos);}catch(Exception e) {e.printStackTrace();return;}array[pos]=value;}

8，remove——删除第一次出现的数据

我们前面分析过了 add 方法的执行原理，那么删除的原理恰好是和 add 的操作相反：在数组中要 “删除” 一个数，让后面的数据依次向前覆盖即可，对于这个删除操作，我们在图书管理器中碰见过相同的操作，其是一样的思路。

可以看到最后还剩一个 3，没有必要处理，useSize- - 即可✅
别忘了，怎么找到待删除数据的位置呢❓——调用前面写过的 indexOf 方法❗️
    public void remove(int toRemove) {int pos = indexOf(toRemove);if (pos == -1) {// 找不到的情况System.out.println("不存在该数据");}else {// 注意这里的循环条件for (int i = pos; i < this.useSize - 1; i++) {this.array[i] = this.array[i + 1];}this.useSize--;}}
⚠️注意：
i < this.useSize - 1 这里不能写成 <=，当数组正好是满的情况下
this.array[i] = this.array[i + 1]; 这里访问 i+1 下标就会数组越界

9，size——获取顺序表长度

直接返回 useSize 即可
public int size() {return useSize;}

10.clear——清空顺序表

因为该数组存放的内容为基本类型，所以我们只需要将usesize变为0就行。
    public void clear() {this.useSize = 0;}
如果存放的是引用类型，不仅要将useSize变为0，还要将数组中存放的引用变量指向的空间全释放掉。释放掉的方法就是将数组存放的引用变量全指向null，当这些空间没有引用变量指向时，就会自动释放掉。

之所以要释放这些空间是为了防止内存泄漏，提高空间的利用率。

ArrayList类中的clear方法就是一个很好的例子，如下：（因为其数组存放的是引用变量）

11，display——打印顺序表

注意：顺序表中不存在该方法，我们这是为了方便看测试结果自己加的。
    public void display() {for (int i = 0; i < this.useSize; i++) {System.out.print(this.array[i] + " ");}System.out.println();}

ArrayList的模拟实现总代码

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;public class SeqList {private int[] array;// 数组private int capacity;// 容量private int useSize;// 当前数组存放的数据的个数public SeqList(int capacity) {this.capacity = capacity;this.array = new int[this.capacity];}public SeqList() {this.capacity = 10;this.array = new int[10];//当无参数时，默认创建一个为容量为10的数组}// 新增元素,默认在数组最后新增public void add(int data) {// 判满if (isFull()) {// 满了就扩容expandCapacity();}this.array[this.useSize] = data;this.useSize++;}// 在 pos 位置新增元素public void add(int pos, int data) {try {judgeAddPos(pos);} catch (Exception e) {e.printStackTrace();return;}if (isFull()) {expandCapacity();}for (int i = useSize - 1; i > pos - 1; i--) {array[i + 1] = array[i];}array[pos] = data;useSize++;}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < useSize; i++) {if (array[useSize] == toFind)return true;}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < useSize; i++) {if (array[i] == toFind)return i;}try {throw new NotFindPos("不存在该数" + toFind);} catch (Exception e) {e.printStackTrace();return -1;}}// 获取 pos 位置的元素public int get(int pos) {try {judgePos(pos);} catch (Exception e) {e.printStackTrace();return -1;}return array[pos];
}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {try{judgePos(pos);}catch(Exception e) {e.printStackTrace();return;}array[pos]=value;}//删除第一次出现的关键字keypublic void remove(int toRemove) {int pos = indexOf(toRemove);if (pos == -1) {// 找不到的情况System.out.println("不存在该数据");}else {// 注意这里的循环条件for (int i = pos; i < this.useSize - 1; i++) {this.array[i] = this.array[i + 1];}this.useSize--;}}// 获取顺序表长度public int size() {return useSize;}// 清空顺序表public void clear() {useSize=0;}// 打印顺序表，注意：ArrayList 没有这个方法，为了方便看测试结果给出的public void display() {for (int i = 0; i <useSize ; i++) {System.out.print(array[i]+" ");}System.out.println();}public boolean isFull() {return  this.capacity == this.useSize;}public  void expandCapacity(){this.array =Arrays.copyOf(this.array,capacity*2);capacity*=2;}public void judgeAddPos(int pos){if(pos<0||pos>useSize){throw new ArrayListIndexOutOfException("pos位置不合法");}}public  void judgePos(int pos){if(pos<0||pos>useSize-1){throw new ArrayListIndexOutOfException("pos位置不合法");}
}}class  ArrayListIndexOutOfException extends  RuntimeException{public ArrayListIndexOutOfException(String message) {super(message);}
}
class  NotFindPos extends RuntimeException{public  NotFindPos(String message){super(message);}
}

模拟的顺序表SeqList的使用

class Test{public static void main(String[] args) {SeqList seqList=new SeqList();seqList.add(0,4);seqList.add(1);seqList.add(4);seqList.display();seqList.remove(1);seqList.display();seqList.clear();seqList.add(1);seqList.display();seqList.add(5);System.out.println(seqList.contains(5));seqList.set(1,6);seqList.display();System.out.println(seqList.contains(5));System.out.println(seqList.indexOf(2));System.out.println(seqList.get(0));seqList.set(4,3);seqList.add(2,7);seqList.display();System.out.println(seqList.size());}}
对于其打印如下：

❤️❤️我们看显示结果可知这代码的确没问题。所以对于这模拟的顺序表我们就模拟成功了.你们自己也可以使用下该代码，看下是否有误，如果有误欢迎大佬来评论区指点一下。

总结

所以这就是我们的顺序表第一部分内容，我们在这主要对顺序表进行了模拟，使我们在之后的学习中能更加理解顺序表的源码，学习其源码思想。在之后的顺序表第二部分我们将给大家介绍真正的顺序表ArrayList，敬请期待！还希望各位大佬们能给个三连，点点关注，点点赞，发发评论呀，感谢各位大佬~❤️❤️💕💕🥳🎉🎉🎉