数据结构——单链表的增删改查-数据结构-单链表的增删改查.md

焦虑烧麦 197 2022-05-02

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