- 一、动态数组
- 二、代码实现
- 1.增加
- 2.删除
- 3.修改
- 4.查询
- 5.测试
- 总结
一、动态数组
动态数组：就是在普通数组上，增加了一个可以根据元素的个数动态调整数组大小的功能。之前的普通数组最大的问题就是数组长度定长，一旦一个数组在定义时确定长度之后，在使用过程中无法修改这个长度。
Java中提供的数组都是静态数组 int类型、char类型、long类型、(定义之后没法改变长度)，需要我们自己来定义一个类，拓展基础数组的功能。
那么我们究竟是如何动态的调整数组的大小呢，实际上就是当我们数组已经满了的时候，使用Arrays.copyOf(data,data.length*2);来给数组扩容，这样就把旧数组的所有内容复制到新数组中，新数组的长度为原来数组的二倍。
只要是数据结构无外乎增删改查
1.增加代码如下：
public class MyArray{
//整型数组data
private int[] data;
//当前动态数组中已经存储的元素个数
private int size;
//有参构造，定义数组的长度
public MyArray(int initCap) {
this.data = new int[initCap];
}
//实现一个扩容的方法
private void grow() {
this.data = Arrays.copyOf(data, data.length * 2);
}
}
//为了让数组能打印出来，我们重写toString方法
public String toString() {
String ret = "[";
//此时取得是有效数据，所以小于size
for (int i = 0; i < size; i++) {
ret = ret + data[i];
if (i != size - 1) {
ret = ret + ",";
}
}
ret = ret + "]";
return ret;
}
//在当前数组中添加一个新元素val
public void add(int val) {
data[size] = val;
size++;
//判断数组是否已满，并进行扩容
if (size == data.length) {
grow();
}
}
//在index位置添加一个新元素
public void add(int index, int val) {
if (index < 0 || index > size) {
System.err.println("index is illegal");
}
//从当前最后一个有效元素开始向后搬移，把index位置空出来
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
//index位置空出来了，此时可以插入val;
data[index] = val;
size++;
if (size == data.length) {
grow();
}
}
2.删除
代码如下：
//删除索引为index对应的元素值，返回删除前的元素值
public int removeIndex(int index) {
if (index < 0 || index >= size) {
System.err.println("remove index is illegal");
return -1;
}
//元素搬移，从index开始，后一个元素覆盖前一个元素
// 一直走到size-1（最后一个有效元素）
int oldVal = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
return oldVal;
}
//删除数组中第一个元素
public int removeFirst() {
return removeIndex(0);
}
//删除数组中最后一个元素
public int removeLast() {
return removeIndex(size - 1);
}
//只删除第一个值为val的元素
public boolean removeByValueOnce(int val) {
for (int i = 0; i < size; i++) {
if (data[i] == val) {
removeIndex(i);
return true;
}
}
return false;
}
//删除数组中所有值为value的元素
public boolean removeAllValue(int val) {
if (getByValue(val) == -1) {
return false;
}
for (int j = 0; j < size; j++) {
if (data[j] == val) {
removeIndex(j);
//后一个元素将前一个元素覆盖后，判断当前元素是否为待删除元素
j--;
}
}
return true;
3.修改
代码如下：
//修改index位置的元素为newVal，并返回之前的元素oldVal
public int set(int index, int newVal) {
if (index < 0 || index >= size) {
return -1;
}
int oldVal = data[index];
data[index] = newVal;
return oldVal;
}
//将动态数组中第一个值为oldVal的元素修改为newVal
public boolean setValue(int oldVal, int newVal) {
int index = getByValue(oldVal);
if (index != -1) {
data[index] = newVal;
return true;
}
System.out.println("oldVal is not exist!");
return false;
}
4.查询
//查询当前动态数组中第一个值为val的元素的索引，若不存在 返回-1
public int getByValue(int val) {
for (int i = 0; i < size; i++) {
if (data[i] == val) {
return i;
}
}
return -1;
}
//查询当前动态数组中是否存在值为val的元素
public boolean contains(int val) {
if (getByValue(val) != -1) {
return true;
}
return false;
}
//查询当前动态数组中索引为index的元素值
public int get(int index) {
if (index < 0 || index >= size) {
System.err.println("index is illegal");
return -1;
}
return data[index];
}
5.测试
public static void main(String[] args) {
MyArray myArray = new MyArray(3);
myArray.add(10);
myArray.add(20);
myArray.add(20);
myArray.add(20);
System.out.println(myArray);
System.out.println(myArray.removeAllValue(20));
System.out.println(myArray);
}
总结
从上面我们可以看出动态数组可以防止数组越界，但同时也浪费了大量的空间，数组的删除操作需要移动大量的元素，也很麻烦。
