数组是最为常见也是最简单的数据结构之一，本文通过2次封装来一步一步实现数组的功能，来了解与熟悉这个最基本的数据结构
初始化
public class Array<E> {
private int size;
private E[] data;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
}
添加元素
public void addLast(E e){
add(size,e);
}
public void addFirst(E e){
add(0,e);
}
// 在index索引的位置插入一个新元素e
public void add(int index,E e){
if(size == data.length)
throw new IllegalArgumentException("Add failed. Array is full.");
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
for(int i = size - 1; i >= index ; i --) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
在add函数中通过for循环，将数据从最后一个开始一个一个往后挪一位，这样做的目的是讲
index这个位置空出来最终插入需要添加的元素这里我们的数组只能实现固定的长度，当添加超过规定长度时会抛出异常，不用担心接下来会实现动态扩容和缩减功能
获取和修改元素
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
包含，搜索和删除
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size-1);
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
E e = data[index];
for (int i = index; i <=data.length; i++) {
data[i] = data[i+1];
}
size--;
data[size] = null;
return e;
}
// 从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for (int i = 0; i < data.length; i++) {
if (data[i].equals(e)) {
return I;
}
}
return -1;
}
// 查找数组中是否有元素e
public boolean contain(E e){
for (E datum : data) {
if (datum.equals(e)) {
return true;
}
}
return false;
}
- 注意remove中最后将data[size]设为null
动态数组(动态扩容和缩容)与复杂度震荡
// 在index索引的位置插入一个新元素e
public void add(int index,E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
if(size == data.length)
resetData(size*2);
for (int i = 0; i < data.length; i++) {
data[index + 1] = data[I];
}
data[index] = e;
size++;
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
E e = data[index];
for (int i = index; i < data.length; i++) {
data[i] = data[i+1];
}
size--;
if (size==data.length/4) {
resetData(data.length/2);
}
return e;
}
// 将数组空间的容量变成newCapacity大小
public void resetData(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < sze; i++) {
newData[i] = data[I];
}
data = newData;
}
resetData方法传入需要的容量，并新建数组newData，通过循环将之前data的数据复制到newData中。最后将
data地址指到新建的newData。而老数组由于没有了指向，最终会被jvm回收add函数中，当
size达到容量界限时扩容到现在的2倍。而remove中，当size为容量的¼时,可能同学们都有疑问这里缩容条件为什么不是½呢？这里就涉及到一个效率问题，举例：假设缩容条件为½
Aarry array = new Array(5);
array.addLast(1);
array.addLast(2);
array.addLast(3);
size为3，容量为5，当我们再次添加数据：
array.addLast(4);
此时该操作方法的时间复杂度时O(1),然而当我们再次array.addLast时由于有了扩容操作resetData,此时时间复杂度为O(n)容量变为10。如果此时进行一个removeLast，由于满足了缩容条件½,会再次调用resetData此操作又是一个时间复杂度为O(n)的操作。如果一个操作反复在这个条件之间操作，就会极大的降低操作效率，这种一个时间复杂度O(1)的操作变为O(n)的操作又叫做--复杂度震荡。如果此时缩容条件为四分之一则可以有效的避免这种情况
