基础数据结构-数组 - 图1

1. 数组

1.1 数组是什么

数组是一组数据类型相同的数据元素集合，数组的大小声明后不可改变，数组中的数据元素存储空间在内存中的表现形式是连续的。
基础数据结构-数组 - 图2

1.2 数组有哪些优缺点

得益于数组是在内存空间中连续存储的，所以数组具有随机读取的特性。

优点：

查找速度快：数组查找数据的时间复杂度是O(1)，因为数组是连续存储的所以直接通过数组下标就能够找到指定位置的元素。一维数组大致的寻址公式为：空间地址+下标索引*类型大小

public class HelloWorld{
    public static void main(String[]args){
        int[]arr = new int[5];
        /*
            假设arr[0]的位置是10001,那么根据寻址公式可知：
            arr[0]===>10001+0+typesize
            arr[1]===>10001+1+typesize
            arr[2]===>10001+2+typesize
            arr[3]===>10001+3+typesize
            arr[4]===>10001+4+typesize
        */
    }
}

缺点：

修改、删除元素的速度比较慢：原因在于数组如果要添加一个元素那么这个坐标之后包括插入位置坐标元素都需要依次往后移，如果是删除一个元素那么就是删除下标后边的元素往前挪动。删除和修改数组的时间复杂度为O(n)。

1.3 数组有哪些类型

一维数组 ```java public class OneArray{

public static void main(String[]args){

 //声明一个一维数组
 int[]arr = new arr[10];
 //为一维数组赋值
 int[0] = 1;
 int[1] = 2;
 int[2] = 3;

}


2. 多维数组
```java
public class TwoArray{
    public static void main(String[]args){
        //声明一个二维数组
        int[][]arr = new int[5][10];
        //为二维数组赋值
        int[0][0] = 1;
        int[0][1] = 2;
        int[1][0] = 3;
        int[1][1] = 4;
    }
}

1.3 数组的基本操作

package com.muzili.array;
/**
 *
 * @author: muzili(李敷斌)
 * @date: 2021/6/29
 * @version: v0.0.1
 * @description: 动态数组 类ArrayList实现
 */
public class DynamicArray<T> {
    private int size = 10;
    private T[] arr;
    public DynamicArray(){
        arr = (T[]) new Object[size];
    }
    public DynamicArray(int size){
        if (size==0){
            return;
        }
        arr = (T[]) new Object[size];
    }
    public int getSize() {
        return size;
    }
    public T[] getArr() {
        return arr;
    }
    /**
     * 向指定位置插入一个元素
     * @param loc
     * @param ele
     */
    public void add(Integer loc,T ele){
        if (loc < size){
            //从最后一个元素开始移动
            for (int i = size - 1; i > loc; i--) {
                arr[i] = arr[i-1];
            }
            arr[loc] = ele;
            return;
        }
        //如果 最大maxIndex自加后大于size则需要扩容
        expansion();
        add(loc, ele);
    }
    /**
     * 数组扩容
     */
    private void expansion(){
        //扩容2倍
        int tmpSize = size * 2;
        T[]tmpArr = (T[]) new Object[tmpSize];
        for (int i = 0; i < arr.length; i++) {
            tmpArr[i] = arr[i];
        }
        arr = tmpArr;
        size = tmpSize;
    }
    /**
     * 删除自定位置的元素
     * @param loc
     */
    public void remove(int loc){
        if (loc >= size){
            return;
        }
        for (int i = loc; i < size-1; i++) {
            arr[i] = arr[i+1];
        }
        arr[size-1] = null;
    }
    /**
     * 获取原始
     * @param loc
     * @return
     */
    public T get(int loc){
        if (loc >= size){
            return null;
        }
        return arr[loc];
    }
    public static void main(String[] args) {
        DynamicArray<String> strArr = new DynamicArray<String>(10);
        strArr.add(0,"1");
        strArr.add(0,"2");
        strArr.add(2,"3");
        strArr.add(3,"4");
        strArr.add(2,"4");
        strArr.add(12,"5");
        Object[] arr = strArr.getArr();
        for (int i = 0; i < arr.length; i++) {
            System.out.println("元素下标["+i+"]，元素值="+arr[i]);
        }
        //删除下标为1的元素
        strArr.remove(1);
        System.out.println("==========================================");
        arr = strArr.getArr();
        for (int i = 0; i < arr.length; i++) {
            System.out.println("元素下标["+i+"]，元素值="+arr[i]);
        }
    }
}

2. Java中的内存

基础数据结构-数组 - 图4

2.1 堆内存

在Java中，通过new创建的对象都是存放在堆内存中的，堆内存由GC垃圾回收器管理，当一个对象不再被引用那么它就会被垃圾回收器回收。堆内存是灵活的，它实现了内存的按需分配，而且它能够自动释放内存。

2.2 栈内存

在Java中，栈内存用于存储基本数据类型的变量、指令代码、常量以及对象引用（对象句柄），栈内存由编译器进行管理，它的生命周期是比较短的，它可能随着一个方法调用的结束内存就被立即释放，正是由于这一特性，所以栈内存的效率比较高，仅次于寄存器。

2.3 面试题

分析以下代码中，声明的变量是属于栈内存还是堆内存？

String str1 = "abc";