图文+实战，轻松学会数据结构【数组】

数组可以说是最基本最常见的数据结构，数组一般用来存储相同类型的数据，可通过数组名和下标进行数据的访问和更新，由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据（这叫作“随机访问”），因此数组的访问速度非常可观，而添加和删除数据比较耗工夫

假设数组中有 n 个数据，由于访问数据时使用的是随机访问（通过下标可计算出内存地址），所以时间复杂度为恒定的O(1)
但另一方面，想要向数组中添加或删除数据时，必须把目标位置后面的数据一个个移动，如果在数组头部添加数据，就要移动n次，时间复杂度为O(n)，删除操作也是同理

实战Java模拟数组

使用Java语言来模拟数组的实现过程，目标是实现一个无限扩容，并且完成增删改查，返回数组长度，判断数组是否为空等方法，这里注意，如果自己想没有思路，可以将这个过程通过纸和笔来画出来，帮助理解，真的很实用

🆗，目标明确，那就开始写代码了，首先创建一个类表示自己编写的数组类，取名为 MyArray

数组初始化

首先定义一个属性，int类型数组，elements，并使用无参构造进行数组初始化，默认是没有元素的
/**
 * 用于存储数据的数组
 */
private int[] elements;

/**
 * 初始化
 */
public MyArray() {
    elements = new int[0];
}

length方法，返回数组长度

获取数组长度的方法，返回数组长度
/**
 * 获取数据长度的方法
 * @return 返回数组长度
 */
public int length() {
    return this.elements.length;
}

isLegal方法，判断下标是否正常

判断数组下标是否符合要求，即小于0 或者大于数组长度-1 都是不合法的，因为数组的下标是从0开始计算的，true表示输入的下标合法，false表示不合法，并提示
/**
 * 判断数组下标是否符合要求，即 小于0 或者 大于数组长度-1 都是不合法的
 * 因为数组的下标是从0开始计算的
 * @param index 数组下标
 * @return 布尔，true表示输入的下标合法，false表示不合法，并提示
 */
public boolean isLegal(int index) {
    if (index < 0 || index > elements.length - 1) {
        System.out.println("数组下标不合法，操作不成功");
        return false;
    }
    return true;
}

add方法，添加数据

这里难的就是理解数组这种数据结构是不可变长的，一旦确定大小，就没办法修改了，那如果数组装满了，怎么办，数组扩容，说是扩容，本质是创建一个更大的新的数组，把原数组循环赋值给新数组，最后重点，把新数组的引用赋值给原数组这就完成了数组的扩容
/**
 * 完成数组的增
 * @param element 需要加入数组的元素
 */
public void add(int element) {
    // 数组扩容，当添加时就在已有基础上加1
    int newLength = this.elements.length + 1;
    // 创建一个新的大小的数组
    int[] newArr = new int[newLength];
    // 循环将原数组的值赋给新长度的数组
    for (int i = 0; i < elements.length; i++) {
        newArr[i] = elements[i];
    }
    // 把添加元素放在数组中
    newArr[newLength - 1] = element;
    // 把新数组的引用赋值给真的数组，newArr此时就没人引用了，就会被JVM机进行销毁
    elements = newArr;
}

remove方法，移除数据

在进行删除操作时，首先要判断要删除的下标是否合理，如果合理再进行后续操作，否则直接返回，当下标合理，重点来了，这里遍历数组元素，通过判断当前元素是否小于要删除元素的下标，如果时就直接赋值，如果等于，直接 continue 跳过，就相当于删了，否则就是原数组下标值赋给新的数组下标 -1位置的元素
/**
* 数组删除方法
* @param index 待删除数组元素的下标值
*/
public void remove(int index) {
if (!isLegal(index)) {
    return;
}
int[] newArr = new int[elements.length - 1];
for (int i = 0; i < elements.length; i++) {
    if (i < index) {
        newArr[i] = elements[i];
    } else if (i == index) {
        continue;
    } else {
        newArr[i - 1] = elements[i];
    }
}
elements = newArr;
}

update方法，更新数组元素

更新就时指定要改下标为多少的元素，改为多少，但也要注意下标合法判断哦，很简单
/**
 * 更新数组下标元素的值
 * @param index    待更新数组元素的下标
 * @param newValue 待更新下标的值
 */
public void update(int index, int newValue) {
    if (!isLegal(index)) {
        return;
    }
    this.elements[index] = newValue;
}

search方法，查找数组元素

简单的遍历查找数组元素，有则直接返回元素的下标，没有返回-1

/**
 * 查找元素
 * @param targetVal 待查找的目标值
 * @return 数组下标，找到了直接返回，没找到返回-1
 */
public int search(int targetVal) {
    for (int i = 0; i < elements.length; i++) {
        if (elements[i] == targetVal) {
            return i;
        }
    }
    System.out.println("芜湖，没找到");
    return -1;
}

isEmpty方法，检测数组是否为空

只要数组的length不等于0，数组就不为空，就返回false，反之为空，返回true
/**
 * 判断数组是否为空
 * @return 如果为空返回true，不为空返回false
 */
public boolean isEmpty() {
    if (elements.length != 0) {
        return false;
    }
    return true;
}

toString方法，打印遍历后的数组

这里使用toString方法，借助Arrays工具类打印数组
/**
 * 重写 toString，调用Arrays工具类打印数组
 * @return
 */
@Override
public String toString() {
    return Arrays.toString(elements);
}

测试

public static void main(String[] args) {
    // 实例化自己写的数组类
    MyArray myArray = new MyArray();
    // 添加数据
    myArray.add(100);
    myArray.add(-150);
    myArray.add(50);
    myArray.add(4);
    System.out.println(myArray);
    // 移除数据
    myArray.remove(3);
    System.out.println(myArray);
    // 修改数据
    myArray.update(2, 100100);
    System.out.println(myArray);
    myArray.update(10, 100);
    // 查询数组
    int i = myArray.search(100);
    System.out.println(i);
}

[100, -150, 50, 4]
[100, -150, 50]
[100, -150, 100100]
数组下标不合法，操作不成功
0

总结

数组是最基本最常见的数据结构，一般用来存储相同类型的数据
数组可通过数组名和下标进行数据的访问和更新
数组在内存上是连续的，这种连续使得我们可以高效的进行元素“访问”
优点是访问快，复杂度为O(1)；
缺点是插入和删除是时的元素移动导致速度慢，并且其“内存”大小固定。
对于大小固定的数据，选用数组进行存储简直不要太棒

原文地址:https://blog.csdn.net/m0_53321320/article/details/124580107 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1802209996998578176.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部