1、什么是数组？
数组是一种
线性表数据结构，它用一组连续的内存空间，来存储一组具有相同数据类型的数据。
-
线性表结构除数组外、栈、队列、链表也是线性表结构。非线性表有 堆、树、图等，在非线性表中数据之间不是简单的前后关系。
-
连续的内存空间和相同的数据类型：好处是随机访问。但是坏处是插入和删除需要搬移数据显得十分低效。
2、数组的查找时间复杂度。
img
数据适合查找操作：排序好的数组二分法查找时间复杂度为O（logn）; 数据支持随机访问，根据下标随机访问的时间复杂度为O（1）
3、低效的插入和删除
-
插入
-
数组的末尾插入 O（1）
-
数组的开头插入 O（n）
-
平均情况复杂度为： (1 + 2 + .....n) /n = O(n) 按照末尾向前插入的复杂度累计
-
如果数据无序，我们插入数据x时，可以将指定位置m的数据搬移到数组末尾，将数据x插入到位置m 此时的时间复杂度为O（1）
-
img
-
删除操作
-
删除末尾元素： O（1）
-
删除开头元素： O（n）
-
平均情况复杂度： O（n）
-
处理思路：当多个连续数据（a、b、c）需要删除时，先记录数据已经被删除，当数组内没有空间可以存储时，在触发一次真正的数据删除工作。大大减少了数据删除导致的搬移的工作
-
image
也是JVM的垃圾回收机制算法的核心思想。
网友评论