数组
数组是一种线性数据结构，用连续的存储空间存储相同类型数据。
- 线性表:数组、链表、队列、栈 非线性表:树 图
- 连续的内存空间、相同的数据，所以数组可以随机访问，但对数组进行删除插入，为了保证数组的连续性，就要做大量的数据搬移工作
优点：数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。
原因：计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。而数组是连续的存储空间，当计算机需要随机访问数组中的某个元素时，可通过内测地址和数据类型的大学计算出该元素存储的内存地址a[i]_address = base_address + i * data_type_size
缺点：插入删除需要诺动元素，时间复杂度O(n) 优化方式：
- 数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素， 插入到第k个位置，此处复杂度为O(1)
- 多次删除集中在一起，提高删除效率。记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没 有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。
ArrayList底层也是通过数据存储，但支持动态扩容（重新申请一个空间，全部复制过去）。