1.只能存放int的自定义数组类
public class Array {
private int[] data;
private int size;//data[size]指向数组中第一个没有数据的位置
//传入数组的容量capacity构造Array
public Array(int capacity){
data=new int[capacity];
size=0;
}
//无参构造，默认数组capacity为10
public Array(){
data=new int[10];
size=0;
}
//获取数组已有长度
public int getSize(){
return size;
}
//获取数组容量
public int getCapacity(){
return data.length;
}
//判断数组是否为空
public boolean isEmpty(){
return size==0;
}
//向数组尾部添加数据
public void addLast(int e){
add(size,e);
}
//向数组头添加数据
public void addFirst(int e){
add(0,e);
}
//向数组中任意一个位置添加数据
public void add(int index,int e){
if(data.length==size)
throw new IllegalArgumentException("array is full");
if(index<0||index>size)
throw new IllegalArgumentException("array is full");
for(int i=size-1;i>=index;i--){
data[i+1]=data[i];
}
data[index]=e;
size++;
}
//获取某个索引元素
public int get(int index,int e){
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
return data[index];
}
//设置某个索引位置元素
public void set(int index,int e){
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
data[index]=e;
}
//判断数组是否包含某个元素
public boolean contains(int e){
for(int i=0;i<size;i++){
if(data[i]==e)
return true;
}
return false;
}
//查找某个元素并返回索引，不存在则返回-1
public int find(int e){
for(int i=0;i<size;i++){
if(data[i]==e)
return i;
}
return -1;
}
//删除索引位置元素并返回被删元素值
public int remove(int index){
int tem=data[index];
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
for(int i=index+1;i<size;i++)
data[i-1]=data[i];
size--;
return tem;
}
//删除指定数值的元素
public void removeElement(int e){
int index = find(e);
if(index!=-1)
remove(index);
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size=%d capacity=%d\n", size,data.length));
sb.append("[");
for(int i=0;i<size;i++){
sb.append(data[i]);
if(i!=size-1)
sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
2.泛型化数组
public class Array<E> {
private E[] data;
private int size;//data[size]指向数组中第一个没有数据的位置
//传入数组的容量capacity构造Array
public Array(int capacity){
//data=new E[capacity];这样子new不对
data=(E[]) new Object[capacity];
size=0;
}
//无参构造，默认数组capacity为10
public Array(){
//data=new E[10];
data= (E[]) new Object[10];
size=0;
}
//获取数组已有长度
public int getSize(){
return size;
}
//获取数组容量
public int getCapacity(){
return data.length;
}
//判断数组是否为空
public boolean isEmpty(){
return size==0;
}
//向数组尾部添加数据
public void addLast(E e){
add(size,e);
}
//向数组头添加数据
public void addFirst(E e){
add(0,e);
}
//向数组中任意一个位置添加数据
public void add(int index,E e){
if(data.length==size)
throw new IllegalArgumentException("array is full");
if(index<0||index>size)
throw new IllegalArgumentException("array is full");
for(int i=size-1;i>=index;i--){
data[i+1]=data[i];
}
data[index]=e;
size++;
}
//获取某个索引元素
public E get(int index,E e){
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
return data[index];
}
//设置某个索引位置元素
public void set(int index,E e){
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
data[index]=e;
}
//判断数组是否包含某个元素
public boolean contains(E e){
for(int i=0;i<size;i++){
//if(data[i]==e)
//==为引用比较
//equals为值比较，对于对象来说，进行值比较
if (data[i].equals(e))
return true;
}
return false;
}
//查找某个元素并返回索引，不存在则返回-1
public int find(E e){
for(int i=0;i<size;i++){
//if(data[i]==e)
if (data[i].equals(e))
return i;
}
return -1;
}
//删除索引位置元素并返回被删元素值
public E remove(int index){
E tem=data[index];
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
for(int i=index+1;i<size;i++)
data[i-1]=data[i];
size--;
return tem;
}
//删除指定数值的元素
public void removeElement(E e){
int index = find(e);
if(index!=-1)
remove(index);
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size=%d capacity=%d\n", size,data.length));
sb.append("[");
for(int i=0;i<size;i++){
sb.append(data[i]);
if(i!=size-1)
sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
3.动态数组
//当数组满时进行扩容
private void resize(int newCapacity){
E[] newData=(E[])new Object[newCapacity];
for (int i=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);
public class Array<E> {
private E[] data;
private int size;//data[size]指向数组中第一个没有数据的位置
//传入数组的容量capacity构造Array
public Array(int capacity){
//data=new E[capacity];这样子new不对
data=(E[]) new Object[capacity];
size=0;
}
//无参构造，默认数组capacity为10
public Array(){
//data=new E[10];
data= (E[]) new Object[10];
size=0;
}
//获取数组已有长度
public int getSize(){
return size;
}
//获取数组容量
public int getCapacity(){
return data.length;
}
//判断数组是否为空
public boolean isEmpty(){
return size==0;
}
//向数组尾部添加数据
public void addLast(E e){
add(size,e);
}
//向数组头添加数据
public void addFirst(E e){
add(0,e);
}
//向数组中任意一个位置添加数据
public void add(int index,E e){
if(index<0||index>size)
throw new IllegalArgumentException("error");
//当数组满了，进行扩容
if(data.length==size)
resize(2*data.length);
for(int i=size-1;i>=index;i--){
data[i+1]=data[i];
}
data[index]=e;
size++;
}
//获取某个索引元素
public E get(int index,E e){
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
return data[index];
}
//设置某个索引位置元素
public void set(int index,E e){
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
data[index]=e;
}
//判断数组是否包含某个元素
public boolean contains(E e){
for(int i=0;i<size;i++){
//if(data[i]==e)
//==为引用比较
//equals为值比较，对于对象来说，进行值比较
if (data[i].equals(e))
return true;
}
return false;
}
//查找某个元素并返回索引，不存在则返回-1
public int find(E e){
for(int i=0;i<size;i++){
//if(data[i]==e)
if (data[i].equals(e))
return i;
}
return -1;
}
//删除索引位置元素并返回被删元素值
public E remove(int index){
E tem=data[index];
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
for(int i=index+1;i<size;i++)
data[i-1]=data[i];
size--;
//当元素减少到一半时，进行缩容
if (size== data.length/2)
resize(data.length/2);
return tem;
}
//删除指定数值的元素
public void removeElement(E e){
int index = find(e);
if(index!=-1)
remove(index);
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size=%d capacity=%d\n", size,data.length));
sb.append("[");
for(int i=0;i<size;i++){
sb.append(data[i]);
if(i!=size-1)
sb.append(", ");
}
sb.append("]");
return sb.toString();
}
//当数组满时进行扩容
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()并不是每次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);