数组

Posted on Edited on
数组

数组：线性数据结构，连续存储空间（空间利用率问题），存储相同类型的数据
数组优点：下标随机访问O(1),查找复杂度不是O(1),有序使用二分查找时O(logn)
线性表：像一条线一样的结构，一个前驱一个后继。包括数组、链表、队列、栈
非线性表：不是简单的前后关系。包括树、图、堆

为什么很多编程语言中数组都从0开始编号

“下标”最确切的定义应该是“偏移（offset）”

  1. 从1开始编号，随机访问数组元素去顶地址多一次减法运算，对于CPU来说多了一次减法指令。
    • 从0开始第k个元素地址 a[k]_address = base_address + k * type_size
    • 从1开始第k个元素地址 a[k]_address = base_address + (k-1)*type_size
  2. C语言设计者用0开始计数数组下标，以后程序设计沿用此计数习惯，或者说为了在一定程度上减少C语言程序员学习Java的学习成本

如何实现随机访问

线性表+连续存储空间+相同数据类型 即数组

优化低效的“插入”和“删除”

  1. 无序数组可直接在末尾插入
  2. 无序数组在k位置插入，将k位移动末尾，新数据插入到k
  3. 删除数据，多次删除后再搬移数据

容器和数组

容器能否完全替代数组？
ArrayList最大的优势

  • 封装数组操作(封装数据搬移等)
  • 动态扩容（JAVA ArrayList自动扩容为1.5倍）

Java ArrayList无法存储int、long基本类型,需要封装为Integer、Long类，Autoboxing、Unboxing有一定的性能消耗，所以特别关注性能或希望使用基本类型，就用数组
如果数据大小已知，且数据操作简单，用不到ArrayList提供的大部分方法，直接使用数组。

如何选择？
业务开发，接受丢失一丢丢性能，直接使用容器，省事省力
底层开发，如网络框架，使用数组