线性表(每个线性表上的数据最多只有前和后两个方向):数组,链表,队列,栈 非线性表(数据之间并不是简单的前后关系):二叉树,堆,图
数组的概念
数组( Array )是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
数组的特点
连续的内存空间和相同类型的数据
数组的优点
随机访问:利用寻址公式对元素进行访问:
a[i]_address = base_address + i * data_type_size数组的查找操作时间复杂度不是O(1),即便是排好的数组,用二分查找,时间复杂度也是O(logn);正确的说法
数组支持随机访问,根据下标随机访问的时间复杂度为O(1)
数组的缺点
低效的插入和删除
- 插入:最好O(1),最坏O(n)
数组若无序,插入新的元素时,可以将第 K 个位置元素移动到数组末尾,把新的元素,插入到第 k 个位置,此处复杂度为O(1)
- 删除:最好O(1),最坏O(n)
多次删除集中在一起,提高删除效率,记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即 JVM 标记清除垃圾回收算法。
标记 - 清除算法
标记 - 清除算法在垃圾收集时会先标记出需要回收的对象,标记完成后统一回收所有被标记的对象。清除之后会产生大量不连续的内存碎片。标记 - 整理垃圾回收算法在标记完成之后让所有存活的对象都向一端移动,然后直接清理掉边界以外的内存
访问越界
数组越界在 C 语言中是一种未决行为,并没有规定数组访问越界时编译器应该如何处理。因为,访问数组的本质就是访问一段连续内存,只要数组通过偏移计算得到的内存地址是可用的,那么程序就可能不会报任何错误
数组和容器
容器能否完全替代数组(ArrayList,vector)
相比于数组, java 中的 ArrayList 封装了数组的很多细节(插入删除时数据的迁移工作),并支持动态扩容。一旦超过存储容量,扩容时比较耗时,因为涉及到内存申请和数据搬移。
Java ArrayList 无法存储基本类型,比如 int 、 long ,需要封装为 Integer 、 Long 类,而Autoboxing 、 Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。
如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。
当要表示多维数组时,用数组往往会更加直观。比如
Object[][]array ;而用容器的话则需要这样定义:ArrayList<ArrayList > array。
总结
对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发,比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选
数组的下标
下标从内存来看,就是偏移量.如果用1开始计数.array[k]的内存地址为:a[k]_address = base_address + (k-1)*type_size;可以看出,多了一个减法运算,数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始号,而不是从 1开始。(python下标可以为任何整数)
Comments