【数据结构数组介绍 + 手写简单的ArrayList

2023年 8月 16日 56.1k 0

数组

什么是数组

数组是指一组连续的内存存储位置。数组中的每一个位置称为元素,它们具有相同类型并且使用下标去指示。

每一个索引下标对应一个相同数据类型的值。如下是我偷的一张图:

image.png

数组下标是连续的,数据存储地址也是连续的,存储数据的类型是统一的。

数组特点

  • 数据类型相同:数组中的元素具有相同的数据类型,可以是数值类型也可以是引用类型,反正同一数组里类型相同。
  • 元素有序:数组中的元素以特定的顺序排列,元素的位置称为下标或索引。
  • 通过索引下标访问:数组使用下标(索引从0开始)来访问特定位置的元素。
  • 长度不可改变:一旦创建,数组的长度是初始化之后就不可改变。
  • 数组的数据形式

    数组可以分为一维数组,二维数组,多维数组。

    一维数组顾名思义是一个维度的,每个数组单位存储数据。

    二维数组顾名思义是两个维度的,每个数组单位存储的是一个一维数组。

    n维数组每个数组单位存储的是(n-1)维数组。

    java创建数组:

    • int []a[] = new int[6][6];
    • int a[][] = new int[6][];(使用时必须初始化每个一维数组),比如: a[0] = new int[5];
    • int[][]a = new int[][]{{1,2},{1,3,4}};
    • int[][]a = new int[][]{}; 不报错但无法使用,它不拥有存放数据的内存空间

    上述写法都是不会报错的。

    数组操作

  • 数组的查询: 数组的存储是连续的,可以直接通过下标去查询,时间复杂度O(1)
  • 数组的添加: 数组一般是往后添加的,时间复杂度是O(1),如果是往中间添加,那就比较麻烦,时间复杂度为O(n), 因为后面的数据都要后移一位。
  • 数组删除: 与添加同理,删除之后,删除元素的后面数据都要前移,所以时间复杂度O(n)。
  • image.png

    本人画图水平有限,将就看😂😂😂😂

    数组使用场景

  • 存储固定长度的数据,因为数组长度不可变

  • 实现栈和队列:通过控制元素的添加和移除,数组可以方便实现栈和队列这种先进先出的数据结构。

  • 需要频繁查找元素的场景,连续存储,访问快

  • Java中的数组实现😎

    Java里面有一个数组的实现类ArrayList, 它是Java里的一个典型的数组结构的类。

    但是你可能会发现,它居然不用指定长度,而且我想加多少数据就加多少数据,不是说数组长度是固定的吗😅😅😅

    不要急,是因为它有扩容机制,当满了就去扩容数组,将原数组的数据复制到新数组。

    ArrayList特性

    • 初始容量为10,扩容之后为原来的1.5倍
    • 底层使用Object数组实现,支持快速随机访问

    为了加深对ArrayList的理解,我们手写一个简单的ArrayList。

    手写ArrayList🤩

    首先,我们得搭建基本的类框架,最终类的结构如下图所示:

    同样,使用泛型,为了类型安全。

    image.png

    从上到下依次是:

    • 当前数组大小
    • 数组目前的容量
    • 存放数组的Object数组, 不能是E[], 因为该数组是需要初始化的,而泛型是不能初始化的。

    构造函数

    构造函数里我们设定数组初始大小,初始化Object数组。

    public FakeArrayList() {
        capacity = 10;
        elements = new Object[capacity];
    }
    

    扩容函数

    当前数组大小等于最大容量(没法添加新元素时),这时候就需要对数组进行扩容了。

    实现的原理就是创建一个新数组,然后将旧数组的的值复制进去。

    private void grow(){
        // 表示需要扩容
        if (size==capacity){
            System.out.println("触发扩容");
            // 扩容为1.5倍
            int newCapacity = (capacity >> 1) + capacity;
            // 改变当前的容量
            capacity = newCapacity;
            // 复制到新数组
            elements = Arrays.copyOf(elements, newCapacity);
        }
    }
    

    小心这里有个坑,+号的运算级别高于位运算符,所以位运算符那里需要添加括号。不然结果就是0了。

    添加数据

    我这里是写了两种添加方法,一种是默认的在末尾添加,另一种是在指定索引位置添加

    // 末尾添加

    public void add(E e) {
        // 判断是否扩容
        grow();
        // 添加数据
        elements[size++] = e;
    }
    

    // 指定位置添加

    public void add(int index, E element){
        // 检查索引有无越界, 越界就调用add()函数加到末尾,我这里就没写了,所以我们不能添加超过索引的
        grow();
        // 将index之后及其index的数据往后移动一位
        System.arraycopy(elements, index, elements, index+1, size-index);
        // 添加数据
        elements[index] = element;
        size++;
    }
    

    删除跟这个添加也差不多,我就不赘述了。

    获得数据

    public E get(int index) {
        // 我没有写越界判断,所以不要查索引之外的
        return (E) elements[index];
    }
    

    测试一下

    public static void main(String[] args) {
        FakeArrayList list = new FakeArrayList();
        for (int i = 0; i < 11; i++) {
            list.add("hhh" + i);
        }
        list.add("11");
        System.out.println(list.get(11));
        list.add(3, "替换索引3的数据");
        System.out.println(list.get(3));
        System.out.println("查看数据:");
        for (int i = 0; i < list.size; i++) {
            System.out.println(list.get(i));
        }
    }
    

    输出

    触发扩容
    11
    替换索引3的数据
    查看数据:
    hhh0
    hhh1
    hhh2
    替换索引3的数据
    hhh3
    hhh4
    hhh5
    hhh6
    hhh7
    hhh8
    hhh9
    hhh10
    11

    先验证扩容,添加十一个数,可以看到触发了扩容

    然后验证末尾添加,发现添加成功

    再然后,替换索引为3的数据,再查看发现成功

    最后,打印整个数组,观看最后的数据结构与我们预期的是否相同,验证成功。

    成功完成基本的ArrayList的编写,原来的ArrayList也基本是这个逻辑。

    总结

  • 数组存储空间是连续的,根据索引去获取数据
  • 数组查询很快,中间插入和删除较慢
  • 数组长度是不可变的
  • Java的ArrayList实现的数组可以扩容(新数组)
  • 手写一个简单的ArrayList不难
  • 相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论