在开始讨论链表和队列前，先回顾一下课堂上讲授的数组内容。数组是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实现复杂度、动态数组、链表、栈、队列、二叉搜索树等