专栏首页WindCoder数据结构01-数组

数据结构01-数组

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

  • 因为线性表连续的内存空间和相同类型的数据这两个特性,数组的随机访问速度快。
  • 也因此,具有低效的“插入”和“删除”

动态数组,是指数组的容量能动态增长的数组,对于Java而言,Collection集合中提供了ArrayList和Vector。

插入操作

若有一元素想往int[n]的第k个位置插入数据,需要将k~n位置的元素顺序往后移一位。 - 最好时间复杂度O(1),插在末尾不需要移动数据时 - 最坏时间复杂度O(n),插在开头,所有数据均需要移动 - 平均时间复杂度O(n),根据(1+2+3+...+n)n = O(n)

当为无序数组时,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放到第K位上,此时时间复杂度依旧为O(1)。

删除操作

和插入类似:

  • 最好情况时间复杂度为 O(1),删除数组末尾的数据时。
  • 最坏情况时间复杂度为 O(n),删除开头的数据时。
  • 平均情况时间复杂度也为 O(n),同插入操作的公式。

某些情况下,为了避免数据会被搬移多次,我们可以结合JVM 标记清除垃圾回收算法的核心思想,先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

链表与数组的区别:

  • 链表适合插入、删除,时间复杂度 O(1);
  • 数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

容器(ArrayList)与数组的适用场景

ArrayList将所有数组操作封装起来,且支持动态扩容,每当空间不够时,自动扩容空间1.5倍。

  • ArrayList 无法存储基本类型,比如 int、long,需要封装为 Integer、Long 类,而 Autoboxing、Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。
  • 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。
  • 表示多维数组时,用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList<ArrayList> any

数组下标从0开始

int[] a = {10,20,30,40,50} 的存储示例如下:

计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:

a[i]_address = base_address + i * data_type_size

其中,data_type_size是数组中每个元素的大小。

假设计算机为上面的数组int[] a分配了一块连续的内存空间1000~1019,首地址为base_address = 1000,因为是int类型,这里的data_type_size为4个字节,其内存空间分配如图:

如果数组下标从1开始,计算公式将成为如下:

a[k]_address = base_address + (k-1)*type_size

从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。但更多的可能是由于历史原因,C的设计者使用了0作为下标开始,Java沿用了该设计。

结语

这里主要从数据结构角度介绍了一下数组,其它的数组知识点可以看下面两篇文章:

Java漫谈-数组 [转]Java中的数组是对象吗?

本文参考资料

数据结构与算法之美

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java漫谈-数组

    在Java语言中,数组是对象(An object is a class instance or an array.),而且是动态创建的。

    汐楓
  • Java中的数组是对象吗?

    首先说明:Java中的数组是对象,这个可以查看The Java Language Specification SE(4.3.1)可得,另外本文讨论的相关问题的结...

    汐楓
  • JavaScript中字符串与数组的相关操作

    如果不包含在数组中,则返回 -1,若是包含,则返回对应元素所在数组中的下标值,该值从0开始;

    汐楓
  • 探究JS V8引擎下的“数组”底层实现

    JavaScript 中的数组有很多特性:存放不同类型元素、数组长度可变等等,这与数据结构中定义的数组结构或者C++、Java等语言中的数组不太一样,那么JS数...

    2020labs小助手
  • 数组是如何随机访问元素?数组下标为什么从0开始,而不是1?

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

    搜云库技术团队
  • Python进阶:NumPy

    NumPy(Numerical Python) 是 Python 语言的一个扩展程序库,支持大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。这...

    披头
  • 房上的猫:数组

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

    房上的猫
  • 【Java提高十五】数组

    一、什么是数组 数组?什么是数组?在我印象中的数组是应该这样的:通过new关键字创建并组装他们,通过使用整形索引值访问它的元素,并且它的尺寸是不可变的!...

    奋斗蒙
  • 【Java】基础12:什么叫数组?

    {1,2,3,4,5,6}:提前初始化数组的元素,可以有任意多个,但元素的类型要和前面定义的数据类型相匹配。

    刘小爱
  • Day 1-Java-imooc-5.数组

    课程地址:http://www.imooc.com/learn/85 总结图片来自 http://www.imooc.com/article/10535 ? -...

    杨熹

扫码关注云+社区

领取腾讯云代金券