数组

数组三大特性


数组是一种线性表的数据结构,它使用一组连续的内存空间,来存储一组具有相同类型的数据。

有三个关键词可以辅助我们理解数组,线性表、连续内存空间、相同数据类型

线性表

由零个或多个数据元素组成的有限序列,线性表中的第一个元素无前驱,最后一个元素无后继,其他元素有且只有一个前驱和后继。常见的线性表除了数组,还有链表、队列、栈也是线性表。

有线性表就有非线性表,如:树、堆、图等就是非线性表。

连续内存空间

连续的内存空间,这个存储特性非常重要,它使得硬件对其友好。因为内存空间是连续的,而数组中的每个块的大小又是相等的。所以非常容易推导出公式:数组头存储的物理地址 + 偏移量=指定下标的物理地址。因为直接能够计算出物理地址,因而计算机就无需再寻址可以直接访问内存,因此这个特性也被称为:数组的随机访问特性

我们经常会听到如下结论:数据查询的时间复杂度是O(1),这个结论本身是不太准确的。数组只有在随机访问的情况下,它的时间复杂度才是O(1)。如果是正常的搜索,即使才有性能最优的二分查找,所需的时间复杂度也要O(logn)。

前面讲到了数组连续内存空间带来的益处:提供了随机访问特性。但是有利也有弊,因为要满足数组占用空间的连续性的特性,就需要靠搬迁数据来保证内存空间的连续性

相同的数据类型

这是一个隐性的定义,日常的时候我们几乎不会关注这个点。我们试想一下,如果存储在数组中的数组,包含 int(4)、long(8)、char(2)、byte(1)、double(8)、float(4) 元素的数组,那么计算物理内存地址的时候是多么麻烦的一件事情。

正是因为要去类型一致,所以会存在空间上的浪费。在对内存空间要求高的应用场景下,如:Redis中自建了的ziplist的数据结构,达到了节省空间的目的。

低效的插入删除操作

import java.util.Arrays;

public class Test {
    @org.junit.Test
    public void test() {
        Object[] objects = new Object[5];
        for (int i = 0; i < 5; i++) {
            objects[i] = i;
        }
        System.out.println(Arrays.asList(objects));
        // case 1: 标记清除
        objects[1] = null;
        System.out.println(Arrays.asList(objects));
        // case 2: 执行删除
        Object[] newObjects = new Object[4];
        System.arraycopy(objects, 0, newObjects, 0, 1);
        System.arraycopy(objects, 2, newObjects, 1, 3);
        System.out.println(Arrays.asList(newObjects));
    }
}

// [0, 1, 2, 3, 4]
// [0, null, 2, 3, 4]
// [0, 2, 3, 4]

初始化了样本数据:[0, 1, 2, 3, 4],此时我们希望删除数据1,我们可以怎么操作呢?

  • 直接将对应位置的数值置为 null,删除后的数据如:[0, null, 2, 3, 4],对应代码 case 1。
  • 执行删除操作,然后将后面的数据搬迁,最终数据如:[0, 2, 3, 4],对应代码 case 2。

标记清除的本质是使用空间换时间,我们可以通过触发删除执行的频率来调整性能。删除操作,对应了:新数组申请、数据的拷贝、原数据的释放,相比标记清除算法是一个重量级的操作。

ArrayList 能否完全替代数组?

ArrayList 的优势是官方对 数组的封装,它提供了许多实用的功能,比如:搬迁数据、自动扩容等,种种这些都是手写数组比较困扰的事情。

通常我们的应用场景,使用ArrayList是足够的,但这也不表明数组已无用武之地。因为要使用 ArrayList,就必须要满足 ArrayList 使用的条件。那么在破坏 ArrayList 使用的条件的一些例外情况,则是需要使用数组的。

  • ArrayList 使用泛型,不支持基本类型。高性能场景下(包装类型会自动装箱、拆箱),推荐使用原始类型。
  • 高维数组场景下,选择array[0][0][0][0][0][0][1]对比选择list.get(0).get(0).get(0).get(0).get(0).get(0).get(1),感觉数组更加直观一点。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 责任链模式(分离职责,动态组合)

    登录、注册功能是日常开发中必备的功能,不管哪里都有它的身影。现在需要给客户提供一个注册功能,就如下图那样。

    幺鹿
  • UML — — 类图目录

    这里不会将UML的各种元素都提到,我只想讲讲类图中各个类之间的关系; 能看懂类图中各个类之间的线条、箭头代表什么意思后,也就足够应对 日常的工作和交流; 同时,...

    幺鹿
  • DataBinding·常用注解说明

    Observable接口提供给开发者添加/移除监听者的机制。为了使开发更便捷,我们创建了BaseObservable类,它已经实现了Observable接口中的...

    幺鹿
  • 前端入门11-JavaScript语法之数组声明正文-数组

    作为一个前端小白,入门跟着这几个来源学习,感谢作者的分享,在其基础上,通过自己的理解,梳理出的知识点,或许有遗漏,或许有些理解是错误的,如有发现,欢迎指点下。

    请叫我大苏
  • Python科学计算 | NumPy——快速处理数据01

    最近在看张若愚老师的《Python科学计算》,也算是对Python的基本功进行一次锻炼,看着就记下笔记,这里开个系列来分享一下个人笔记,文章内容都是markdo...

    Sam Gor
  • Shell 数组

    Shell中数据类型不多,比如说字符串,数字类型,数组。数组是其中比较重要的一种,同时Shell中的数组不像JAVA/C,只能是一维数组,没有二维数组;数组元素...

    企鹅号小编
  • C++小议二维数组

    一、二维数组的介绍 当数组元素具有两个下标时, 该数组称为二维数组。 二维谁可以看做具有行和列的平面数据结构。 二、二维数组的定义 定义二维数组的形式:

    老九学堂-小师弟
  • 数组基础知识: 100万成员的数组取第一和最后一个有性能差距吗?

    数组几乎可以是所有软件工程师最常用到的数据结构,正是因为如此,很多开发者对其不够重视.

    帅地
  • Java Review (五、数组)

    数组是编程语言中最常见的一种数据结构,可用于存储多个数据,每个数组元素存放一个数据,通 常可通过数组元素的索引来访问数组元素,包括为数组元素赋值和取出数组元素的...

    三分恶
  • 房上的猫:数组

    一.数组:  1.定义:   (1)数组就是一个变量,用于将相同数据类型的数据储存在内存中   (2)数组中的每一个数据元素都属于统一数据类型  2.基本要素:...

    房上的猫

扫码关注云+社区

领取腾讯云代金券