数据结构之链表与数组(一)—链表实现队列
用数组实现了队列之后,我们一样可以通过链表来实现队列,下面是代码示例。
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)原则。队列可以使用多种方式实现,包括链表和数组。本文将深入探讨两种队列实现方式:循环链表队列...
数组、链表、队列、栈数据结构特点,各自优点和缺点 在计算机科学中,数据结构是指用于组织和存储数据的方式。常见的数据结构包括数组、链表、队列、栈等。每种数据结构都有其特点、优点和缺点,本文将对这些数据...
链表是一种线性数据结构,与数组不同,它的元素在内存中不是连续存储的。链表由一系列节点组成,每个节点包含数据和指向下一个节点的引用。链表分为单向链表、双向链表和循环链表等类型,它们各有优缺点,如单向链表...
"go语言通过数组和链表的方式实现队列" 从给定的文件信息中,我们可以生成以下知识点: 1.队列的定义:队列是一种特殊的线性表,只能在队列的尾部添加元素,在队列的头部删除元素,先进先出(FIFO)。 2.go语言中...
这种数据结构通常用在需要频繁添加或删除元素的场景,例如在实现栈、队列或者在处理不确定数量的数据时。 在这个高效数据管理类中,可能采用了类似“动态数组”的机制,当链表节点数超过一定阈值时,会转换为数组...
在队列的代码中,引用了链表的代码
在某些场景下,链表栈和链表队列相比数组实现的栈和队列,能更好地处理动态变化的大小需求。 在实际编程中,我们可能需要对这些数据结构进行优化,例如,循环链表可以避免空指针问题,提高效率;链表栈和链表队列...
链表、栈、队列和串(字符串)是数据结构中的基本概念,这里我们将深入探讨它们以及相关的算法实现。 首先,链表是一种非连续的数据存储结构,其中每个元素称为节点,包含数据和指向下一个节点的引用。链表分为单向...
在数据结构中,数组、链表、队列、栈是四种常用的数据结构,它们之间有着紧密的联系,但同时也存在着许多区别。本文将详细介绍数组、链表、队列、栈的区别和联系。 一、数组和链表的区别 数组和链表都是线性表数据...
这里我们将探讨标题和描述中提到的四种数据结构:表、链表、栈和队列,并结合源代码的学习来理解它们。 1. **表**(Array):表是最基础的数据结构,它是一个固定大小的数组,用于存储同类型的数据。在C语言中,...
在C语言中,数组形链表是一种特殊的数据结构,它结合了数组的高效访问和链表的灵活扩展性。这种数据结构通常用于处理动态数组,其中元素可以方便地添加或删除,而不需要像传统数组那样预先知道确切的大小。本文将...
本主题将深入探讨线性表、链表、队列、栈这四种基本的数据结构,并以C++语言为例,通过相关源代码(stringData.cpp、seqList.cpp、node.cpp、seqQueue.cpp、linkQueue.cpp、linkStack.cpp、seqStack.cpp)来解析其...
链表是一种线性数据结构,与数组不同,它不连续存储元素。每个元素称为节点,包含数据和指向下一个节点的引用(或指针)。链表有多种类型,如单向链表、双向链表和循环链表。在单向链表中,每个节点只能向前指向一个...
链表是一种线性数据结构,与数组不同,它不连续存储元素。每个元素称为节点,包含两部分:数据域(存储信息)和指针域(指向下一个节点的地址)。链表的主要类型有单链表、双向链表和循环链表。在单链表中,我们通常...
数据结构顺序表、链表和数组是逻辑结构还是物理(存储)结构? 数据结构是计算机科学中的一门重要学科,它研究的是计算机中数据的组织、存储和处理方式。数据结构可以分为逻辑结构和物理结构两种。 逻辑结构是指...