数组学习笔记

数组

「数组(Array)」是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

1. 线性表 (Linear List)
   数据排成像一条线一样的结构。每个线性表上的数据最多只有前后两个方向。除数组外，还有链表、队列、栈等都是线性表结构

与之相对立的概念就是非线性表，如二叉树、堆、图等。因为它们并非简单的前后关系。

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

• 优点:带来一个特性：「随机访问」-- 指定下标访问迅速，时间复杂度为 O(1)
• 缺点:除指定下标访问外的操作低效，在进行插入，删除等操作时，为保证连续性，需要做大量的数据搬移工作。

「随机访问」原理

一组长度为 10 的 int 数组，int a[] = new int[10] 在内存中申请了一块连续的空间，1000~1039 ，其中内存块的首地址为 base_address = 1000。

计算机会给每个内存单元分配一个地址，然后通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，会首先通过寻址公式:

a[i]_address = base_address + i * data_type_size

计算出该元素存储的内存地址，data_type_size = 4 (Java 中 int 的占用 4 字节 Java 基础数据类型占用字节数)

数组和链表的区别

• 数组: (有序、二分查找)最好时间复杂度是 O(logn)，最坏时复杂度 O(n)，数组支持随机访问，根据下标随机访问的时复杂度是 O(1)
• 链表: 插入、删除的时复杂度为 O(1)，查找的时复杂度 O(n)

数组的「插入」与「删除」操作

• 插入: 假设一个长度为 n 的数组，现在将一个数据插入到 k(0<=k<n) 位置，为保证数据在内存中的连续性，就需要将原先 k ~ n 的位置的数据向后挪一位，再将新数据插入。
  最好时间复杂度: O(1)，最坏时间复杂度 O(n)，平均时间复杂度 O(n)。
  注: 如果数据是无序的，可以将 k 位置的数据直接放到最后再在 k 位置插入新数据，时间复杂度降为 O(1) --- 快速排序思想

• 删除: 同样一个数组，删除 k 位置的数据，为保证数据在内存中的连续性，需要将 k 之后的数据向前挪动，时间复杂度同上。
  因为每次删除操作都会引起一次数据搬移，所以在不追求数据连续性的情况下，可以将多次删除操作集中在一次执行，先记录下已删除的数据，并不执行删除，当数组空间不足时，触发执行一次删除操作，将标记的数据删除 --- JVM 标记清除回收算法思想
  

Java基础数据类型占用字节数

类型	存储需求	bit	取值范围	备注
int	4字节	4*8	-2147483648~2147483647	即 (-2)的31次方 ~ (2的31次方) - 1
short	2字节	2*8	32768~32767	即 (-2)的15次方 ~ (2的15次方) - 1
long	8字节	8*8		即 (-2)的63次方 ~ (2的63次方) - 1
byte	1字节	1*8	-128~127	即 (-2)的7次方 ~ (2的7次方) - 1
float	4字节	4*8		float 类型的数值有一个后缀 F（例如：3.14F）
double	8字节	8*8		没有后缀 F 的浮点数值（例如：3.14）默认为 double
boolean	1字节	1*8	true、false
char	2字节	2*8		Java中，只要是字符，不管是数字还是英文还是汉字，都占两个字节。