1.数组基础
- java提供给我们的数组是静态数组，初始化时需要指定空间，且存放的类型为基础的数据类型，而且并不支持扩容等操作，但是有时我们存放一类数据，事先并不知道需要准备多少空间给我们的数据，这是静态数组的局限性，数组是最基础的一种数据结构，很多其他数据结构都可以基于数组实现。
- 由于数组的局限性，因此java为我们提供了集合这种高级数据结构，在集合中，ArrayList的底层就是使用静态数组来实现的，因此可以把ArrayList当作一种动态数组，在集合中使用泛型来支持存储任意相同类型的对象，使用扩容来实现不需要指定大小来存储未知数量的元素，来大大的扩展集合的作用，但是泛型并不支持基础数据类型，因此基础数据类型又有其对应的包装类。
- 基于静态数组，我们实现自己的动态数组，也可以称为自定义集合，支持泛型和扩容操作。
- 由于使用数组同时可以实现其他种类的数据结构(栈，队列，堆)，除了模拟ArrayList部分方法实现，其他的方法提供为后续实现其他数据结构做准备
2.实现
2.1.基于java静态数组做二次封装
public class Array<E> {
private E[] data;
//记录元素个数
private int size;
/**
* 构造函数，传入数组的容量构造一个数组
*
* @param capacity ：容量
*/
public Array(int capacity) {
if (capacity == 0) {
capacity = 10;
}
data = (E[]) new Object[capacity];
size = 0;
}
/**
* 无参构造函数，默认数组的容量capacity = 10
*/
public Array() {
this(10);
}
/**
* 传入一个数组，构造动态数组
* @param arr ：
*/
public Array(E[] arr) {
data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
size = arr.length;
}
}
提供三个构造函数，可以直接传入一个静态数组，也可以指定容量或者不指定
2.2.提供基础方法
/**
* 获取数组的容量
*
* @return ：容量大小
*/
public int getCapacity() {
return data.length;
}
/**
* 数组是否为空
*
* @return ：
*/
public boolean isEmpty() {
return size == 0;
}
2.3.添加方法
/**
* 往数组中最后添加一个元素
*
* @param e ：添加的元素
*/
public void addLast(E e) {
add(size, e);
}
/**
* 往数组中第一个位置添加元素
*
* @param e ：添加的元素
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 往指定位置添加一个元素
*
* @param index ：位置
* @param e ：添加的元素
*/
public void add(int index, E e) {
//index是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed,index is illegal.");
}
//若元素个数等于最大容量，数组已满
if (size == data.length) {
//上向四舍五入，当用户传入capacity = 1时，直接使用int会永不扩容
resize((int) Math.ceil(1.5 * data.length));
}
//该指定位置所有元素往后移一位，将新元素e放入指定位置
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
/**
* 扩容数组
*
* @param newCapacity ：新的容量
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 设置数组中某个元素
*
* @param index ： 下标(索引)
* @param e : 修改的元素
*/
public void set(int index, E e) {
//index是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed,Require index is illegal");
}
data[index] = e;
}
添加方法可以在数组首尾和中间添加元素，因此可以复用在指定位置添加一个元素这个方法，添加元素的思路，要先判断当前数组是否已经满了(在ArrayList有更优的解决方案),若满了，先扩容再添加元素
2.4.判断方法
/**
* 查找数组中是否有元素e
*
* @param e :元素
* @return ：
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
/**
* 查找数组中某元素的索引
* 若没有该元素则返回-1
*
* @return ：返回索引或-1
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
2.5.删除方法
/**
* 删除数组中索引为index的元素，并返回这个元素
* 使用泛型支持任何类型的对象，不支持基本数据类型(使用基础数据类型的包装类)
*
* @param index ：索引
* @return ：删除的元素
*/
public E remove(int index) {
//index是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Remove failed,index is illegal");
}
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
//当前元素为数组容量的四分之一时，缩减数组容量为原数组的一半
//若当前数组的容量为1，则不允许缩容
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
/**
* 删除数组中第一个元素
*
* @return ：
*/
public E removeFirst() {
return remove(0);
}
/**
* 删除数组中最后一个元素
*
* @return ：
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 删除数组中元素为e的第一个元素
*
* @param e : 删除的元素
*/
public void removeElement(E e) {
//获取e的索引
int index = find(e);
//若元素存在
if (index != -1) {
remove(index);
}
}
2.6.获取方法
/**
* 根据索引值获取数组中某个元素
*
* @param index ： 下标
* @return ：该下标元素
*/
public E get(int index) {
//index是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed,Require index is illegal");
}
return data[index];
}
/**
* 获取第一个索引的元素
*
* @return : 第一个元素
*/
public E getFirst() {
return get(0);
}
/**
* 获取最后一个索引的值
*
* @return : 最后一个元素
*/
public E getLast() {
return get(size - 1);
}
2.7.重写toString方法
/**
* 重新自定义打印方法
*
* @return ：
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(String.format("Array：size = %d , capacity = %d\n", size, data.length));
str.append("[");
for (int i = 0; i < size; i++) {
str.append(data[i]);
if (i != size - 1) {
str.append(",");
}
}
str.append("]");
return str.toString();
}
