今天我想跟大家来唠叨一下双向链表,何为双向链表?简而言之,每个结点存储两个链,并允许双向遍历的链表称为双向链表。我对于链表的理解是这样的,一个结点类,一个位置类,一个链表本身类。
一、结点类
public class DoubleLinkNode { public String iData; //前一个结点 public DoubleLinkNode prev; //后一个结点 public DoubleLinkNode next; public DoubleLinkNode(String iData){ this(iData,null,null); } public DoubleLinkNode(String iData, DoubleLinkNode dln, DoubleLinkNode dln2) { this.iData=iData; this.prev=dln; this.next=dln2; } }
这个类比较简单,没什么好说,对于第二个构造器,主要是为了使后面结点之间的连接更简洁。你也可以不用这个构造器。
二、位置类(迭代器类)
public class DbLinkListIterator { //标识当前的位置 DoubleLinkNode current; DbLinkListIterator(DoubleLinkNode dln) { current=dln; } //判断当前位置是否有效 public boolean isValid(){ return current!=null; } //向前行进 public void advace(){ if (isValid()) { current=current.next; } } //向后倒退 public void back(){ if (isValid()) { current=current.prev; } } //返回当前位置的标识符 public String retrieve(){ if (isValid()) { return current.iData; } return null; } }
这个类主要用来反馈链表当前的位置,如果你不想单独建这个类,你可以把它放在链表本身类的内部。但是本人觉得把它单独抽象出来成一个类,结构会更加的清晰。
三、链表本身类
public class LinkList_Double { //头结点 private DoubleLinkNode header; //尾结点 private DoubleLinkNode tail; //初始化头尾结点 public LinkList_Double() { header=new DoubleLinkNode("header"); tail=new DoubleLinkNode("tail",header,null); header.next=tail; } //判断双向链表是否为空 public boolean isEmpty(){ return header.next==tail||tail.prev==header; } //第一个结点之前的位置 public DbLinkListIterator zero(){ return new DbLinkListIterator(header); } //第一个结点的位置 public DbLinkListIterator first(){ if (!isEmpty()) { return new DbLinkListIterator(header.next); } return new DbLinkListIterator(header); } //最后一个结点的位置 public DbLinkListIterator last(){ if (!isEmpty()) { return new DbLinkListIterator(tail.prev); } return new DbLinkListIterator(tail); } //指定位置之后插入方法 public void insertAfter(String obj,DbLinkListIterator pos){ if (pos!=null&&pos.current!=null) { DoubleLinkNode newDoubleLinkNode=new DoubleLinkNode(obj,pos.current,pos.current.next); newDoubleLinkNode.prev.next=newDoubleLinkNode; newDoubleLinkNode.next.prev=newDoubleLinkNode; } } //指定位置之前插入方法 public void insertBefore(String obj,DbLinkListIterator pos){ if (pos.current!=header&&pos!=null&&pos.current!=null) { DoubleLinkNode newDoubleLinkNode=new DoubleLinkNode(obj,pos.current.prev,pos.current); newDoubleLinkNode.prev.next=newDoubleLinkNode; newDoubleLinkNode.next.prev=newDoubleLinkNode; } } //查找方法 public DbLinkListIterator find(String key){ DoubleLinkNode itr=header.next; while (itr!=null) { if (itr.iData.equals(key)) { return new DbLinkListIterator(itr); } itr=itr.next; } return null; } //删除方法 public void delete(String key){ DbLinkListIterator itr=find(key); if (itr==null) { System.out.println("不存在该关键字"); return; } itr.current.prev.next=itr.current.next; itr.current.next.prev=itr.current.prev; } //向前显示 public void displayBofore(){ if (isEmpty()) { System.out.println("该双向链表为空"); }else { DbLinkListIterator itr=first(); while (itr!=null&&!itr.retrieve().equals("tail")) { System.out.print(itr.retrieve()+" "); itr.advace(); } } } //向后显示 public void displayAfter(){ if (isEmpty()) { System.out.println("该双向链表为空"); }else { DbLinkListIterator itr=last(); while (itr!=null&&!itr.retrieve().equals("header")) { System.out.print(itr.retrieve()+" "); itr.back(); } } } }
为了方便,作者的想法是虚构两个结点,即头结点、尾结点,这样做的好处就是能够保证每次插入有效结点时,它的前后都有结点,这样就少了许多的条件判断。当然双向链表本身的方法肯定不止这么一点,我只是大概的列举了一些。
四、测试类
public class LinkList_doubleTest { public static void main(String[] args) { LinkList_Double linkList_Double=new LinkList_Double(); //插入第一个结点 linkList_Double.insertAfter("a", linkList_Double.zero()); //在指定结点之后插入 linkList_Double.insertAfter("b", linkList_Double.find("a")); linkList_Double.insertAfter("c", linkList_Double.find("b")); //在指定结点之前插入 linkList_Double.insertBefore("e", linkList_Double.find("b")); linkList_Double.insertBefore("f", linkList_Double.first()); //删除指定结点 linkList_Double.delete("f"); //顺序显示 linkList_Double.displayBofore(); //逆序显示 linkList_Double.displayAfter(); } }
最后,作者也是正在学习的过程中,自然还有很多 考虑不周全的地方,如有,还请见谅,并希望您能指出我的不足之处,大家一起学习、进步。
相关推荐
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
一个简洁而又优雅的Android原生UI框架,解放你的双手!还不赶紧点击使用说明文档,体验一下吧! 涵盖绝大部分的UI组件:TextView、Button、EditText、ImageView、Spinner、Picker、Dialog、PopupWindow、ProgressBar、LoadingView、StateLayout、FlowLayout、Switch、Actionbar、TabBar、Banner、GuideView、BadgeView、MarqueeView、WebView、SearchView等一系列的组件和丰富多彩的样式主题。
基于背向散射的超声骨密度仪算法研究和软件设计的任务书.docx
机械毕业设计81五自由度机械臂设计.doc
数据可视化-上海各地区风速热力图
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
RBF神经网络概述.doc
游戏植物大战僵尸(经典版)
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
基于s7200自动售货机-plc-控制.doc
基于深度学习方法去评估锂电池健康状态(SOH)python源码.zip对象是NASA的锂电池容量衰退数据集,本资源中的源码都是经过本地编译过可运行的,评审分达到95分以上。资源项目的难度比较适中,内容都是经过助教老师审定过的能够满足学习、使用需求,如果有需要的话可以放心下载使用。 基于深度学习方法去评估锂电池健康状态(SOH)python源码.zip对象是NASA的锂电池容量衰退数据集,本资源中的源码都是经过本地编译过可运行的,评审分达到95分以上。资源项目的难度比较适中,内容都是经过助教老师审定过的能够满足学习、使用需求,如果有需要的话可以放心下载使用。基于深度学习方法去评估锂电池健康状态(SOH)python源码.zip对象是NASA的锂电池容量衰退数据集,本资源中的源码都是经过本地编译过可运行的,评审分达到95分以上。资源项目的难度比较适中,内容都是经过助教老师审定过的能够满足学习、使用需求,如果有需要的话可以放心下载使用。 基于深度学习方法去评估锂电池健康状态(SOH)python源码.zip对象是NASA的锂电池容量衰退数据集,本资源中的源码都是经过本地编译过可运行的,评审分
电脑工具.txt
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
移动机器人机械臂的设计小论文.doc
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
C语言诞生于美国的贝尔实验室,由丹尼斯·里奇(Dennis MacAlistair Ritchie)以肯尼斯·蓝·汤普森(Kenneth Lane Thompson)设计的B语言为基础发展而来,在它的主体设计完成后,汤普森和里奇用它完全重写了UNIX,且随着UNIX的发展,c语言也得到了不断的完善。为了利于C语言的全面推广,许多专家学者和硬件厂商联合组成了C语言标准委员会,并在之后的1989年,诞生了第一个完备的C标准,简称“C89”,也就是“ANSI C”,截至2020年,最新的C语言标准为2018年6月发布的“C18”。 [5] C语言之所以命名为C,是因为C语言源自Ken Thompson发明的B语言,而B语言则源自BCPL语言。 1967年,剑桥大学的Martin Richards对CPL语言进行了简化,于是产生了BCPL(Basic Combined Programming Language)语言。
【资源说明】 C++基于OpenCV对图片进行识别+裁剪源码+使用文档+全部资料(优秀项目).zipC++基于OpenCV对图片进行识别+裁剪源码+使用文档+全部资料(优秀项目).zipC++基于OpenCV对图片进行识别+裁剪源码+使用文档+全部资料(优秀项目).zip 【备注】 1、该项目是个人高分毕业设计项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(如软件工程、计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!
密码学实验报告2.docx