定义
数组是一种
数据结构。它用一组
，来存储一组具有
的数据。
特点
- 线性表
线性表就是数据排列像一条线一样的数据结构，每个线性表上的数据最多只有前和后两个方向。链表、队列、栈等也是线性表结构。
二叉树、堆、图等，是非线性表，因为数据之间并不是简单的前后关系
- 连续的内存空间和相同的数据类型
这两个限制，使数组有了随机访问的特性，计算机可以使用以下寻址公式，随机访问数组中的某个元素：
a[i]_address = base_address + i * data_type_size
base_address为数组的起始地址，data_type_size是每个元素占用的内存的大小，i是元素的索引。
- 低效的插入和删除
为了保证数组的连续性，在进行插入、删除操作的时候，需要做大量的数据迁移工作，因此效率会低一些。
举两个例子
插入：假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。如果数据插在末尾，这时的时间复杂度为 O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。平均情况时间复杂度为 (1+2+…n)/n=O(n)。
删除：跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
是否有优化的办法呢？答案是有的：
插入：如果数组中的元素，是没有任何规律的，数组只是被当作一个存储数据的集合，这种情况下，可以直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。
删除：可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作(这也是标记清除算法思想啊同志们)。
时间复杂度
随机查找：O(1)
插入：最好：O(1)，最坏：O(N)，平均O(N)
删除：最好：O(1)，最坏：O(N)，平均O(N)
容器ArrayList
Java语言中的容器，
java.util.ArrayList，底层的数据结构就是数组。封装了操作的细节，并且支持动态扩容，使用起来更加方便。不过需要注意一点的是，如果能够预知数据的数量，最好提前定义容器的大小，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。
尽管ArrayList用起来很方便，但是数组也并非没有用武之地：
1.数组无法存储基本类型数据，而装箱拆箱也会有一定的性能消耗，特别关注性能，选择数组
2.某些使用多维数据结构的情况下，使用数组看起来更直观，Object[][] array与ArrayList<ArrayList<object> > array
对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选
数组练习题目
| 两数之和 |
| 盛水最多的容器 |
| 移动零 |
| 爬楼梯 |
| 三数之和 |
| 删除排序数组中的重复项 |
| 旋转数组 |
| 合并两个有序数组 |
| 加一 |
网友评论