步印（一） JAVA链表和队列的的学习了解

    在开始讨论链表和队列前，先回顾一下课堂上讲授的数组内容。数组是java中最基本的数据结构，可以将其理解为一个容器，即可以用数组来装东西。但数组这个这个容器，在其定义的时候，它的长度就是固定的了。因此，在使用的时候，难免会有各种限制，这样的代码是死板呆滞。由此 ，引入了队列和链表这两种数据结构，它们和数组最大区别是：可以实现自动增长。

    新建一个一个队列类，可以定义其初始的长度(容量)和每次增加的个数，添加,插入,删除元素及返回队列长度的方法。

public class Queue3 {
	//数组的初始长度和每次增加个数
	private int initLen;
	private int increaseNum;
	//设置一个计数器,初始值为0,用来检测数组是否越界，也作为测量队列长度
	private int count = 0;
	//长度为 initLen的数组
	int [] oldQ = new int[initLen];
	Queue3(int initLen, int increaseNum){
		this.initLen = initLen ;
		this.increaseNum = increaseNum;
	}
	Queue3(){
		this(3,3);          
	}
	//数组添加元素的方法
	public void add(int o){
		//判断是否出现越界
		if(count < oldQ.length){
			oldQ[count] = o;
			count++;
		}else{
			//一个新数组,长度为原数组+increaseNum
			int [] newQ = new int[oldQ.length+increaseNum];
			//新数组赋值
			for(int i=0;i < oldQ.length ;i++){
				newQ[i] = oldQ[i];
			}
			newQ[oldQ.length] = o;
			count++;
			//两数组互换
			oldQ = newQ;
		}
	}
	//返回数组中的值的方法
	public int get(int index){
		return oldQ[index];
	}
	//删除数组中指定位置的值的方法
	public int delete(int index){
		int tmp;
		//判断位置是否有效
		if(index <0 && index >= oldQ.length){
			 tmp=99999999;
		}else{
			int [] newQ = new int[oldQ.length-1];  
			tmp = oldQ[index];
			for(int i=0 ; i < index ; i++){
				newQ[i] = oldQ[i];
			}
			for(int i=index;i < oldQ.length-1 ;i++){
				newQ[i] = oldQ[i+1];
			}
			//
			oldQ = newQ;
		}
		return tmp;
	}
	//在指定位置插入元素的方法
	public void insert(int index,int o){
		//判断index的位置是否合法
		if(index < 0 && index >= oldQ.length){			
		}else {
		   //新建一个长度+1的数组
			int newQ [] = new  int[oldQ.length+1];
			//新数组赋值
			newQ[index] = o ;
			for(int i=0;i < index; i++){
			newQ[i] = oldQ[i] ;
			}
			for( int i= index+1; i<oldQ.length;i++){
			newQ[i] = oldQ[i-1];
			}
			//交换
			oldQ=newQ;
		}		
	}
	//求长度的方法
	public int size(){
		return oldQ.length;
	}
}

    实际上，队列就是对数组的一个升级版，他们都是顺序存储结构的。而链表是链式存储结构。实现链表，我用了两个类，Node类和 List类。

public class Node1 {
		private int data;
		private Node1 next;
		//设置节点的数据
		public void setData(int o){
			this.data = o;
		}
		public int getData(){
			return data;
		}
		//设置下一个节点
		public void setNext(Node1 n){
			this.next = n;
		}
		//返回下一个节点
		public Node1 getNext(){
			return this.next;
		}
		
}
public class List1 {
	//链表的属性，头节点	
	private Node1 root;
	//链表的最后一个节点
	private Node1 tail;
	public List1(Node1 root,Node1 tail) {	
		this.root = root;
		this.tail = tail;
	}
	public void setRoot(Node1 n){
		root=n;
	}
	//链表添加节点
	public void add(Node1 n){
		if( root.equals(tail) ){
			root.setNext(n);
			tail = n;
		}else{
			tail.setNext(n);
			tail = n;
		}		
	}
	//找到指定位置的节点
	public Node1 Query(int index){
		Node1 tem = root ;
		while(index > 0){
			tem = tem.getNext();
			index--;
		}
		return tem;
	}
	//返回指定节点的值
	public int getData(int index){
		return this.Query(index).getData();
	}
	//链表在指定位置后面插入节点
	public void insert(Node1 n , int index){		
		//定位到指定位置的节点
		Node1 n0 = this.Query(index);
		//n指向n0的下一个
		n.setNext( n0.getNext() );
		//n0指向n
		n0.setNext(n);
	}
	//删除指定位置的节点,并返回其内容
	public int delete(int index){
		//找到指定位置的节点
		Node1 n =this.Query(index);
		//如果要删除头节点，则把第二个节点设为头节点
		if(index ==0){
			root = root.getNext();
		}else{
			//找到指定位置的前一个节点
			Node1 n0 = this.Query(index-1);
			//找到指定位置的后一个节点
			Node1 n1 = this.Query(index+1);
			//删除
			n0.setNext(n1);
		}
		//返回删除节点的内容
		return n.getData();
		//从安全角度考虑，把删除的n指向空,但会报错
		//n.setNext(null);
	}
} 

   接着 ，就可以测试比较队列和链表了。主要比较的是他们 查找 、 插入、  删除性能上的差异。从理论上来分析，队列是顺序结构，数据是一个挨着一个存储的，就像战士们排成一队，链表就相当于一跟线把数据给串起来，不难想象，在查找上，队列的肯定比链表快。而在插入和删除上，和现实生活中类似，插队等举动总是让队伍越派越长，插入和删除在队列中的实现比较麻烦。而链表就如同把一根绳剪断，在断处用新的接上，所以实现起来很快。

   究竟是怎样，可以编程来直观地体现。借助System.currentTimeMillis()方法，该函数返回1970年1月1日0时起的毫秒数，因此可以在代码的头和尾都设置这么一个函数，就可以求出这段代码的运行时间了。

   测试队列

public class TestQ3 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//生成一个队列
		Queue3 q = new Queue3(0,1);
		for(int i=0; i< 100000 ;i++){
			q.add(i);
		}		
		//查找
		Random rand = new Random();
		long start1=System.currentTimeMillis();
		for(int i=0;i <= 1000; i++){
			int x=rand.nextInt(99999);
			q.get(x);
		}
		long end1=System.currentTimeMillis();
		long cost1 = start1 - end1;
		System.out.println("返回时间"+cost1);
		//插入
		long start2=System.currentTimeMillis();
		for(int i=0;i <= 1000; i++){
			int x=rand.nextInt(99999);
			q.insert(x, 0);
		}
		long end2=System.currentTimeMillis();
		long cost2 = end2 - start2 ;
		System.out.println("插入时间"+cost2);
		//删除
		long start3=System.currentTimeMillis();
		for(int i=0;i <= 1000; i++){
			int x=rand.nextInt(99990-i);
			q.delete(x);
		}
		long end3=System.currentTimeMillis();
		long cost3 = end3 - start3 ;
		System.out.println("删除使用时间"+cost3);
		
	}
}

    测试链表

public class NodeTest1 {
	public static void main(String [] args){
		Node1 n0 = new Node1();
		n0.setData(0);
		List1 l = new List1(n0,n0);
		//生成包含10w个节点的链表		
		for(int i=1 ; i<= 100000; i++){
			Node1 n = new Node1();
			n.setData(i);
			l.add(n);
		}		
		//返回节点的值
		Random rand = new Random();
		long start1=System.currentTimeMillis();
		for(int i=0;i <= 1000; i++){
			int x=rand.nextInt(99999);
			l.getData(x);
		}
		long end1=System.currentTimeMillis();
		long cost1 = start1 - end1;
		System.out.println("查找使用时间"+cost1);
		//插入
		long start2=System.currentTimeMillis();
		Node1 n = new Node1();
		for(int i=0;i <= 1000; i++){
			int x=rand.nextInt(99999);
			l.insert(n, x);
		}
		long end2=System.currentTimeMillis();
		long cost2 = end2 - start2 ;
		System.out.println("插入使用时间"+cost2);
		//删除
		long start3=System.currentTimeMillis();
		for(int i=0;i <= 1000; i++){
			int x=rand.nextInt(80000);
			l.delete(x);
		}
		long end3=System.currentTimeMillis();
		long cost3 = end3 - start3 ;
		System.out.println("删除使用时间"+cost3);
	}
}

    结果是         队列                       链表
            查找    1                          165                         
            插入   853                        54
            删除   846                        472  

  此结果和之前的理论分析是一致的。

  这就是队列和链表的简单应用和分析了。在听课时，老师还谈到，删除节点时，为了安全，应把所删节点指向空值，但我设置它指向空的话，会报错。不知道这该怎么做，望各路过大牛指导。