数组

# 如何实现随机访问

线性表数据结构
- 顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
随机访问特性
- 数组可以实现根据下标随机访问数组元素
- 数组-----连续的内存空间和相同类型的数据

# 低效的插入和删除

数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效.

插入
- 数组是有序的时候，需要在第k个位置插入数据，需要将k后面的数据全部后移。
- 高效：但是当数组时无序的，没有规律的，需要在第k个位置插入数据时，可以使用搬移操作
  - 即，将原来第k个位置的元素放到数组最后，将要插入的元素，放到k位置。如下图所示。
删除
- 如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
- 高效：不直接删除元素，而是将要删除的元素进行标记，当达到一定量后，一块删除，这样可以避免多次数据的搬移。----JVM 标记清除垃圾回收算法的核心思想

# 数组越界---c语言

java语言在数组越界时，会抛出异常java.lang.ArrayIndexOutOfBoundsException

下面这组代码会无限次输出 helloworld，而不是三次。

原因是 a[3]这个内存地址，存放的是 i=0,所以i会一直重复从0到2。

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

内存问题
- 内存用栈存储，存储结构如下所示
- 所以在访问a[3]时，i=0，无限循环

# 容器与数组

ArrayList---优势
- 可以将很多数组操作的细节封装起来，前面提到的数组插入、删除数据时需要搬移其他数据。
- 支持动态扩容。每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小。我们不需要关心底层的扩容逻辑。
ArrayList---申请
- 因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。
数组与ArrayList
- Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组
- 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
- 当要表示多维数组时，用数组往往会更加直观。比如Object[][] array；而用容器的话则需要这样定义：ArrayList <ArrayList <object>> array
总结：

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。

但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

# LeetCode练习题

实现一个支持动态扩容的数组
实现一个大小固定的有序数组，支持动态增删改操作
实现两个有序数组合并为一个有序数组

#知识 #算法

上次更新: 2023 07 3

← 时(空)间复杂度链表→