数组

1. 数组的定义：

数组（array）是一种线性表数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据。线性表就是数据排列成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向.`

2.数组的查询，删除，插入

由于数组它是连续的内存空间和相同的数据类型，有了这两个限制，才能让数组可以随机访问。这两个限制也让数组的很多操作变得低效，比如删除和插入操作，为了保证连续性需要做大量的数据搬移工作。为什么数组的插入和删除是低效的？

插入操作：   假如数组的长度为n，如果我们需要将一个数据插入到数组中的第k个位置，为了把第k个位置腾出来，需要把第k~n这部分的元素都顺序的往后挪一位，操作复杂。   如果在数组的末尾插入元素，那就不需要移动数据了，插入比较简单，单是如果在数组的头部插入元素就复杂了，需要把所有的数据都往后移动一位。   如果一个数组中的数据是有序的，那我们在某一个位置插入一个新的元素的时候就必须得按照上面的方法移动k之后的数据，但是数组中存储的数据如果没有任何规律，这时候，如果想要把某个元素插入到k位置，为了避免大规模的数据搬移，有个简单的办法就是：直接把k位置的数据搬到数组的最后面，把新元素放到第k个位置。

删除操作：   跟插入数据类似，如果我们要删除第k个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞。  在某些情况下，如果我们不要求数据必须是连续的，那么删除的时候可以不真删除，只是把这个元素标记为已删除，当组空间不够用的时候，在触发一次真正的删除，这样就大大减少了删除操作导致的搬移操作。  其实JVM的核心垃圾算法就是这个思想

3.数组的类型

Java数组是引用类型，放在堆空间。

4.数组定义方法

方式一

数组存储的数据类型[] 数组名字 = new 数组存储的数据类型[长度];

数组定义格式详解： 数组存储的数据类型： 创建的数组容器可以存储什么数据类型。 [] : 表示数组。 数组名字：为定义的数组起个变量名，满足标识符规范，可以使用名字操作数组。 new：关键字，创建数组使用的关键字。 数组存储的数据类型： 创建的数组容器可以存储什么数据类型。 [长度]：数组的长度，表示数组容器中可以存储多少个元素。 注意：数组有定长特性，长度一旦指定，不可更改。 和水杯道理相同，买了一个2升的水杯，总容量就是2升，不能多也不能少。

int[] arr = new int[3];

方式二

数据类型[] 数组名 = new 数据类型[]{元素1,元素2,元素3...}; int[] arr = new int[]{1，2，3，4，5};

方式三

数据类型[] 数组名 = {元素1,元素2,元素3...}; int[] arr = {1，2，3，4，5};

5.数组原理内存图

内存是计算机中的重要原件，临时存储区域，作用是运行程序。我们编写的程序是存放在硬盘中的，在硬盘中的程 序是不会运行的，必须放进内存中才能运行，运行完毕后会清空内存。 Java虚拟机要运行程序，必须要对内存进行空间的分配和管理。 Java虚拟机的内存划分 为了提高运算效率，就对空间进行了不同区域的划分，因为每一片区域都有特定的处理数据方式和内存管理方式。 JVM的内存划分：

区域名称作用寄存器给CPU使用，和我们开发无关。本地方法栈JVM在使用操作系统功能的时候使用，和我们开发无关。方法区存储可以运行的class文件。堆内存存储对象或者数组，new来创建的，都存储在堆内存。方法栈方法运行时使用的内存，比如main方法运行，进入方法栈中执行。

6.数组在内存中的存储

一个数组内存图

public static void main(String[] args) { int[] arr = new int[3]; System.out.println(arr);//[I@5f150435 }

以上方法执行，输出的结果是[I@5f150435，这个是什么呢？是数组在内存中的地址。new出来的内容，都是在堆 内存中存储的，而方法中的变量arr保存的是数组的地址。 输出arr[0]，就会输出arr保存的内存地址中数组中0索引上的元素 两个数组内存图

public static void main(String[] args) { int[] arr = new int[3]; int[] arr2 = new int[2]; System.out.println(arr); System.out.println(arr2); }

两个变量指向一个数组

public static void main(String[] args) { // 定义数组，存储3个元素 int[] arr = new int[3]; //数组索引进行赋值 arr[0] = 5; arr[1] = 6; arr[2] = 7; //输出3个索引上的元素值 System.out.println(arr[0]); System.out.println(arr[1]); System.out.println(arr[2]); //定义数组变量arr2，将arr的地址赋值给arr2 int[] arr2 = arr; arr2[1] = 9; System.out.println(arr[1]); }

7.数组的常见操作

数组越界异常 创建数组，赋值3个元素，数组的索引就是0，1，2，没有3索引，因此我们不能访问数组中不存在的索引，程序运 行后，将会抛出 ArrayIndexOutOfBoundsException 数组越界异常。在开发中，数组的越界异常是不能出现的，一 旦出现了，就必须要修改我们编写的代码。 数组空指针异常

public static void main(String[] args) { int[] arr = {1,2,3}; arr = null; System.out.println(arr[0]); ｝

arr = null 这行代码，意味着变量arr将不会在保存数组的内存地址，也就不允许再操作数组了，因此运行的时候 会抛出 NullPointerException 空指针异常。在开发中，数组的越界异常是不能出现的，一旦出现了，就必须要修 改我们编写的代码。

8.数组遍历

数组遍历： 就是将数组中的每个元素分别获取出来，就是遍历。遍历也是数组操作中的基石。 方式一： for循环遍历 方式二： 增强for循环 数组获取最大值元素 **最大值获取：**从数组的所有元素中找出最大值。 实现思路： 定义变量，保存数组0索引上的元素 遍历数组，获取出数组中的每个元素 将遍历到的元素和保存数组0索引上值的变量进行比较 如果数组元素的值大于了变量的值，变量记录住新的值 数组循环遍历结束，变量保存的就是数组中的最大值

public static void main(String[] args) { int[] arr = { 5, 15, 2000, 10000, 100, 4000 }; //定义变量，保存数组中0索引的元素 int max = arr[0]; //遍历数组，取出每个元素 for (int i = 0; i < arr.length; i++) { //遍历到的元素和变量max比较 //如果数组元素大于max if (arr[i] > max) { //max记录住大值 max = arr[i]; } } System.out.println("数组最大值是： " + max); }

数组反转 数组的反转： 数组中的元素颠倒顺序，例如原始数组为1,2,3,4,5，反转后的数组为5,4,3,2,1 **实现思想：**数组最远端的元素互换位置。 实现反转，就需要将数组最远端元素位置交换 定义两个变量，保存数组的最小索引和最大索引 两个索引上的元素交换位置 最小索引++，最大索引–，再次交换位置 最小索引超过了最大索引，数组反转操作结束

public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; /* 循环中定义变量min=0最小索引 max=arr.length‐1最大索引 min++,max‐ */ for (int min = 0, max = arr.length ‐ 1; min <= max; min++, max‐‐) { //利用第三方变量完成数组中的元素交换 int temp = arr[min]; arr[min] = arr[max]; arr[max] = temp; } // 反转后，遍历数组 for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } }

9.数组作为方法参数和返回值

数组作为方法参数 数组作为方法参数传递，传递的参数是数组内存的地址。

public static void main(String[] args) { int[] arr = { 1, 3, 5, 7, 9 }; //调用方法，传递数组 printArray(arr); } /* 创建方法，方法接收数组类型的参数 进行数组的遍历 */ public static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } }

10.数组作为方法返回值

数组作为方法的返回值，返回的是数组的内存地址

public static void main(String[] args) { //调用方法，接收数组的返回值 //接收到的是数组的内存地址 int[] arr = getArray(); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } /*创建方法，返回值是数组类型 return返回数组的地址 */ public static int[] getArray() { int[] arr = { 1, 3, 5, 7, 9 }; //返回数组的地址，返回到调用者 return arr; }

方法的参数类型区别 总结: 方法的参数为基本类型时,传递的是数据值. 方法的参数为引用类型时,传递的是地址值.

10.数组查询的时间复杂度

按照数组下标访问为O(1) 数组访问是随机访问，时间复杂度为O(1)，因为int数组创建时会初始化一个内存地址(eg:array的地址Ox1110)，想要查找数组array[2]，直接进行内存地址计算 内存地址 + n * 数组类型字节数(int型为4字节，long类型为8字节) 后根据计算的地址直接访问。按照数组中存储的元素访问 最坏时间复杂度为O(n)。 由于我们只保存了索引为 0 处的内存地址，因此在查找元素时，只需从数组开头逐步向后查找就可以了。如果数组中的某个元素为目标元素，则停止查找；否则继续搜索直到到达数组的末尾。最坏情况–----末尾是目标元素或者数组中不包含目标元素，时间复杂度O(n)。删除,插入元素  如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。  但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是O(n)。因为在每个位置插入数据的概率是一样的所以时间复杂度平均为O(n/2)，省略常数1/2，即O(n)。 删除同理。

11.数组存储机制

对于数组的定义，初始化时用new与不用new 没区别 ，只是两种方式罢了，因为数组是引用数据类型，建立对象时，无论用不用new，数组实体都是放在 堆内存中，引用变量放在栈内存。main函数放在栈空间。数组的引用变量存放在栈中，其元素则存放在堆内存中。 以 int 型数组为例，也可以发现，基本数据类型在堆中也会出现。 int[] array=new int[]{1,2}; 由于new了一个对象，所以new int[]{1,2}这个对象是存储在堆中的，也就是说1,2这两个基本数据类型是存储在堆中。

12.ArrayList动态数组

ArrayList test = new ArrayList();

java中的ArrayList相当与一个动态数组，支持扩容。它可以把很多数组操作的细节封装起来，比如数组的插入和删除。

数组在定义的时候，因为需要给它分配连续的内存空间，需要预先指定其大小，当存放的数据大于其大小的时候，我们需要从新分配一块更大的空间，把原来的复制过去在插入新的元素。

ArrayList中，当空间不够用的时候，它会自动扩容为原来的1.5倍的大小。

因为扩容设计到内存的申请和数据的搬移，这是比较耗时的，所以，如果事先能确定数据的大小，做好在创建ArrayList的时候指定其大小

虽然ArrayList比数组好用，不过有些时候使用数组会更好一些。 1）因为ArrayList无法存储基本类型，int long等需要封装成Integer,Long类，而自动装箱和拆箱的操作也会有一定的性能消耗，所以如果关注性能或者想用基本类型就选用数组 2）如果数据的大小已经知道，并且对数据的操作简单，可以直接使用数组 3）当使用多为数组的时候，用数组表示起来更加直观比如int[][]arr；而用容器的话则需要这样定义ArrayList arr。 在开发中，一般情况下直接使用ArrayList就可以，如果是偏底层的开发比如网络框架开发等需要更高的性能，使用数组更合适。

Object类型：

是所有引用类型的父类，在引用类型的顶端。 它的引用变量可以指向任何类型的一个对象。

面试题：怎么使用数组存一些类型不同的数据

用Object定义一个数组 Object[] arr = new Object[3]; arr[0] = "aaa"; arr[1] = new int[3]; arr[2] = new Scanner(System.in);

为什么ArryList无法存储基本数据类型，

因为引用对象，实际内容都存放在堆内或方法区里面，

但是基本数据类型是在栈内存上分配空间的，栈上的数据随时会被收回。