java总结之链表实现队列

系统管理员 2022-04-14 05:20 181阅读 0赞

链表在我看来就是一种基础的数据结构，它没有一定的排列顺序，但是每个节点内都有指向下一个节点的指针，即使是在java里也是一样的。使用链表可以不用预先设置大小，但是链表不能实现随机读取数据，每次读取数据总是要从根节点开始遍历。相比于数组，虽然数组能实现随机读取数据，但是也同时失去了不用预先设置大小的优点，可能会造成内存空间不必要的浪费！

在说会链表如何实现队列。首先我们需要创建一个链表的节点类。在节点类里面，我们首先要定义两个节点的属性，一个是节点内的节点数据对象，以及指向下一个节点的指针。在方法的定义中我定义了1、义对下一个节点的引用方法。2、定义获得下一个节点的数据对象的方法。3、定义在当前节点设置数据对象的方法。4、定义获得当前节点数据对象的方法。

代码实现如下：

package com.czh130717;
    
    public class LinkNode {
    	private Object ob;//节点内的数据对象
    	private LinkNode next;//对下一个节点的引用
    	
    	public LinkNode(Object ob){
    		this.ob=ob;
    	}
    	public LinkNode() {
    		
    	}
    	//定义对下一个节点的引用方法
    	public void setNext(LinkNode next){
    		this.next=next;
    	}
    	//定义获得下一个节点的数据对象的方法
    	public LinkNode getNext(){
    		return next;
    	}
    	//定义在当前节点设置数据对象的方法
    	public void setObj(Object obj){
    		this.ob=obj;
    	}
    	//定义获得当前节点数据对象的方法
    	public Object getnode(){ 
    		return ob; 
    		}
    
    }

定义完一个节点类，再次我们需要定义一个链表类。

链表类里，我们需要定义一个静态的根节点root，和尾节点last。并定义了一个链表添加数据对象的功能

//定义添加功能
    		public void add(Object ob){	
    			LinkNode lin=new LinkNode(ob);
    			if(null==root){					
    				root=lin;
    				last=root;
    			}
    			else{
    				last.setNext(lin);
    				last=lin;
    			}
    		}

其中Object ob是我们需要添加的节点数据对象，我们要实例化一个节点对象来存储这个节点数据对象，其次我们要判断链表是否为空，即链表的根节点是否为空，如果root为空，则将该存储了要添加的数据对象的节点设为根节点，并将其设置为尾节点。如果根节点不为空，则将要添加的节点直接调用节点类的定义下一个节点的方法，将其设为last节点的下一个节点，并将该节点设置为最后一个节点。如此反复添加即可。

其次我还实现了查询功能。

//定义查询功能,获取节点的功能
    		public LinkNode get(int index){
    				LinkNode lin=root;
    				int c=0;
    				while(c!=index){					
    					lin=lin.getNext();											
    					c++;					
    				}
    				return lin;
    		}

首先该查询功能是根据要查询数据的索引位置来查询的，当然我们也可以根据要查询数据的具体值来查询。查询，自然要从根节点开始遍历，当遍历到要查询的数据，返回其值即可。

插入功能的实现

//定义一个插入功能,插入第index个节点之后
    		public void insert(Object ob,int index){
    			LinkNode lk=new LinkNode(ob);
    			LinkNode node1=this.get(index-1);
    			LinkNode node2=this.get(index);			
    			if(root==null){
    				root=lk;
    			}
    			else{				
    				node1.setNext(lk);
    				lk.setNext(node2);
    				}			
    			}

插入功能的实现，无可厚非，便是根据要插入节点的索引值，将其上一个节点直接指向要插入的节点，并将该节点指向下一个节点，自然便实现了插入功能。但是要注意的当节点插入在头尾的位置时，其实没有父节点和子节点的！这个情况要注意！

删除功能

//删除功能；删除指定位置的节点
    		public void remove(int index){
    			if(index==0){
    				root=this.get(index+1);
    			}else{
    			   this.get(index-1).setNext(this.get(index+1));
    		}
    			count--;
    		}

获取队列长度

//得到长度功能 
    		public int getLength(){ 
    		int length=0; 
    		LinkNode node=root; 
    		while(node!=null){ 
    		node=node.getNext(); 
    		length++; 		
    		} 
    		System.out.println(length);
    		return length; 		
    		}

打印功能

//定义一个打印功能
    		public void print(LinkNode root){ 
    			if(null != root){
    			Object data=root.getnode();
    			System.out.println(data); 			
    			LinkNode node=root.getNext();
    			print(node);			
    		} else{
    			return;
    		}
    			System.out.println();
    		}}

让队列实现打印功能，我们需要循环遍历队列，每取出一个节点数据对象便打印一次即可！

最后我创建了一个学生类继承该队列类，实现了所有功能！

代码如下：

package com.czh130717;
    
    public class Student extends LinkList {
    	public static void main(String[] args){
    		LinkList ls=new Student();
    		ls.add("李月迪");				
    		ls.add("蔡佳");
    		ls.add("周一帆");
    		ls.add("陈国辉");
    		ls.add("胡哥");
    		ls.add("刘培森");
    		ls.add("段亚辉");
    		ls.print(root);
    		System.out.println();
    		ls.insert("淳震华", 1);
    		ls.print(root);			
    		ls.remove(0);
    		ls.print(root);			
    		ls.getLength();						
    }
    }