数据结构--数组

定义

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

这里边有几个关键词

线性表数据结构

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

非线性表

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

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

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

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

我们创建一个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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!