今天我想跟大家来唠叨一下双向链表,何为双向链表?简而言之,每个结点存储两个链,并允许双向遍历的链表称为双向链表。我对于链表的理解是这样的,一个结点类,一个位置类,一个链表本身类。
一、结点类
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(); } }
最后,作者也是正在学习的过程中,自然还有很多 考虑不周全的地方,如有,还请见谅,并希望您能指出我的不足之处,大家一起学习、进步。
相关推荐
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表
双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成...
双向链表
定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及左结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
详细的介绍了Linux内核中使用的最频繁的双向链表
双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
实现双向链表的增删改查功能,dos窗口输入输出,可运行,有注释
C 语言版 双向链表 #include #include typedef struct list { int date; struct list *llink; struct list *rlink; }st; st *creat () //创建双向链表 { st *head , *p , *q; head = q = p = NULL; int ...
通过建立双向链表,来实现双向查找,增加和删除的功能
双向链表是一种比较常用的数据结构,在许多场合都有应用。但是,双向链表的节点操作,对于初学者来说或许显得比较繁琐。尤其是,当用链表描述不同的数据结构时,节点结构体的定义都是不同的,这就需要为每一种链表都...
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
原创手操,操作系统课设,线程安全的双向链表,VC6.0,无须配置,可运行
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
用模板类实现了一个简单的双向链表domo。
用双向链表实现大数阶乘 输入一个不限制大小的数 即可计算出它的阶乘
循环双向链表,实现了插入、查找特定的节点、删除等功能,是自己花了半天的时间写完的。
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
基础数据结构双向链表的C++描述版。实现了双向链表的基本功能。包括拷贝构造函数和IO操作符重载、赋值操作符重载
ALIST是一段基于C语言的数组型双向链表的处理代码,接口简单明了,易于使用,标准C语言开发,可添加在任何C/C++语言工程中,需要注意的是,如果使用了操作系统,请自行在库中修改指向处添加资源锁定,避免因操作系统...