1.只能存放int的自定义数组类
publicclassArray {
privateint[] data;
privateintsize;//data[size]指向数组中第一个没有数据的位置
//传入数组的容量capacity构造Array
publicArray(intcapacity){
data=newint[capacity];
size=0;
}
//无参构造，默认数组capacity为10
publicArray(){
data=newint[10];
size=0;
}
//获取数组已有长度
publicintgetSize(){
returnsize;
}
//获取数组容量
publicintgetCapacity(){
returndata.length;
}
//判断数组是否为空
publicbooleanisEmpty(){
returnsize==0;
}
//向数组尾部添加数据
publicvoidaddLast(inte){
add(size,e);
}
//向数组头添加数据
publicvoidaddFirst(inte){
add(0,e);
}
//向数组中任意一个位置添加数据
publicvoidadd(intindex,inte){
if(data.length==size)
thrownewIllegalArgumentException("array is full");
if(index<0||index>size)
thrownewIllegalArgumentException("array is full");
for(inti=size-1;i>=index;i--){
data[i+1]=data[i];
}
data[index]=e;
size++;
}
//获取某个索引元素
publicintget(intindex,inte){
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
returndata[index];
}
//设置某个索引位置元素
publicvoidset(intindex,inte){
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
data[index]=e;
}
//判断数组是否包含某个元素
publicbooleancontains(inte){
for(inti=0;i<size;i++){
if(data[i]==e)
returntrue;
}
returnfalse;
}
//查找某个元素并返回索引，不存在则返回-1
publicintfind(inte){
for(inti=0;i<size;i++){
if(data[i]==e)
returni;
}
return-1;
}
//删除索引位置元素并返回被删元素值
publicintremove(intindex){
inttem=data[index];
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
for(inti=index+1;i<size;i++)
data[i-1]=data[i];
size--;
returntem;
}
//删除指定数值的元素
publicvoidremoveElement(inte){
intindex=find(e);
if(index!=-1)
remove(index);
}
@Override
publicStringtoString(){
StringBuildersb=newStringBuilder();
sb.append(String.format("Array: size=%d capacity=%d\n", size,data.length));
sb.append("[");
for(inti=0;i<size;i++){
sb.append(data[i]);
if(i!=size-1)
sb.append(", ");
}
sb.append("]");
returnsb.toString();
}
}
2.泛型化数组
publicclassArray<E> {
privateE[] data;
privateintsize;//data[size]指向数组中第一个没有数据的位置
//传入数组的容量capacity构造Array
publicArray(intcapacity){
//data=new E[capacity];这样子new不对
data=(E[]) newObject[capacity];
size=0;
}
//无参构造，默认数组capacity为10
publicArray(){
//data=new E[10];
data= (E[]) newObject[10];
size=0;
}
//获取数组已有长度
publicintgetSize(){
returnsize;
}
//获取数组容量
publicintgetCapacity(){
returndata.length;
}
//判断数组是否为空
publicbooleanisEmpty(){
returnsize==0;
}
//向数组尾部添加数据
publicvoidaddLast(Ee){
add(size,e);
}
//向数组头添加数据
publicvoidaddFirst(Ee){
add(0,e);
}
//向数组中任意一个位置添加数据
publicvoidadd(intindex,Ee){
if(data.length==size)
thrownewIllegalArgumentException("array is full");
if(index<0||index>size)
thrownewIllegalArgumentException("array is full");
for(inti=size-1;i>=index;i--){
data[i+1]=data[i];
}
data[index]=e;
size++;
}
//获取某个索引元素
publicEget(intindex,Ee){
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
returndata[index];
}
//设置某个索引位置元素
publicvoidset(intindex,Ee){
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
data[index]=e;
}
//判断数组是否包含某个元素
publicbooleancontains(Ee){
for(inti=0;i<size;i++){
//if(data[i]==e)
//==为引用比较
//equals为值比较，对于对象来说，进行值比较
if (data[i].equals(e))
returntrue;
}
returnfalse;
}
//查找某个元素并返回索引，不存在则返回-1
publicintfind(Ee){
for(inti=0;i<size;i++){
//if(data[i]==e)
if (data[i].equals(e))
returni;
}
return-1;
}
//删除索引位置元素并返回被删元素值
publicEremove(intindex){
Etem=data[index];
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
for(inti=index+1;i<size;i++)
data[i-1]=data[i];
size--;
returntem;
}
//删除指定数值的元素
publicvoidremoveElement(Ee){
intindex=find(e);
if(index!=-1)
remove(index);
}
@Override
publicStringtoString(){
StringBuildersb=newStringBuilder();
sb.append(String.format("Array: size=%d capacity=%d\n", size,data.length));
sb.append("[");
for(inti=0;i<size;i++){
sb.append(data[i]);
if(i!=size-1)
sb.append(", ");
}
sb.append("]");
returnsb.toString();
}
}
3.动态数组
//当数组满时进行扩容
privatevoidresize(intnewCapacity){
E[] newData=(E[])newObject[newCapacity];
for (inti=0;i<size;i++)
newData[i]=data[i];
data=newData;
}
//当元素减少到一半时，进行缩容
if (size==data.length/2)
resize(data.length/2);
//当数组满了，进行扩容
if(data.length==size)
resize(2*data.length);
publicclassArray<E> {
privateE[] data;
privateintsize;//data[size]指向数组中第一个没有数据的位置
//传入数组的容量capacity构造Array
publicArray(intcapacity){
//data=new E[capacity];这样子new不对
data=(E[]) newObject[capacity];
size=0;
}
//无参构造，默认数组capacity为10
publicArray(){
//data=new E[10];
data= (E[]) newObject[10];
size=0;
}
//获取数组已有长度
publicintgetSize(){
returnsize;
}
//获取数组容量
publicintgetCapacity(){
returndata.length;
}
//判断数组是否为空
publicbooleanisEmpty(){
returnsize==0;
}
//向数组尾部添加数据
publicvoidaddLast(Ee){
add(size,e);
}
//向数组头添加数据
publicvoidaddFirst(Ee){
add(0,e);
}
//向数组中任意一个位置添加数据
publicvoidadd(intindex,Ee){
if(index<0||index>size)
thrownewIllegalArgumentException("error");
//当数组满了，进行扩容
if(data.length==size)
resize(2*data.length);
for(inti=size-1;i>=index;i--){
data[i+1]=data[i];
}
data[index]=e;
size++;
}
//获取某个索引元素
publicEget(intindex,Ee){
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
returndata[index];
}
//设置某个索引位置元素
publicvoidset(intindex,Ee){
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
data[index]=e;
}
//判断数组是否包含某个元素
publicbooleancontains(Ee){
for(inti=0;i<size;i++){
//if(data[i]==e)
//==为引用比较
//equals为值比较，对于对象来说，进行值比较
if (data[i].equals(e))
returntrue;
}
returnfalse;
}
//查找某个元素并返回索引，不存在则返回-1
publicintfind(Ee){
for(inti=0;i<size;i++){
//if(data[i]==e)
if (data[i].equals(e))
returni;
}
return-1;
}
//删除索引位置元素并返回被删元素值
publicEremove(intindex){
Etem=data[index];
if(index<0||index>=size)
thrownewIllegalArgumentException("index error");
for(inti=index+1;i<size;i++)
data[i-1]=data[i];
size--;
//当元素减少到一半时，进行缩容
if (size==data.length/2)
resize(data.length/2);
returntem;
}
//删除指定数值的元素
publicvoidremoveElement(Ee){
intindex=find(e);
if(index!=-1)
remove(index);
}
@Override
publicStringtoString(){
StringBuildersb=newStringBuilder();
sb.append(String.format("Array: size=%d capacity=%d\n", size,data.length));
sb.append("[");
for(inti=0;i<size;i++){
sb.append(data[i]);
if(i!=size-1)
sb.append(", ");
}
sb.append("]");
returnsb.toString();
}
//当数组满时进行扩容
privatevoidresize(intnewCapacity){
E[] newData=(E[])newObject[newCapacity];
for (inti=0;i<size;i++)
newData[i]=data[i];
data=newData;
}
}
均摊复杂度
resize()并不是每次add都会触发，可以将其均摊到add步骤上
复杂度震荡
//当元素减少到一半时，进行缩容
if (size==data.length/2)
resize(data.length/2);
//当数组满了，进行扩容
if(data.length==size)
resize(2*data.length);
当数组中的数据一直在data.length/2附近波动，会产生复杂度震荡，操作过于激进，可以使用相对lazy的策略
//当元素减少到1/4时，进行缩容
if (size==data.length/4&&data.length/2!=0)
resize(data.length/2);
