1.自我定义ArrayList类
在自我实现Java中的ArrayList（顺序表）之前，我们需要先自我定义一个ArrayList类，定义方式如下：
public class MyArrayList{ //创建一个数组 private int[] array; //用于记录数组中的元素格式 private int arrayNumber; //初始化数组原始大小 public static final int CAPACITY = 10; //构造方法 public MyArrayList() { this.array = new int[CAPACITY]; this.arrayNumber = 0; }
这段代码定义了一个名为MyArrayList的类，用于实现顺序表。以下是对代码的分析：
- 私有属性：
- array：一个整型数组，用于存储元素。
- arrayNumber：一个整型变量，用于记录数组中元素的个数。
- CAPACITY：一个常量，表示数组的初始容量。
- 构造方法：
- MyArrayList()：构造方法初始化了数组array为长度为CAPACITY的整型数组，并将arrayNumber初始化为0。
这样我们就定义好了一个ArrayList类，接下来就是实现Java中ArrayList中的方法了。
2.自我实现ArrayList中的方法
在自我实现ArrayList中的方法之前，先让我们看一下要实现哪些方法：
// 新增元素,默认在数组最后新增 public void add(int data) { } // 在 pos 位置新增元素 public void add(int pos, int data) { } // 判定是否包含某个元素 public boolean contains(int toFind) { } // 查找某个元素对应的位置 public int indexOf(int toFind) { } // 获取 pos 位置的元素 public int get(int pos) { } // 给 pos 位置的元素设为 value public void set(int pos, int value) { } //删除第一次出现的关键字key public void remove(int toRemove) { } // 获取顺序表长度 public int size() { } // 打印顺序表 public void display() { }
那么接下来让我们一个一个的自我实现：
（1）新增元素,默认在数组最后新增
Java代码：
public boolean isFull() { return this.array.length == this.arrayNumber; } private void beBig() { this.array = Arrays.copyOf(this.array, this.array.length * 2); } public void add(int data) { //判断是否已满 if (isFull()) { //顺序表满了就进行扩容 beBig(); } //顺序表未满，添加元素 this.array[this.arrayNumber] = data; this.arrayNumber++; }
现在我们对这些代码进行分析：
- isFull() 方法用于检查顺序表是否已满。它通过比较数组的长度和数组中元素的个数来确定是否满了。如果数组的长度等于数组中元素的个数（即 array.length == arrayNumber），则表示数组已满，返回 true；否则返回 false。
- beBig() 方法用于扩容数组。它使用 Arrays.copyOf() 方法将原数组扩容为原来的两倍大小。这样做是为了在顺序表满时能够动态扩展数组大小以容纳更多的元素。
- add(int data) 方法用于向顺序表中添加元素。首先，它检查顺序表是否已满，如果满了，则调用 beBig() 方法进行扩容。然后，将新元素添加到数组的下一个位置，并更新数组中元素的个数。
（2）在 pos 位置新增元素
Java代码：
public boolean isFull() { return this.array.length == this.arrayNumber; } private void beBig() { this.array = Arrays.copyOf(this.array, this.array.length * 2); } public void add(int pos, int data) throws IndexException { //如果索引异常就抛出异常 if (pos < 0 || pos > this.arrayNumber) { throw new IndexException("索引异常！！！"); } else { //判断是否已满 if (isFull()) { 对原顺序表进行扩容 beBig(); } else { for (int i = this.arrayNumber - 1; i >= pos; i--) { this.array[i + 1] = this.array[i]; } this.array[pos] = data; this.arrayNumber++; } } }
现在让我们逐行分析一下：
- public boolean isFull(): 这个方法检查数组是否已满，即数组中的元素数量是否等于数组的长度。如果是，则返回true，否则返回false。
- private void beBig(): 这个方法用于扩大数组的容量。它使用Arrays.copyOf()方法创建了一个新数组，长度是原数组的两倍，然后将原数组的内容复制到新数组中。
- public void add(int pos, int data) throws IndexException: 这是一个添加元素的方法，接受两个参数：要添加的位置pos和要添加的数据data。如果位置超出了数组的范围，则抛出IndexException异常。否则，如果数组已满，则先扩大数组的容量，然后执行插入操作；如果数组未满，则将从插入位置开始的元素向后移动一个位置，为新元素腾出位置，并将新元素插入到指定位置。
（3）判定是否包含某个元素
Java代码：
public boolean contains(int toFind) { //循环遍历顺序表查找目标元素 for (int i = 0; i < this.arrayNumber; i++) { if (this.array[i] == toFind) { return true; } } return false; }
现在让我们来逐步分析一下：
- 方法签名：public boolean contains(int toFind)
- 返回类型：boolean，表示是否包含特定元素。
- 参数：int toFind，表示要查找的元素值。
- 循环结构：
- 使用 for 循环遍历整数数组。
- 循环变量 i 从 0 开始逐渐增加，直到数组长度（this.arrayNumber）。
- 条件判断：
- 在每次循环中，通过 if 语句检查当前数组元素是否等于要查找的元素 toFind。
- 如果找到了匹配的元素，返回 true，表示数组中包含了要查找的元素。
- 返回结果：
- 如果整个循环执行完毕都没有找到匹配的元素，则返回 false，表示数组不包含要查找的元素。
（4）查找某个元素对应的位置
Java代码：
public int indexOf(int toFind) { //遍历顺序表查找元素位置 for (int i = 0; i < this.arrayNumber; i++) { if (this.array[i] == toFind) { return i; } } return -1; }
让我逐行解释一下：
- public int indexOf(int toFind) {: 这是一个公有方法，用于查找数组中某个特定元素的索引。方法的参数 toFind 是要查找的目标元素。
- for (int i = 0; i < this.arrayNumber; i++) {: 这是一个 for 循环，从数组的第一个元素开始逐个检查，直到数组的长度为止。this.arrayNumber 可能是数组的长度，尽管代码中未显示出来，但我们可以假设它是这样的。
- if (this.array[i] == toFind) {: 在循环的每一次迭代中，检查数组中当前位置的元素是否等于我们要查找的元素 toFind。
- return i;: 如果找到了匹配的元素，就返回当前元素的索引 i。
- return -1;: 如果整个数组都被遍历了但没有找到匹配的元素，则返回 -1，表示未找到。
（5）获取 pos 位置的元素
Java代码：
public boolean isEmpty() { return this.arrayNumber == 0; } public int get(int pos) throws EmptyException, IndexException { //判断数组是否为空 if (isEmpty()) { throw new EmptyException("数组为空！！！"); } //判断数组索引是否越界 if (pos < 0 || pos >= this.arrayNumber) { throw new IndexException("索引异常！！！"); } return this.array[pos]; }
现在让我逐行解释一下：
- isEmpty() 方法用于检查数组是否为空。它通过检查 arrayNumber 属性是否为 0 来判断数组是否为空。如果 arrayNumber 为 0，则返回 true，否则返回 false。
- get(int pos) 方法用于获取数组中指定位置的元素。它首先调用 isEmpty() 方法来检查数组是否为空。如果数组为空，则抛出 EmptyException 异常，表示数组为空。然后，它检查所请求的位置是否有效，即是否在数组范围内。如果位置 pos 小于 0 或者大于等于 arrayNumber，则抛出 IndexException 异常，表示索引异常。如果以上两个条件都通过了，它返回数组中位置 pos 的元素值。
（6）给 pos 位置的元素设为 value
Java代码：
public boolean isEmpty() { return this.arrayNumber == 0; } public void set(int pos, int value) throws EmptyException, IndexException { //判断数组是否为空 if (isEmpty()) { //抛出异常 throw new EmptyException("数组为空！！！"); } //判断数组索引是否越界 if (pos < 0 || pos >= this.arrayNumber) { //抛出异常 throw new IndexException("索引异常！！！"); } this.array[pos] = value; }
现在让我逐行解释一下：
- isEmpty() 方法用于判断数组是否为空。它返回一个布尔值，表示数组中是否没有元素。具体来说，它通过检查数组中存储的元素数量是否为0来确定数组是否为空。
- set(int pos, int value) 方法用于设置数组中指定位置的元素值。它接受两个参数：位置（pos）和要设置的值（value）。在设置之前，它会先检查数组是否为空，如果为空则抛出 EmptyException 异常；然后检查位置是否合法，如果位置越界则抛出 IndexException 异常；最后，如果一切正常，它会将给定的值设置到指定位置的数组元素中。
（7）删除第一次出现的关键字key
Java代码：
public boolean isEmpty() { return this.arrayNumber == 0; } public void remove(int toRemove) throws EmptyException{ //判断数组是否为空 if(isEmpty()){ //抛出异常 throw new EmptyException("数组为空！！！"); } //遍历查找目标元素 int index = indexOf(toRemove); if(index == -1){ return; } for(int i = index;i<this.arrayNumber-1;i++){ this.array[i] = this.array[i+1]; } this.arrayNumber--; }
现在让我逐行解释一下：
- isEmpty() 方法：这个方法用于检查数组是否为空。它通过检查 arrayNumber 是否等于 0 来确定数组是否为空。如果 arrayNumber 为 0，则返回 true，表示数组为空，否则返回 false。
- remove(int toRemove) 方法：这个方法用于从数组中删除指定的元素 toRemove。首先，它会检查数组是否为空，如果数组为空，则抛出 EmptyException 异常。然后，它会调用 indexOf(toRemove) 方法来查找 toRemove 在数组中的索引位置。如果找不到目标元素，则直接返回，不做任何操作。如果找到了目标元素，则会从该索引位置开始，将后面的元素向前移动一位，覆盖掉要删除的元素。最后，将数组的元素数量 arrayNumber 减一，表示成功删除了一个元素。
（8）获取顺序表长度
Java代码：
public int size() { return this.arrayNumber; }
这里不做过多的解释了！！！
（9）打印顺序表
Java代码：
public void display() { //循环遍历输出 for (int i = 0; i < this.arrayNumber; i++) { System.out.print(this.array[i] + " "); } }
这里就是最简单的循环遍历数组，将数组中的元素进行输出操作。
这样我们就完成了顺序表中所有的方法的自我实现了，当然读者还可以自己为这个自我实现的顺序表添加一下方法。
3.总结自我实现ArrayList
从上边的文章中，我们自我创建了一个ArrayList，并且自我去实现了其中的方法，所以我们对上文进行一些总结，对于自我实现一个类似于ArrayList的数据结构的流程可以概括如下：
- 确定数据结构：选择合适的数据结构来存储元素。通常使用数组作为基础数据结构。
- 定义类和成员变量：创建一个类来表示 ArrayList，定义数组作为存储元素的数据结构，并定义一个表示数组当前大小的变量。
- 实现构造方法：编写构造方法初始化数组和其他必要的变量。
- 实现添加元素方法：编写方法来添加新的元素到数组中。需要考虑数组已满时的动态扩容。
- 实现获取元素方法：编写方法通过索引获取数组中的元素。
- 实现删除元素方法：编写方法来删除指定位置的元素。需要考虑删除元素后，保持数组的连续性。
- 实现其他操作方法：根据需要实现其他方法，如获取数组大小、清空数组、判断数组是否为空等。
- 异常处理：考虑可能出现的异常情况，如访问空数组、越界访问等，并进行适当的异常处理。
最后，我们附上自我实现的ArrayList的类的完整代码：
public class MyArrayList { private int[] array; private int arrayNumber; public static final int CAPACITY = 10; //构造方法 public MyArrayList() { this.array = new int[CAPACITY]; this.arrayNumber = 0; } public boolean isFull() { return this.array.length == this.arrayNumber; } private void beBig() { this.array = Arrays.copyOf(this.array, this.array.length * 2); } public void add(int data) { //判断是否已满 if (isFull()) { //顺序表满了就进行扩容 beBig(); } //顺序表未满，添加元素 this.array[this.arrayNumber] = data; this.arrayNumber++; } public void display() { for (int i = 0; i < this.arrayNumber; i++) { System.out.print(this.array[i] + " "); } } public void add(int pos, int data) throws IndexException { if (pos < 0 || pos > this.arrayNumber) { throw new IndexException("索引异常！！！"); } else { if (isFull()) { beBig(); } else { for (int i = this.arrayNumber - 1; i >= pos; i--) { this.array[i + 1] = this.array[i]; } this.array[pos] = data; this.arrayNumber++; } } } public boolean contains(int toFind) { for (int i = 0; i < this.arrayNumber; i++) { if (this.array[i] == toFind) { return true; } } return false; } public int indexOf(int toFind) { for (int i = 0; i < this.arrayNumber; i++) { if (this.array[i] == toFind) { return i; } } return -1; } public boolean isEmpty() { return this.arrayNumber == 0; } public int get(int pos) throws EmptyException, IndexException { //判断数组是否为空 if (isEmpty()) { throw new EmptyException("数组为空！！！"); } //判断数组索引是否越界 if (pos < 0 || pos >= this.arrayNumber) { throw new IndexException("索引异常！！！"); } return this.array[pos]; } public void set(int pos, int value) throws EmptyException, IndexException { //判断数组是否为空 if (isEmpty()) { //抛出异常 throw new EmptyException("数组为空！！！"); } //判断数组索引是否越界 if (pos < 0 || pos >= this.arrayNumber) { //抛出异常 throw new IndexException("索引异常！！！"); } this.array[pos] = value; } public void remove(int toRemove) throws EmptyException { //判断数组是否为空 if (isEmpty()) { //抛出异常 throw new EmptyException("数组为空！！！"); } //遍历查找目标元素 int index = indexOf(toRemove); if (index == -1) { return; } for (int i = index; i < this.arrayNumber - 1; i++) { this.array[i] = this.array[i + 1]; } this.arrayNumber--; } public int size() { return this.arrayNumber; } }
