C# · 12月 20, 2021

数据结构–数组

定义

数组 :是一种线性表数据结构,他用一组连续的内存空间,来储存一组相同的数据类型的数据

这里边有几个关键词

线性表数据结构

顾名思义,线性表就是数据排成一条线型的结构,每个线性表上的数据,最多有前后俩个方向,其实除了数组,链表,队列,栈也是线性结构

非线性表

比如二叉树,堆,图 ,之所以叫非线性表是因为,数据之间并不是简单的前后关系

连续的内存空间和相同的数据类型

正因为这俩个特点,他才有了杀手锏,根据下标随机访问,但是有利就有弊,这俩个特性导致,数组插入和删除非常低效,需要做大量的搬运工作

数组是如何实现下表随机访问的

我们创建一个10个数据int类型的数组,int[] a =new int[10];在图中,计算机给数组分配了一块连续的内存空间1000-1039;其中内存块的首地址为base_address=1000;

我们知道,机器会给每个内存单元分配一个内存地址,机器通过地址来访问内存中的数据,当计算机随机访问数组中某个数据时,他会先计算出数据的内存地址,如下

a[i]_address = base_address + i * data_type_size

其中data_type_size是每个元素的大小,我们用的是int类型,所以是4个字节

低效的插入和删除

插入

假如数组长度为n,我们需要将一个数据,插入到k的位置,为了把k的位置让出来,我们需要把数组中k-n的数据统一向后挪一位

假如在数组的末尾插入数据,不需要挪动时间复杂度为O(1),假如在数组的头部插入数据,需要挪动n个时间复杂度为O(n),因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为(1+2+…n)/n=O(n)

删除

跟插入一样,如果要删除k位置的数据,需要把数组向前挪动一位,防止出现内存空洞

假如在数组的末尾删除数据,不需要挪动时间复杂度为O(1),假如在数组的头部插入数据,需要挪动n个时间复杂度为O(n),因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为(1+2+…n)/n=O(n)

如何提高删除效率

如果频繁删除,我们可以把删除的数据进行标记而不去真正删除,等到内存不够的时候,一起吧标记的删除,就会减少很多不必要的挪动,提高效率,这也是jvm垃圾回收标记清楚算法的实现

容器是否能替代数组

java中提供了List容器,那什么时候用数组,什么时候用容器呢

容器的优势 :1 使用简单 2 动态扩容

容器劣势:1 无法储存基本数据类型,int等,需要封装成integer

我总结一下,对于业务开发,直接使用容器就足够了,省时省力,如果需要将性能优化到极致,那可以使用数组