数组属于线性表的一种,线性表还包括了链表,栈和队列。
数组(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
网友评论