在开始讨论链表和队列前,先回顾一下课堂上讲授的数组内容。数组是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
此结果和之前的理论分析是一致的。
这就是队列和链表的简单应用和分析了。在听课时,老师还谈到,删除节点时,为了安全,应把所删节点指向空值,但我设置它指向空的话,会报错。不知道这该怎么做,望各路过大牛指导。
相关推荐
用java 队列 链表 栈不少老师大作业布置的就是这个,需要的同学就放心下载吧
arithmetic java算法冒泡排序、二叉树、数组、链表、队列学习简单示例 private static void mpSoft(String [] data) { for (int i = 0; i ; i++) { System.out.println(Arrays.toString(data)); for (int j = 0; ...
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法。(Java描述)
数据库与数据结构课程 堆栈链表与队列链表的基本操作函数,还有可供参考的可执行文件exe
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
内容和要求 单链表操作 和 栈、队列的... 4)定义一个顺序栈和循环队列,实现将队列中所有元素逆置。 实验数据:1)线性表为 6,2,11,5,2,4,2; 2)x=2; 3) k=5 或 k=10; 4)队列中的数据为 1,2,3,4,5,6
在队列的代码中,引用了链表的代码
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作,下面介绍一下java使用数组和链表实现队列的示例
基于c语言数据结构中栈和队列思想的简单停车场管理系统,以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车...
基于JAVA创建单链表,并实现了在队列末尾增加、删除元素,在队列中插入、删除元素,打印链表。
单链队列,详细内容见博文:http://blog.csdn.net/u013071074/article/details/27641665
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
- 学习数据结构和算法:了解常用的数据结构和算法,如数组、链表、栈、队列、排序算法等。 2. Web开发基础: - 学习HTML、CSS和JavaScript:掌握前端开发的基础知识,了解网页布局、样式设计和交互效果。 - 学习...
主要介绍了java链表应用--基于链表实现队列,结合实例形式分析了java基于链表实现队列尾指针相关操作使用技巧,需要的朋友可以参考下
Java_Stack_Queue Java中使用链表的堆栈和队列实现
JAVA实现链表 有序二叉树 队列的代码例子
面试中,经常要用到的数据结构(链表、队列、栈、二叉树、哈希表等)以及一些常用的算法(排序:归并、快速排序、基数排序等,查找:二分查找法),,统一由JAVA实现.
基于JAVA实现的常用数据结构代码,JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等