Java中ArrayList(顺序表)的自我实现(如果想知道Java中怎么自我实现ArrayList,那么只看这一篇就足够了!)

简介: Java中ArrayList(顺序表)的自我实现(如果想知道Java中怎么自我实现ArrayList,那么只看这一篇就足够了!)

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的类,用于实现顺序表。以下是对代码的分析:

  1. 私有属性:
  • array:一个整型数组,用于存储元素。
  • arrayNumber:一个整型变量,用于记录数组中元素的个数。
  • CAPACITY:一个常量,表示数组的初始容量。
  1. 构造方法:
  • 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++;
    }

 现在我们对这些代码进行分析:

  1. isFull() 方法用于检查顺序表是否已满。它通过比较数组的长度和数组中元素的个数来确定是否满了。如果数组的长度等于数组中元素的个数(即 array.length == arrayNumber),则表示数组已满,返回 true;否则返回 false。
  2. beBig() 方法用于扩容数组。它使用 Arrays.copyOf() 方法将原数组扩容为原来的两倍大小。这样做是为了在顺序表满时能够动态扩展数组大小以容纳更多的元素。
  3. 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++;
            }
        }
    }

现在让我们逐行分析一下:

  1. public boolean isFull(): 这个方法检查数组是否已满,即数组中的元素数量是否等于数组的长度。如果是,则返回true,否则返回false。
  2. private void beBig(): 这个方法用于扩大数组的容量。它使用Arrays.copyOf()方法创建了一个新数组,长度是原数组的两倍,然后将原数组的内容复制到新数组中。
  3. 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;
    }

现在让我们来逐步分析一下:

  1. 方法签名:public boolean contains(int toFind)
  • 返回类型:boolean,表示是否包含特定元素。
  • 参数:int toFind,表示要查找的元素值。
  1. 循环结构:
  • 使用 for 循环遍历整数数组。
  • 循环变量 i 从 0 开始逐渐增加,直到数组长度(this.arrayNumber)。
  1. 条件判断:
  • 在每次循环中,通过 if 语句检查当前数组元素是否等于要查找的元素 toFind。
  • 如果找到了匹配的元素,返回 true,表示数组中包含了要查找的元素。
  1. 返回结果:
  • 如果整个循环执行完毕都没有找到匹配的元素,则返回 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;
    }

让我逐行解释一下:

  1. public int indexOf(int toFind) {: 这是一个公有方法,用于查找数组中某个特定元素的索引。方法的参数 toFind 是要查找的目标元素。
  2. for (int i = 0; i < this.arrayNumber; i++) {: 这是一个 for 循环,从数组的第一个元素开始逐个检查,直到数组的长度为止。this.arrayNumber 可能是数组的长度,尽管代码中未显示出来,但我们可以假设它是这样的。
  3. if (this.array[i] == toFind) {: 在循环的每一次迭代中,检查数组中当前位置的元素是否等于我们要查找的元素 toFind。
  4. return i;: 如果找到了匹配的元素,就返回当前元素的索引 i。
  5. 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];
    }

现在让我逐行解释一下:

  1. isEmpty() 方法用于检查数组是否为空。它通过检查 arrayNumber 属性是否为 0 来判断数组是否为空。如果 arrayNumber 为 0,则返回 true,否则返回 false。
  2. 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;
    }

现在让我逐行解释一下:

  1. isEmpty() 方法用于判断数组是否为空。它返回一个布尔值,表示数组中是否没有元素。具体来说,它通过检查数组中存储的元素数量是否为0来确定数组是否为空。
  2. 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--;
    }

现在让我逐行解释一下:

  1. isEmpty() 方法:这个方法用于检查数组是否为空。它通过检查 arrayNumber 是否等于 0 来确定数组是否为空。如果 arrayNumber 为 0,则返回 true,表示数组为空,否则返回 false。
  2. 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的数据结构的流程可以概括如下:

  1. 确定数据结构:选择合适的数据结构来存储元素。通常使用数组作为基础数据结构。
  2. 定义类和成员变量:创建一个类来表示 ArrayList,定义数组作为存储元素的数据结构,并定义一个表示数组当前大小的变量。
  3. 实现构造方法:编写构造方法初始化数组和其他必要的变量。
  4. 实现添加元素方法:编写方法来添加新的元素到数组中。需要考虑数组已满时的动态扩容。
  5. 实现获取元素方法:编写方法通过索引获取数组中的元素。
  6. 实现删除元素方法:编写方法来删除指定位置的元素。需要考虑删除元素后,保持数组的连续性。
  7. 实现其他操作方法:根据需要实现其他方法,如获取数组大小、清空数组、判断数组是否为空等。
  8. 异常处理:考虑可能出现的异常情况,如访问空数组、越界访问等,并进行适当的异常处理。

最后,我们附上自我实现的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;
    }
    
}


相关文章
|
24天前
|
存储 Java API
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
|
14天前
|
存储 安全 Java
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
|
24天前
|
设计模式 Java 编译器
Java中的内部类(如果想知道Java中有关内部类的知识点,那么只看这一篇就足够了!)
Java中的内部类(如果想知道Java中有关内部类的知识点,那么只看这一篇就足够了!)
|
21天前
|
存储 Java 索引
深度解读Java的ArrayList
深度解读Java的ArrayList
|
5天前
|
设计模式 并行计算 安全
Java面试题: 如何使用装饰器模式来增强ConcurrentHashMap的功能?在什么情况下应该使用CopyOnWriteArrayList而不是ArrayList?
Java面试题: 如何使用装饰器模式来增强ConcurrentHashMap的功能?在什么情况下应该使用CopyOnWriteArrayList而不是ArrayList?
10 0
|
18天前
|
Java
【JAVA集合篇 - ArrayList】你真的了解ArrayList吗?
【JAVA集合篇 - ArrayList】你真的了解ArrayList吗?
8 0
|
4天前
|
Java 调度
Java线程的六种状态
Java线程有六种状态: 初始(NEW)、运行(RUNNABLE)、阻塞(BLOCKED)、等待(WAITING)、超时等待(TIMED_WAITING)、终止(TERMINATED)。
15 1
|
5天前
|
存储 安全 Java
Java面试题:请解释Java内存模型(JMM)是什么,它如何保证线程安全?
Java面试题:请解释Java内存模型(JMM)是什么,它如何保证线程安全?
37 13
|
1天前
|
安全 Java 开发者
Java并发编程中的线程安全性与性能优化
在Java编程中,处理并发问题是至关重要的。本文探讨了Java中线程安全性的概念及其在性能优化中的重要性。通过深入分析多线程环境下的共享资源访问问题,结合常见的并发控制手段和性能优化技巧,帮助开发者更好地理解和应对Java程序中的并发挑战。 【7月更文挑战第14天】
|
1天前
|
监控 Java API
Java并发编程之线程池深度解析
【7月更文挑战第14天】在Java并发编程领域,线程池是提升性能、管理资源的关键工具。本文将深入探讨线程池的核心概念、内部工作原理以及如何有效使用线程池来处理并发任务,旨在为读者提供一套完整的线程池使用和优化策略。