java总结之 链表实现队列

       链表在我看来就是一种基础的数据结构，它没有一定的排列顺序，但是每个节点内都有指向下一个节点的指针，即使是在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();						
}
}