数据结构之数组
数组属于线性表的一种，线性表还包括了链表，栈和队列。
数组（Array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。
image.png
数组下标从零开始(Why)
存储原理
数组用一组连续的内存空间来存储一组具有相同类型的数据
image.png
(模拟内存存储)
灰色格子：被使用的内存
橙色格子：空闲的内存
红色格子：数组占用的内存
数组可以根据下标随机访问数据
比如一个整型数据 int[] 长度为5
image.png
假设首地址是：1000
int是4字节（32位）,实际内存存储是位
随机元素寻址
a[i]_address=a[0]_address+i*4
该公式解释了三个方面
1）连续性分配
2）相同的类型
3）下标从0开始
操作
读取元素，根据下标读取元素的方式叫作随机读取int n=nums[2]
更新元素nums[3]= 10;
注意不要数组越界，读取和更新都可以随机访问，时间复杂度为O(1)
插入元素，有三种情况：
尾部插入
在数据的实际元素数量小于数组长度的情况下：
直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作
image.png
a[6]=10
中间插入
在数据的实际元素数量小于数组长度的情况下：
由于数组的每一个元素都有其固定下标，所以首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。
image.png
超范围插入
假如现在有一个数组，已经装满了元素，这时还想插入一个新元素，或者插入位置是越界的
这时就要对原数组进行扩容：可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统统复制
过去，这样就实现了数组的扩容。
image.png
int[] numsNew=new int[nums.length*2];
System.arraycopy(nums,0,numsNew,0,nums.length);
// 原数组就丢掉了，资源浪费
nums=numsNew;
删除元素，数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。
for(int i=p;i<nums.length;i++){
nums[i-1]=nums[i];
}
完整的代码：
public class ArrayDemo1 {
int[] nums = new int[8];
public ArrayDemo1() {
nums[0] = 3;
nums[1] = 1;
nums[2] = 2;
nums[3] = 5;
nums[4] = 4;
nums[5] = 9;
}
public int get(int i) {
return nums[i];
}
public void update(int i, int n) {
nums[i] = n;
}
public void insertTail(int n) {
nums[6] = n;
}
public void insertMiddle(int p, int n) {
for (int i = nums.length-1; i >= p-1; i--) {
//能取得值
if (nums[i] != 0) {
nums[i+1]=nums[i];
}
}
nums[p-1]=n;
}
/**
* 旧数组复制到新数组
*/
public void resize(){
int[] numsNew=new int[nums.length*2];
System.arraycopy(nums,0,numsNew,0,nums.length);
nums=numsNew;
}
public void insertOutOfBounds(int p,int n){
//数组扩容
resize();
nums[p-1]=n;
}
public void deleteMiddle(int p){
for(int i=p;i<nums.length;i++){
nums[i-1]=nums[i];
}
}
public void display() {
for (int n : nums) {
System.out.println(n);
}
}
public void display2() {
for (int i = nums.length - 1; i >= 0; i--) {
System.out.println(nums[i]);
}
}
public static void main(String[] args) {
ArrayDemo1 demo1 = new ArrayDemo1();
demo1.deleteMiddle(3);
demo1.display();
}
}
时间复杂度
读取和更新都是随机访问，所以是O(1)。
插入数组扩容的时间复杂度是O(n)，插入并移动元素的时间复杂度也是O(n)，综合起来插入操作的时间复杂度是O(n)。
删除操作，只涉及元素的移动，时间复杂度也是O(n)。
优缺点
优点：
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素
缺点：
插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。 (ArrayList LinkedList )
申请的空间必须是连续的，也就是说即使有空间也可能因为没有足够的连续空间而创建失败
如果超出范围，需要重新申请内存进行存储，原空间就浪费了
应用
数组是基础的数据结构，应用太广泛了，ArrayList、Redis、消息队列等等。
数据结构和算法的可视化网站：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
