之前1和2都是静态数组，我们创造动态数组
package com.company;
/**
* @program: Array
* @description: 数组
* @author: Gu
* @create: 2019-04-10 22:03
**/
public class Array<E> {
private E[] data;
private int size;
//初始化
public Array(int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
//无参构造函数默认最大容量为10
public Array() {
this(10);
}
//数组长度
public int length() {
return data.length;
}
//数组元素个数
public int getSize() {
return size;
}
//数组是否为空
public boolean isEmpty() {
return size == 0;
}
//向数组指定位置中添加元素
public void add(int index, E element) {
if (index >= data.length || index < 0) {
throw new IllegalArgumentException("[数组索引非法]");
}
if (size == data.length) {
//throw new IndexOutOfBoundsException("[数组已达到最大容量]");
//动态数组，数组容量到达最大值时，要扩容，我们暂定为扩容2倍（与java动态数组倍数不同）
int newCapacity = data.length * 2;
resize(newCapacity);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = element;
size++;
}
//向数组第一个索引添加元素
public void addFirst(E element) {
add(0, element);
}
//数组末尾添加元素
public void addLast(E element) {
add(size, element);
}
//根据index查找指定元素
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[数组索引非法]");
}
return data[index];
}
//查找数组是否包含指定元素
public boolean contains(E element) {
for (E value : data) {
if (value.equals(element)) {
return true;
}
}
return false;
}
//返回指定元素的索引
public int find(E element) {
for (int i = 0; i < size; i++) {
if (data[i].equals(element)) {
return i;
}
}
return -1;
}
//修改数组元素
public void set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[数组索引非法]");
}
data[index] = element;
}
//删除指定元素
public void delete(E element) {
int index = find(element);
if (index == -1) {
throw new IllegalArgumentException("[数组没有该元素]");
}
remove(index);
}
//根据索引删除元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[数组索引非法]");
}
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size = size - 1;
//删除内容后，我们希望向数组扩容一样，数组容量也会减少，我们假定size为1/2时，容量减半
if (size == data.length / 4 && data.length / 2 != 0) {
int newCapacity = data.length / 2;
resize(newCapacity);
}
return res;
}
private void resize(int capacity) {
E[] temp = (E[])new Object[capacity];
for (int i = 0; i < size; i++) {
temp[i] = data[i];
}
data = temp;
}
//删除第一个
public E removeFirst() {
return remove(0);
}
//删除最后一个
public E removeLast() {
return remove(size - 1);
}
//打印数组相关信息
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append(String.format("数组的size : %d, 数组的capacity : %d \n", size, data.length));
stringBuffer.append("[");
for (int i = 0; i < size; i++) {
stringBuffer.append(data[i]);
if (i == size - 1) {
stringBuffer.append("]");
break;
}
stringBuffer.append(",");
}
return stringBuffer.toString();
}
}
主要是增加数据和减少数据时，修改了数组容量。
测试类
package com.company;
public class Main {
public static void main(String[] args) {
//add()
Array<Integer> array = new Array<>(10);
for (int i = 0; i < 10; i++) {
array.add(i, i + 1);
}
System.out.println(array);
//[1,2,3,4,5,6,7,8,9,10]
//addFirst()
array.addFirst(0);
System.out.println(array);
//[0,1,2,3,4,5,6,7,8,9,10]
//removeFirst
array.removeFirst();
System.out.println(array);
}
}
这里使用均摊分析简单说明下扩容或者减半时的时间复杂度。
假如数组capacity = 4， size = 4， 这时我们增加数据时，会触发resize（）操作，使得capacity = 8，并且把老数组的数据复制到新数组。
此时我们统计下操作步骤：5次add操作 + 4次复制操作 = 9
我们均摊下时间复杂度： 9 / n = 2; 此时n = 4；是常数O（1）；
数组容量减半也是如此。
还有复杂度的震荡问题
我们可以看一张图：
复杂度的震荡
数组capacity = 10, size = 10，我们增加一个元素 ，此时capacity = 20。 接着 我们减去一个元素，capacity = 10，这些都符合逻辑。但是此时我们发现每做一次操作的时间复杂度为O（n）。
上述现象就是复杂度震荡问题。
产生问题的原因在于，每次size = capacity / 2 时，我们都会减半capacity。 现在我们采取新的策略，只有增加时才会扩容，减少size = capacity / 2 时我们不急于减半，只有当size = capacity / 4，我们才将capacity = capacity/2；修改后的代码如下
//根据索引删除元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[数组索引非法]");
}
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size = size - 1;
//删除内容后，我们希望向数组扩容一样，数组容量也会减少，我们假定size为1/2时，容量减半
if (size == data.length / 4 && data.length / 2 != 0) {
int newCapacity = data.length / 2;
E[] temp = (E[])new Object[newCapacity];
for (int i = 0; i < size - 1; i++) {
temp[i] = data[i];
}
data = temp;
}
return res;
}
