一.数组基础
1.数组，即把数据码成一排存放。
数组优点：快速查询。
数组最好应用于“索引有语意”的情况，但并非所有有语意的索引都适用于数组，数组也可以处理“索引没有语意”的情况。
2.增、删、改、查，是研究数据结构的基本脉络。
设二次封装的数组的类Array<E>(类型为E，泛型)，E[ ] data 基本参数有capacity和size。
capacity为数组空间最多装的元素个数，即data.length。
size为数组实际装的元素个数。
有些方法需要对size进行维护。
二. 动态数组常见方法
1.基础方法
1）方法1：有参构造函数设置动态数组的capacity
java不支持data = new E[capacity]，需写为data=(E[])new Object[capacity]
2）方法2：无参构造函数默认数组的capacity为10
3）方法3：获取数组元素个数 即size
4）方法4：获取数组的容量 即capacity，data.length
5）方法5：返回数组是否为空 即判断size是否为0
public class Array<E> {
private E[] data;
private int size; //构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
} //无参数的构造函数，默认的数组容量capacity=10
public Array(){
this(10);
} //获取数组中的元素个数
public int getSize(){
return size;
} //获取数组的容量
public int getCapacity(){
return data.length;
} //返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
}
2.增（插入元素）
1）方法1：在index位置插入元素
add(int index, E e)
a.先判断index是否合法，若index<0||index>size，则抛出异常
b.若index == data.length，此时需要调用resize()方法对数组进行扩容（扩容为2*capacity）
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for(int i = 0 ; i < size ; i ++){
newData[i] = data[i];
}
data = newData;
}
resize()方法思想即创建一个容量为newCapacity的新数组newData，通过将data中的每个元素依次赋值给newData，最后令data=newData。
c.在指定位置插入元素的思想，即为从最后一位（size-1）开始，开始循环将元素向后挪一位（data[i+1]=data[i]），直到index的位置。
然后令data[index]=e,
最后，维护size，即size++
2）方法2：向所有元素后添加元素
addLast(E e) 即add(size, e)
3）方法3：向首位值添加元素
addFirst(E e) 即add(0, e)
//向所有元素后添加元素
public void addLast(E e){
add(size, e);
}
//向首位指添加元素
public void addFirst(E e){
add(0,e);
} // important index位置插入元素e
public void add(int index, E e){ if( index < 0 || index > size){
throw new IllegalArgumentException("AddLast failed. Require index < 0 || index > size");
} if(size == data.length){
resize(2 * data.length);
} for(int i = size - 1 ; i >= index ; i -- ){
data[ i + 1 ] = data[i];
} data[index] = e;
size ++;
}
3.查（查询元素）
1）方法1：获取index索引位置的元素
get(int index)
a.先判断index是否合法，若index<0||index>=size，则抛出异常
b.返回data[index]
2）方法2：查找数组中是否有元素e
contains(E e)
循环查找，若有data[i].equals(e)，则返回true，否则返回false。（java中判断类对象的值是否相等采用.equals()方法）
3）方法3：查找元素e所在的索引index，若元素不存在，则返回-1
find(E e)
循环查找，若有data[i].equals(e)，则返回i，否则返回-1
//获取index索引位置的元素
E get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed. Index is illegal");
}
return data[index];
}
//查找数组中是否有元素e
public boolean contains(E e){
for(int i = 0 ; i < size; i ++){
if(data[i].equals(e))
return true;
}
return false;
} //查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for(int i = 0 ; i < size ; i ++){
if(data[i].equals(e)){
return i;
}
}
return -1;
}
4.删（删除元素）
1）方法1：从数组中删除index位置的元素，并返回删除的元素
remove(int index)
a.先判断index是否合法，若index<0||index>=size，则抛出异常。
b.定义ret=data[index]，作为返回值。
c.开始删除操作，即从i=index位置开始，循环地使data[i]=data[i+1]，即将下一位元素覆盖到当前元素中，直到size-1。
d.维护size，即 size --。
e.（非必需）但此时data[size]还是存在用不到的数的，可以进行data[size]=null的操作来避免空间浪费。
f.判断当前size==data.length/2，如果为true，则进行缩容，调用resize()方法，使capacity=data.length/2，避免空间浪费。
g.返回ret，即删除的元素。
2）方法2：删除首个位置的元素并返回该元素
remove(0)
3）方法3：删除末尾位置的元素并返回该元素
remove(size)
4）方法4：直接从数组中删除元素e
emoveElement(E e)方法
先通过find()方法寻找e的index，若存在则返回e的index，不存在则返回-1，当index不为-1时，remove(index)
//从数组中删除index位置的元素，并返回删除的元素
public E remove(int index){
if( index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal"); E ret = data[index]; for(int i = index ; i < size - 1 ; i ++){
data[i] = data[i + 1];
}
size --;
data[size] = null; //loitering objects != memory leak is Better if(size == data.length/2 )
resize(data.length/2);
return ret;
} //删除首个位置的元素
public E removeFirst(){
return remove(0);
} //删除最后一个元素
public E removeLast(){
return remove(size - 1);
} //从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
5.改（重置数组中的元素）
set(int index, E e)
a.先判断index是否合法，若index<0||index>=size，则抛出异常。
b.令data[index] = e
//修改index索引位置的元素e
void set(int index, E e){
if(index < 0 || index >=size){
throw new IllegalArgumentException("Set failed. Index is illegal");
} data[index] = e;
}
6.重写toString()方法，让输出更具有可读性
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
res.append('[');
for(int i = 0 ; i < size ; i ++){
res.append(data[i]);
if(i != size-1){
res.append(", ");
}
}
res.append(']');
return res.toString();
}