`

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

 
阅读更多

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

 

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

 

 

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,如果没要求,操作的过程中尽量不要破坏链表的原始结构;如果破坏链表的结构是目前较好的一种实现方式,那么处理完数据后,一定要记得还原链表的原始数据结构;

     

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

分享到:
评论

相关推荐

    队列的链表与数组分别实现

    本篇文章将深入探讨如何用数组和链表两种数据结构来实现队列。 ### 数组实现队列 数组实现队列的优势在于访问速度快,因为数组是连续存储的,可以通过下标直接访问元素。但数组的大小是固定的,所以在创建时需要...

    数据结构 链表 队列 堆栈

    完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public:

    数组和链表实现队列

    本话题主要探讨了两种常用的数据结构——数组和链表——在实现队列这一线性数据结构时的应用。队列是一种先进先出(First In First Out, FIFO)的数据结构,它的主要操作包括入队(enqueue)、出队(dequeue)以及...

    循环链表队列 循环数组队列的代码实现

    ### 循环链表队列与循环数组队列的代码实现解析 在计算机科学中,队列是一种重要的数据结构,遵循先进先出(FIFO)原则。队列可以使用多种方式实现,包括链表和数组。本文将深入探讨两种队列实现方式:循环链表队列...

    数组、链表、队列、栈数据结构特点,各自优点和缺点 数组和链表.pdf

    数组、链表、队列、栈数据结构特点,各自优点和缺点 在计算机科学中,数据结构是指用于组织和存储数据的方式。常见的数据结构包括数组、链表、队列、栈等。每种数据结构都有其特点、优点和缺点,本文将对这些数据...

    算法大全-面试题-链表-栈-二叉树-数据结构

    链表是一种线性数据结构,与数组不同,它的元素在内存中不是连续存储的。链表由一系列节点组成,每个节点包含数据和指向下一个节点的引用。链表分为单向链表、双向链表和循环链表等类型,它们各有优缺点,如单向链表...

    go语言通过数组和链表的方式实现队列 数组和链表.pdf

    "go语言通过数组和链表的方式实现队列" 从给定的文件信息中,我们可以生成以下知识点: 1.队列的定义:队列是一种特殊的线性表,只能在队列的尾部添加元素,在队列的头部删除元素,先进先出(FIFO)。 2.go语言中...

    一个结合链表与数组于一体的高效数据管理类

    这种数据结构通常用在需要频繁添加或删除元素的场景,例如在实现栈、队列或者在处理不确定数量的数据时。 在这个高效数据管理类中,可能采用了类似“动态数组”的机制,当链表节点数超过一定阈值时,会转换为数组...

    Java版数据结构代码,栈,动态数组,队列,链表,二叉树

    在队列的代码中,引用了链表的代码

    数据结构之链表栈与队列

    在某些场景下,链表栈和链表队列相比数组实现的栈和队列,能更好地处理动态变化的大小需求。 在实际编程中,我们可能需要对这些数据结构进行优化,例如,循环链表可以避免空指针问题,提高效率;链表栈和链表队列...

    数据结构中链表,栈和队列,串的算法实现代码

    链表、栈、队列和串(字符串)是数据结构中的基本概念,这里我们将深入探讨它们以及相关的算法实现。 首先,链表是一种非连续的数据存储结构,其中每个元素称为节点,包含数据和指向下一个节点的引用。链表分为单向...

    数组、链表、队列、栈的区别和联系 数组和链表.pdf

    在数据结构中,数组、链表、队列、栈是四种常用的数据结构,它们之间有着紧密的联系,但同时也存在着许多区别。本文将详细介绍数组、链表、队列、栈的区别和联系。 一、数组和链表的区别 数组和链表都是线性表数据...

    数据结构(表,链表,栈,队列)的源代码

    这里我们将探讨标题和描述中提到的四种数据结构:表、链表、栈和队列,并结合源代码的学习来理解它们。 1. **表**(Array):表是最基础的数据结构,它是一个固定大小的数组,用于存储同类型的数据。在C语言中,...

    C语言数组形链表实现

    在C语言中,数组形链表是一种特殊的数据结构,它结合了数组的高效访问和链表的灵活扩展性。这种数据结构通常用于处理动态数组,其中元素可以方便地添加或删除,而不需要像传统数组那样预先知道确切的大小。本文将...

    数据结构:线性表、链表、队列、栈、串

    本主题将深入探讨线性表、链表、队列、栈这四种基本的数据结构,并以C++语言为例,通过相关源代码(stringData.cpp、seqList.cpp、node.cpp、seqQueue.cpp、linkQueue.cpp、linkStack.cpp、seqStack.cpp)来解析其...

    数据结构的链表,队列,栈(c)

    链表是一种线性数据结构,与数组不同,它不连续存储元素。每个元素称为节点,包含数据和指向下一个节点的引用(或指针)。链表有多种类型,如单向链表、双向链表和循环链表。在单向链表中,每个节点只能向前指向一个...

    C中数据结构(链表,队列,栈的练习)

    链表是一种线性数据结构,与数组不同,它不连续存储元素。每个元素称为节点,包含两部分:数据域(存储信息)和指针域(指向下一个节点的地址)。链表的主要类型有单链表、双向链表和循环链表。在单链表中,我们通常...

    数据结构顺序表、链表和数组是逻辑结构还是物理(存储)结构? 数组和链表.pdf

    数据结构顺序表、链表和数组是逻辑结构还是物理(存储)结构? 数据结构是计算机科学中的一门重要学科,它研究的是计算机中数据的组织、存储和处理方式。数据结构可以分为逻辑结构和物理结构两种。 逻辑结构是指...

Global site tag (gtag.js) - Google Analytics