Array 动态数组
Array 动态数组, 也就是Java内置ArrayLIst的底层实现，也是是栈和队列的底层实现方法之一。
什么是Array?
Array 也称动态数组，是一个线性以存储数据为目的数据结构，它具有以下几个重要特性:
具有索引，能够通过索引对Array对象进行访问, 时间复杂度为O(1)
一个Array对象里面只能存储一种数据类型, 比如全部存储 int 类型
能够动态地进行扩容，缩容操作
是Java内置ArrayList地底层实现, 也是栈和队列的底层实现
Array 图解表示
一个Array对象 可以用下图进行表示。
Array具有3个重要的成员属性, 分别是:
data, 是Java 中的 一维数组
size, 指向data中下一个可以存放数据的索引, 初始值为0
capacity, 表示Array的容量, 也就是data的长度, 在扩容和缩容时动态改变
构造方法
根据上面所说，我们可以很轻易地写出Array的构造方法, 为了增加代码的复用性, 我们使用了泛型。
public class Array<E> {
private E[] data;
private int size;//有效的元素个数
/**
* 传入数组容量构造Array
* @param capacity
*/
public Array(int capacity){
this.data =(E[]) new Object[capacity];
this.size=0;
}
//若不传入, 则创建一个容量为10的Array对象
public Array(){
this(10);
}
}Array还应该有一些常用方法
获取有效元素个数
public int getSize(){
return this.size;
}获取容积
public int getCapacity(){
return this.data.length;
}判断是否为空
public boolean isEmpty(){
return size==0;
}通过索引, 获得元素
public E get(int index){
if (index<0 || index >= this.size){
throw new IllegalArgumentException("Add failed. Required index>=0 <=arr.size");
}
return data[index];
}
获得最后一个元素
public E getLast(){
return this.get(this.size-1);
}获取第一个元素
public E getFirst(){
return this.get(0);
}通过索引, 更改元素
public void set(int index, E e){
if (index<0 || index >= this.size){
throw new IllegalArgumentException("Add failed. Required index>=0 <=arr.size");
}
data[index] =e;
}查询是否包含某个元素
public boolean contains(E e){
for (int i = 0; i < this.size; i++) {
if(data[i].equals(e)){
return true;
}
}
return false;
}查询是否包含某个元素, 并返回索引，若不存在返回-1
public int find(E e){
for (int i = 0; i < this.size; i++) {
if(data[i].equals(e)){
return i;
}
}
return -1;
}扩容, 缩容 resize 操作
当Array 对象容量已满, 想要继续向 Array 对象增加元素需要扩容
当Array 对象元素占容量的很少一部分时, 为节省内存空间，需要缩容
扩容缩容的操作非常简单, 首先构造一个新的 Java数组, 将原数组内的元素全部复制到新数组里面，组后 data指向新数组
//数组扩/缩容
private void resize(int newCapacity){
E[] newData=(E[]) new Object[newCapacity];
for (int i = 0; i < this.size; i++) {
newData[i]=data[i];
}
this.data=newData;
}向指定位置插入一个新元素
若Array容量已满，我们需要对内置的数组进行扩容, 我们选择扩大一倍容量，这只是一个经验值，也可以换成别的值
//在index位置插入一个新元素,index后面的元素需要后移
public void add(int index, E e){
//若索引<0 或是 大于 size, 抛出异常。
if (index<0 || index >this.size){
throw new IllegalArgumentException("Add failed. Required index>=0 <=arr.size");
}
//数组已满,需要扩容
if (this.size==this.data.length){
this.resize(2* data.length);
}
//将index后面的元素一个个后移
for (int i = size-1; i >=index ; i--) {
data[i+1]=data[i];
}
//插入新元素
this.data[index]=e;
//更新有效元素个数
this.size++;
}在首尾插入元素, 只需要调用 add() 函数即可
public void addFirst(E e){
add(0,e);
}
public void addLast(E e){
this.add(this.size,e);
}删除指定位置的元素并返回
//删除index位置的元素,返回删除的元素
public E remove(int index){
//索引越界，抛出异常
if (index<0 || index > this.size){
throw new IllegalArgumentException("Add failed. Required index>=0 <=arr.size");
}
//return的元素
E ret=data[index];
//将index之后的元素, 一个个向前移
for(int i=index+1;i<size;i++){
data[i-1]=data[i];
}
//更新有效元素个数
size--;
//减少了一个元素,将原来最后一个设为NULL
data[size]=null;
//动态减少空间
if (size<= data.length/4 && data.length/2!=0 ){
this.resize(data.length/2);
}
return ret;
}这里特别注意，我们进行缩容的条件。当Array元素小于容积 1/4 时，我们只缩容1/2
这是为了防止resize操作引起的复杂度震荡。假设有这么一个场景, 需要频繁地加入一个元素，进行扩容两倍，随后立马删掉一个元素，又进行缩容至一半。如此反复调用 resize 需要反反复复地 new 一个新数组，非常消耗性能。所以我们把删除元素后resize的条件设置的苛刻一些，宁愿浪费一些空间，也不要引起复杂度的震荡。
删除元素不反回, 删除首尾元素, 都只要调用 remove()函数即可
public void removeElement(E e){
int index=find(e);
if (index!=-1){
remove(index);
}
}
public E removeLast(){
return this.remove(size-1);
}
public E removeFirst(){
return this.remove(0);
}重写toString() 函数, 方便打印输出Array的容积，有效元素个数 和 里面的元素
@Override
public String toString() {
StringBuilder res =new StringBuilder();
res.append("Array: size="+ this.size+ " capacity="+this.data.length);
res.append(" [");
for (int i = 0; i < this.size; i++) {
res.append(data[i]);
if(i!=size-1){
res.append(", ");
}
}
res.append("]");
return res.toString();
}至此我们完成了所有Array的功能模块
测试一下
编写了一个Array测试类
public class ArrayTest {
public static void main(String[] args) {
//泛型中只能放类
Array<Integer> arr= new Array();
for (int i = 0; i < 10; i++) {
arr.addLast(i);
}
System.out.println(arr);
//测试扩容功能
arr.add(10,10);
System.out.println(arr);
//测试增加元素功能
arr.add(1,100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
//测试删除元素功能
arr.remove(2);
System.out.println(arr);
arr.removeElement(10);
System.out.println(arr);
//测试动态减小空间功能
arr.removeElement(9);
arr.removeElement(8);
arr.removeElement(7);
arr.removeElement(6);
arr.removeElement(5);
arr.removeElement(4);
System.out.println(arr);
}
}输出结果
Array: size=10 capacity=10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=11 capacity=20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Array: size=12 capacity=20 [0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Array: size=13 capacity=20 [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Array: size=12 capacity=20 [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Array: size=11 capacity=20 [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=5 capacity=10 [-1, 0, 1, 2, 3]Last updated
Was this helpful?