Java中的List我们经常会使用到,但是很少关注其内部实现,List是一个接口, 里面定义了一些抽象的方法,其目的就是对线性表的抽象,其中的方法就是线性表的一些常用基本运算。 而对于线性表的不同存储结构其实现方式就有所不同了,比如ArrayList是对线性表顺序存储结构的实现, LinkedList是线性表链式存储结构的实现等。 存储结构没有确定我们就不知道数据怎么存储, 但是对于线性表这种逻辑结构中数据的基本操作我们可以预知,无非就是获取长度、获取指定位置的数据、插入数据、 删除数据等等操作,可以参考List。
定义一个接口MyList
//1:返回线性表大小
public int getSize();
//2:判断线性表是否为空:false:true
public boolean isEmpty();
//3:判断线性表是否含有元素e
public boolean contains(Object e);
//4: 查找 返回e元素所在的位置
public int indexOf(Object e);
//4.1:查找 返回第i个位置的元素
public Object get(int i);
//5:将元素e插入到顺序表的第i个位置
public void add(int i,Object e) throws Exception;
public void add(Object e) throws Exception;
//6:将元素e插入到obj之前
public boolean addBefore(Object obj,Object e) throws Exception;
//7:将元素e插入到obj之后
public boolean addAfter(Object obj,Object e) throws Exception;
//8:删除第i个位置元素
public void remove(int i) throws Exception;
//9:删除线性表中第一个为e的元素
public boolean removed (Object e) throws Exception;
//10:替换第i个元素为e
public Object replace(int i,Object e) throws Exception;
//11:输出线性表
public void display();
}
实例化接口
//创建一个存储空间为maxSize的顺序表
private Object[] myList;//顺序表的存储空间
private int size;//顺序表的当前长度
private int maxSize;
//构建顺序表
public MyArrayList(int maxsize) {
size=0;
maxSize=maxsize;
myList=new Object[maxSize];
}
@Override //1:返回线性表大小
public int getSize() {//获取顺序表大小
return this.size;
}
@Override //2:判断线性表是否为空:false:true
public boolean isEmpty() { //空表
return size==0;
}
@Override //3:判断线性表是否含有元素e
public boolean contains(Object e) {//判断是否含有元素e
for (int i=0;i<size;i++){//遍历
if(myList[i].equals(e)){
return true;
}
}
return false;
}
@Override //4: 查找 返回e元素所在的位置
public int indexOf(Object e) { //返回元素e的位置
for (int i=0;i<size;i++){
if(myList[i].equals(e)){
return i;
}
}
return -1;
}
//4.1:查找 返回第i个位置的元素
public Object get(int i){//返回第i个位置的元素
return myList[i];
//return -1;
}
@Override //5:将元素e插入到顺序表的第i个位置
public void add(int i, Object e) throws Exception { //插入到i位置
if(size==maxSize)
throw new Exception("顺序表已满,不可插入");//throw为手动抛出异常
if(i<0||i>size)
throw new Exception("插入位置不合法");
for(int j=size;j>i;j--){
myList[j]=myList[j-1];//i之后的数据依次后移
}
myList[i]=e;
size++;
}
@Override
public void add(Object e) throws Exception {
this.add(size,e);
}
@Override //6:将元素e插入到obj之前
public boolean addBefore(Object obj, Object e) throws Exception {//obj前插入e
//找到obj所在的位置 调用插入就行
int i=indexOf(obj);
if(i<0) return false;
add(i,e);
return true;
}
@Override //7:将元素e插入到obj之后
public boolean addAfter(Object obj, Object e) throws Exception { //obj后插入e
int i=indexOf(obj); //获取obj元素位置
if(i<0) return false; //没找到obj就会返回-1 此时i=-1;
add(i+1,e); //找到了调用插入即可
return true;
}
@Override //8:删除第i个位置元素
public void remove(int i) throws Exception {//移除第i个位置的元素
if(i<0||i>size-1) //判断是否越界
throw new Exception("删除位置不合法");
for(int j=i;j<size-1;j++){
myList[j]=myList[j+1]; //后面的依次向前移一个位置
}
size--;//移除了一个 所以长度-1
}
@Override //9:删除线性表中第一个为e的元素
public boolean removed(Object e) throws Exception {//直接移除元素e(第一个匹配的e)
//找到e的位置调用上面的删除 (先判断有没有)
int i=indexOf(e);
if(i<0) return false; //判断有没有e
remove(i);
return true;
}
@Override //10:替换第i个元素为e
public Object replace(int i, Object e) throws Exception { //替换第i位置的元素为e
if(i<0||i>size)
throw new Exception("位置不合法");
Object obj=myList[i];
myList[i]=e;
return obj;
}
@Override //11:输出线性表
public void display() {//输出顺序表
for(int i=0;i<size;i++){
System.out.print(myList[i]+" ");
}
System.out.println("\n");
}
}
用一个main方法具体实现
public arraylistTest01(int maxsize) {
super(maxsize);
// TODO Auto-generated constructor stub
}
public static void main(String[] args) throws Exception {
arraylistTest01 t1=new arraylistTest01(100);
//申请空间 注意此处如果是10插入的时候会抛出手写的那个异常
for(int i=0;i<10;i++){
t1.add(i, i); //调用insert依次插入构成顺序表
}
System.out.print("初始化的顺序表为:");
t1.display();//显示插入的顺序表
//1:查看
System.out.print("元素4位置为:"+t1.indexOf(4));//查看元素4的位置 从第0个开始
System.out.println("\n");
//2:插入
t1.add(2, 50);//第二个位置插入元素50
System.out.print("插入元素后的顺序表为:");
t1.display();
//3:删除某个位置的元素
t1.remove(5);
System.out.print("删除第5个元素后的顺序表为:");
t1.display();
//4:删除某个元素 :看着函数一样但是参数属性不一样 调用要注意
t1.removed(5);
System.out.print("删除元素5后的顺序表为:");
t1.display();
//修改
t1.replace(8,100);
System.out.print("将第8个元素替换成100后的顺序表为:");
t1.display();
}
}
运行结果
元素4位置为:4
插入元素后的顺序表为:0 1 50 2 3 4 5 6 7 8 9
删除第5个元素后的顺序表为:0 1 50 2 3 5 6 7 8 9
删除元素5后的顺序表为:0 1 50 2 3 6 7 8 9
将第8个元素替换成100后的顺序表为:0 1 50 2 3 6 7 8 100