数据结构之链表与数组(二)—链表实现队列

数据结构之链表与数组(一)—链表实现队列

 

       用数组实现了队列之后，我们一样可以通过链表来实现队列，下面是代码示例。

 

 

import java.util.LinkedList;

/*
 * 先定义一个单向链表节点类，方便对链表的操作
 */
public class LinkNode {
	
	private Object obj;//节点内的数据对象
	private LinkNode next;//对下一个节点的引用
	//在创建节点对象的时候就传入节点的数据对象
	public LinkNode(Object obj){
		this.obj = obj ;
	}
	public void setObj(Object obj){
		this.obj = obj;
	}
	public Object getObj(){
		return obj;
	}
	
	public void setNext(LinkNode next){
		this.next = next;
	}
	public LinkNode getNext(){
		return next;
	}
	

}

 

 

 

链表对队列的操作功能在LinkList类中实现：

 

 

 

 

  

import java.security.acl.LastOwnerException;

import javax.swing.JOptionPane;
import javax.xml.soap.Node;

/*
 * 单向链表类，实现对队列的操作
 */
public class LinkList {

	/**定义属性
	 * @param args
	 */
	private static LinkNode root ;
	private static LinkNode last;
	
	
	/**
	 * 遍历输出链表的方法
	 * root: 链表的根节点
	 */
	public void printLinkList(LinkNode root){
		LinkNode node = root;
		while(node!=null){
			System.out.println(node.getObj()); 
			node = node.getNext(); 

		}
	}
	/**
	 * 计算队列长度
	 */
	public int getSize(){
		int n = 0;
		LinkNode temp = root;
		while( temp != null ){
			temp = temp.getNext();
			n++;
		}
		return n;
	}
	/**
	 * 在队列末尾添加数据
	 */
	public void  add(Object obj){
		//实例化一个新的节点对象，并将obj传入
		LinkNode node = new LinkNode(obj);
		if(null == root){
			root = node;
			last = root;
		}else{
			//将last指向node
			last.setNext(node);
			//节点node变为最后一个节点
			last = node;

		}
		
	}
	/**
	 * 取指定位置节点的数据,并返回该节点
	 */
	public LinkNode getNode(int index){
		//将根节点赋值给一个临时节点temp
		LinkNode temp = root;
		int count=1;
		while(count!=index){
			temp = temp.getNext();
			count++;
		}
		return temp;
	}
	/**
	 * 删除指定节点的数据
	 */
	public void remove(int index){
		//判断index是否超出队列范围
		if(index<1 || index>this.getSize()){
			System.out.println("超出队列范围！");
			
		}else{
			//当要删除的节点位于链表头和尾之间是
			if(index>1 && index<this.getSize()){
				//令该节点的上一节点指向其该节点的下一节点
				this.getNode(index-1).setNext(this.getNode(index+1));
			}
			//当要删除的节点是链表的头或者尾时
			if(1==index || this.getSize()==index){
				if(1==index){
					//将根节点前移
					root = this.getNode(index+1);
				}else {
					//将之后的节点设为空					
					this.getNode(index-1).setNext(null);
					
				}
			}
		}

	}
	/**
	 * 在指定位置插入数据，插入位置之后的数据向后移动
	 */
	public void insert(int index,Object obj){
		//实例化一个新的节点对象
		LinkNode node = new LinkNode(obj);
		//判断root是否为空
		if(null == root){
			root = node ;
		}else{
			//判断插入的位置
			if(1==index){
				//将node指向root
				node.setNext(root);
				root = node;
			}
			if(index>1 || index<=this.getSize()){
				//实例化两个临时节点，分别保存插入位置的前后节点
				LinkNode temp1 = this.getNode(index-1);
				LinkNode temp2 = this.getNode(index);
				//将链表重新连接
				temp1.setNext(node);
				node.setNext(temp2);
			}
		}
		
	}
}

 

 在处理链表问题时的公共注意点有：

1，要时刻考虑节点的指向是否为空；

2，不要把指针指向一些无效的地址空间；

3，如果没要求，操作的过程中尽量不要破坏链表的原始结构；如果破坏链表的结构是目前较好的一种实现方式，那么处理完数据后，一定要记得还原链表的原始数据结构；

     

        在数据结构的学习中，我深刻的体会到了在解决生活或计算机中的任何问题时“三思而后行”的道理都是非常实用的。只有想明白了，要做什么、怎么做，然后再着手去做，才能比较容易地解决问题。如果连要做什么，怎么做都不清楚，那现在所做的行动能成功的概论就非常小了。因此，要用计算机编码来解决一些问题的时候，不要急于编码，而是要先想清楚思路和注意点，然后再着手实现自己的思路。