步印（一） 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{//一个新数组,长度为原数组+increaseNumint [] 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指向nn0.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??

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

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

?