数据结构之链表与数组(一)—链表实现队列
用数组实现了队列之后,我们一样可以通过链表来实现队列,下面是代码示例。
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:
数据结构的定义 数据结构是计算机存储、组织数据的方式,用于高效地访问和修改数据。...Java提供了丰富的数据结构库,包括数组、链表、栈、队列等,这些数据结构为程序员提供了处理各种问题的工具和方法。
数组、链表、队列、栈数据结构特点,各自优点和缺点 数组和链表.pdf
go语言通过数组和链表的方式实现队列 数组和链表.pdf
在队列的代码中,引用了链表的代码
常见的数据结构(栈、队列、数组、链表和红黑树) 数组和链表.pdf
这份资料里面讲解的很清楚详细,易懂,对正在学习编程的同学特别是对正在找工作的同学非常有帮助。
目录: 数据结构中的一些概念 栈(stack) 队列 链表 python中字典对象实现原理 数组 一. 数据结构中的一些概念 1、数据结构是什么 简单来说,数据结果就是设计数据以何种...数据结构:数组、栈、队列、链表、树、图、
链表是一种链式数据结构,由若干节点组成,每个节点包含指向下一个节点的指针。链表的物理存储方式是随机存储,访问方式是顺序访问。查找链表节点的时间复杂度是O[n],中间插入、删除节点的时间复杂度是O(1)。 栈 栈...
线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf
包含数据结构中线性表、链表、队列、栈、串等几种结构的常见操作,以及顺序和链式存储过程
C语言数据结构链表队列的实现 1.写在前面 队列是一种和栈相反的,遵循先进先出原则的线性表。 本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。 分解代码没有包含在内的代码如下: #include #...
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
数据结构实验报告+代码(链表 二叉树 图 字符串 数组 排序 队列 栈)
c语言数组指定位置插入和删除-玩转C语言链表,单链表双向链表的建立遍历插入删除... 数组和链表.pdf
进行多项式运算,运用链表,队列,数组等数据结构。
利用C++实现以下经典数据结构与算法:线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法...
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
基于JAVA实现的常用数据结构代码,JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等