动态数组
数组特点
- 只能存储同一种数据类型的数据。
- 一旦初始化，长度固定。
- 数组中的元素与元素之间的内存地址是连续的
数组的优点是：随机访问。
数组最好应用于索引有语意的情况下。
动态数组： Java 中的数组是静态数组，创建的时候就决定了数组的大小，所以我们需要封装自己的数组类，数组的大小可以动态变化。
数据结构
数据结构的本质跟数据库一样，也是储存数据，然后再对数据进行高效的增删改查操作，只不过数据结构把数据存储在内存中。学习数据结构，就是要了解数据是通过怎样的方式来进行存储以及增删改查操作。
数组的容量跟大小
数组的容量 (capacity) 是数组最大可以存储数据的大小，实际存储的大小 (size) 小于等于容量。
简单的时间复杂度分析
常见的时间复杂度有如下几种：
O(1) ，O(n) ， O(logn) ， O(nlogn) ， O(n^2)
大写的 O (简称大O) 描述的是算法的运行时间和输入数据之间的关系。
比如有这样一个方法：
public static int sum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
这个方法的时间复杂度为 O(n) ，为什么呢？
首先要给 n 一个定义，在这个算法中， n 是 nums 中元素的个数。由定义可知，该算法运行的时间与 nums 中的元素个数成线性关系。
该算法实际时间时间应该如以下公式：
T = c1*n +c2。上述算法每次运行加法运算时都需要取出元素，然后运行加法运算，最后再返回结果，这过程需要的时间可以比作为 c1 ，sum 的初始化时间可以算作 c2，。因为 c1 和 c2 实际上是常数，而且很难确定(这跟 CPU 的运作有关)，因此可以忽略。实际上，大 O 的意思是渐进时间复杂度，描述的是 n 趋近于无穷时，算法之间的时间快慢。上述时间公式中，当 n 趋近于无穷的情况时，小的项就可以忽略了，n 越大，越能体现一个算法的快慢。
因此，以下时间公式对应的时间复杂度如下:
T = 2n +2 ， O(n)
T = 2000n +10000 ， O(n)
T = 1n^2 +10 ， O(n^2)
T = 2n^2 +10n +10 ， O(n^2)
注意：如果一个算法的复杂度为 O(n^2) ，另一个算法为 O(n) ，并不能说明在任何输入的情况下，O(n^2) 的时间要大于 O(n)的时间，具体要看前面的常数。在实际运用中，不一定非要选择一个 O(n) 的算法而抛弃 O(n^2) 的算法，要根据 n 的数量来决定。
动态数组代码实现
public class Array<E> {
// 类内维护的数组
private E[] data;
// 数组内实际存储元素的个数
private int size;
/**
* 构造函数，默认数组的容量为10
*/
public Array() {
this(10);
}
/**
* 构造函数，传入数组的容量
*/
public Array(int capacity) {
//创建带容量的 Object 数组并强转为E类型的数组
data = (E[]) new Object[capacity];
}
/**
* 构造函数，传入一个静态数组
*/
public Array(E[] arr) {
//创建 Object 数组并强转为E类型的数组，长度为传入的静态数组的大小
data = (E[]) new Object[arr.length];
// 把静态数组的值全部复制到 data 数组
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
// 目前 data 数组的长度为静态数组的大小
size = arr.length;
}
/**
* 在 index 索引位置插入新元素 e ,，时间复杂度O(n)
*/
public void add(int index, E e) {
// 为保证数组的连续性，紧密相联，即索引之间不能有空元素
// 如果索引小于 0 或 索引大于最后一个元素的下一个元素
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index>= 0 and index <= size.");
}
// 如果此时数组已满，则扩容为2倍
if (size == data.length) {
resize(data.length * 2);
}
// index 及后面的元素都向后移动一个位置,index位置的元素会复制到index+1的位置
for (int i = size - 1; i >= index; i--) {
// 后一个元素等于前一个元素
data[i + 1] = data[i];
}
//在 index 的位置把之前的值覆盖掉，也就是添加了新元素了
data[index] = e;
// 维护 size ，此时添加了元素，应当加1
size++;
}
/**
* 将数组空间的容量变成 newCapacity 的大小，均摊时间复杂度O(1)
*/
private void resize(int newCapacity) {
// 创建一个 newCapacity 容量的数组对象
E[] newData = (E[]) new Object[newCapacity];
// 把以前的数据复制到新对象中
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
// 将当前数组对象指向新的数组对象
this.data = newData;
}
/**
* 向所有元素后添加一个元素，时间复杂度O(1)
*/
public void addLast(E e) {
add(size, e);
}
/**
* 向所有元素前添加一个元素，时间复杂度O(n)
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 删除指定 index 索引对应的元素，并返回删除的元素，时间复杂度O(n)
*/
public E remove(int index) {
// 注意这个等于的情况
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Demove failed. Require index>= 0 and index < size.");
}
// 先拿到需要返回的元素
E res = data[index];
// index 后面的元素都向前移动一个位置
for (int i = index + 1; i < size; i++) {
// 前一个元素等于后一个元素
data[i - 1] = data[i];
}
// 维护 size ，此时删除了元素，应当减1
size--;
// 把最后没用到的对象置null，利于GC释放内存
data[size] = null;
// 当前存储的元素的大小为容量的4分1时，缩容为原来的一半
// 注意，不能当前存储的元素的大小为容量的2分1时来缩容，因为扩容的时候是扩容2倍，
// 在边界反复添加和删除元素时，会出现复杂度震荡
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
// 返回当前删除的元素
return res;
}
/**
* 删除最后一个元素，并返回删除的元素，时间复杂度O(1)
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 删除第一个元素，并返回删除的元素，时间复杂度O(n)
*/
public E removeFirst() {
return remove(0);
}
/**
* 如果存在元素e ，则删除
*/
public void removeElement(E e) {
// 找到元素 e 对应的索引
int index = find(e);
// 如果索引存在，则删除
if (index != -1) {
remove(index);
}
}
/**
* 修改 index 索引位置的元素为 e ，时间复杂度O(1)
*/
public void set(int index, E e) {
// 注意这个等于的情况
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Index is illegal.");
}
// 直接修改对应索引元素的值
data[index] = e;
}
/**
* 获取 index 索引位置的元素，时间复杂度O(1)
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
/**
* 查找数组中是否有元素e，时间复杂度O(n)
*/
public boolean contain(E e) {
// 不能用这种方式遍历，因为我们每次删除元素时都调用了如下代码 data[size] = null，所以会出现空指针问题
/* for (E datum : data) {
if (datum.equals(e)) {
return true;
}
}*/
for (int i = 0; i < size; i++) {
// 注意这里用的是 equals，不能用 ==
if (data[i].equals(e)) {
return true;
}
}
return false;
}
/**
* 查找数组中对应的元素的索引，如果元素不存在，则返回索引为 -1，时间复杂度O(n)
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
/**
* 返回最后一个元素，时间复杂度O(1)
*/
public E getLast() {
return get(size - 1);
}
/**
* 返回第一个元素，时间复杂度O(1)
*/
public E getFirst() {
return get(0);
}
/**
* 获取数组中元素的个数
*/
public int getSize() {
return size;
}
/**
* 获取数组的容量
*/
public int getCapacity() {
return data.length;
}
/**
* 数组是否为空
*/
public boolean isEmpty() {
return size == 0;
}
// 交换对应元素索引的值
public void swap(int i, int j) {
// 判断索引越界的情况
if (i < 0 || i >= size || j < 0 || j >= size) {
throw new IllegalArgumentException("Index is illegal.");
}
E t = data[i];
data[i] = data[j];
data[j] = t;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d , capacity = %d\n", getSize(), getCapacity()));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(", ");
}
}
res.append(']');
return res.toString();
}
}
动态数组的时间复杂度分析
添加操作
addLast(e) ，O(1) ，跟数组里面的元素个数 n 无关。
addFirst(e) ，O(n) ，跟数组里面的元素个数 n 有关。
add(index ,e) ，O(2/n) = O(n) ，跟数组里面的元素个数 n 有关，可以想像成数组里面的元素需要移动 2/n 次，常数忽略。
因此，添加操作的时间复杂度为 O(n) 级别的，取最糟糕的情况。
删除操作
removeLast(e) ，O(1) ，跟数组里面的元素个数 n 无关。
removeFirst(e) ，O(n) ，跟数组里面的元素个数 n 有关。
remove(index ,e) ，O(2/n) = O(n) ，跟数组里面的元素个数 n 有关，可以想像成数组里面的元素需要移动 2/n 次，常数忽略。
因此，删除操作的时间复杂度为 O(n) 级别的，取最糟糕的情况。
修改操作
set(index ,e) ，O(1) ，跟数组里面的元素个数 n 无关，(即支持随机访问)
查询操作
get(index) ，O(1) ，跟数组里面的元素个数 n 无关。
contain(e) ，O(n) ，跟数组里面的元素个数 n 有关。
find(e) ，O(n) ，跟数组里面的元素个数 n 有关。
因此，查询操作在已知索引情况下的时间复杂度为 O(1) 级别，否则为 O(n) 级别 。
resize 方法
这里要用均摊的方式来计算，计算均摊时间复杂度，不取最坏的情况，这样才比较有意义。
分析如下：
假设当前
capacity = 8，并且每次添加操作都使用addLast，则需要9次addLast操作才触发一次resize方法，再加上8次的拷贝值操作，总共进行了17次基本操作(给一个空间赋值算一次)。因此，平均每次addLast操作，进行了2次基本操作。现在假设
capacity = n,则n+1次addLast操作才会触发一次resize方法，总共进行2n+1次基本操作，所以平均每次addLast操作，进行了2次基本操作。这样均摊来计算，时间复杂度为 O(1) 级别的。
总结：在索引已知的情况下，查、改操作为 O(1) 级别的，增、删操作则跟索引无关，为 O(n) 级别的。所以就像开头所说的，数组最好在已知索引的情况下使用，这样便可以快速地进行查、改操作。