前面翘的链表是单向的,也就是只能从一头开始遍历和操作,每个节点用next关联到下一个节点,今天把双向的敲了一下,双向的就多了一个previous,用它来关联它的上一个节点,这样,链表可以实现从前面操作,也可以从后面操作,单向的链表也就是只有一个头,双向的链表就是两个头,从哪个头都可以对连彼岸进行操作,所谓的操作也就是插入,删除,遍历,打印,等等等等
下面是代码,还是老样子,先是节点类登场,和单向的节点类唯一的区别就是多了一个用来关联前面节 点 的节点。
public Link previous; //定义指向前一个节点
具体代码如下:
package 双向链表; /* * 节点类,封装了属性 * @author TMS * */ public class Link { public long data; public Link next; //定义指向下一个节点 public Link previous; //定义指向前一个节点 /* * 初始化节点的属性 */ public Link(long data) { this.data = data; } /* * 打印出每个节点的信息 */ public void displayLink() { System.out.println("data = "+data); } }
接下来是双向链表的类:里面主要的方法有,
public boolean isEmpty() //判断链表是否为空 public void insertFirst(long value) //从前面插入 public void insertLast(long value) //从后面插入 public Link deleteFirst() //删除前面头的节点 public Link deleteLast() //删除后面头的节点 public boolean insertAftre(long key, long value) //插入到指定节点的后面 public Link deletekey(long key) //删除指定的节点 public void displayFd() //从前面遍历打印 public void displayBd() //从后面遍历打印
下面是具体的代码实现:
package 双向链表; public class DoubleLink { private Link first; private Link last; public DoubleLink() { first = null; last = null; } public boolean isEmpty() { return first == null; } /* * 在头节点插入 */ public void insertFirst(long value) { Link newLink = new Link(value); if (isEmpty()) { //进行判断如果为空,last为newLink,因为这是从前面插入,所以要求是last为newLink last = newLink; } else first.previous = newLink; //不为空的时候,first前'指针'指向新节点 newLink.next = first; //新节点指向原来的头 first = newLink; //从新将头放到最前面 } /* * 在尾节点插入 */ public void insertLast(long value) { Link newLink = new Link(value); if (isEmpty()) { first = newLink; } else { last.next = newLink; newLink.previous = last; } last = newLink; // / } /* * 删除头节点 */ public Link deleteFirst() { Link temp = first; if (first.next == null) { //如果只有一个节点 last = null; //和上面的从头插入一样,让他的尾节点为空。(这种情况是头和尾在一起) } else { first.next.previous = null; //其他情况下,让头节点的下一个节点的前面的节点为空,也就是原来的头节点为空 first = first.next; //将头节点移到下一个节点处 } return temp; //返回删除的 } /* * 删除节点 */ public Link deleteLast() { Link temp = last; if (first.next == null) { first = null; } else { last.previous.next = null; last = last.previous; } return temp; } /* * 在指定的节点后面插入一个新的节点,key值是原来链表中就有的,用来定位,value是新插入节点的值 */ public boolean insertAftre(long key, long value) { Link current = first; while (current.data != key) { //遍历到链表中相应的key处。 current = current.next; if (current.next == null) { return false; // 没找到 } } Link newLink = new Link(value); //初始化新的节点 if (current == last) { //如果到key是最后的尾节点 newLink.next = null; //新节点的next为空 last = newLink; //last定位到最后新插入的节点处 } else { //key在头或中间的时候 newLink.next = current.next; //新节点的next等于key对应的当前节点(current)的next current.next.previous = newLink; //当前key对应的节点的next节点的previous(前节点)指向新的节点 } newLink.previous = current; //通过上面的一连串之后,最后将新节点的previous指向key对应的当前节点(current) current.next = newLink; //当前节点(key对应)的next指向新的节点 return true; } /* * 删除指定 值的节点 key为节点对应的值 */ public Link deletekey(long key) { Link current = first; while (current.data != key) { //遍历链表锁定到key对应的节点处 current = current.next; if (current == null) { //到最后了都没有找到相应的节点 return null; // 没找到返回null } } if (current == first) { //经过遍历如果在第一个节点处 first = first.next; //将头节点移到下一个节点处 } else { //其他的情况下,当前节点的上一个节点的下一个节点 指向当前的节点的下一个节点 current.previous.next = current.next; } if (current == last) { //经过遍历如果在尾节点处 last = current.previous; //直接将尾节点移动到当亲节点的前一个节点处 } else { //其他情况下,也就是key对应的节点在链表中间的时候 current.next.previous = current.previous; //当前节点的下一个节点的前一个节点指向当前节点的前一个节点,跳过了当前节点 } return current; } /* * 从头节点开始打印链表的数据 */ public void displayFd() { System.out.println("从头往后面打印节点"); Link current = first; while (current != null) { //从头开始遍历 current.displayLink(); current = current.next; } } /* * 从尾节点开始打印链表的数据 */ public void displayBd() { System.out.println("从后往前打印节点"); Link current = last; while(current != null) { //从尾节点开始遍历 current.displayLink(); current = current.previous; } } /* * 测试方法 */ public static void main(String[] args) { DoubleLink dl = new DoubleLink(); //从前面插入节点 dl.insertFirst(1); dl.insertFirst(2); dl.insertFirst(3); //从前面打印节点 dl.displayFd(); //从后面插入节点 dl.insertLast(4); dl.insertLast(5); dl.insertLast(6); //从前面和后面打印节点 dl.displayFd(); dl.displayBd(); System.out.println("删除节点:"); //从前面和后面打印节点 dl.deleteFirst(); dl.deleteLast(); dl.displayFd(); dl.displayBd(); //在链表中找到相应的值再在后面插入节点 dl.insertAftre(1, 1222); dl.displayFd(); } }
PS:
以上的方法基本包括了链表操作的所有的方法,只是基本,我暂时不知道链表还能怎么玩,一天一天的 写, 最大的感受就是自己越来越爱写注释了,希望把每一步都能写清楚,这应该也是一点进步哈。
洗洗睡觉,又那么晚了⊙﹏⊙。
相关推荐
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
创建空的双向链表; 逐字符读取键盘输入的合法字符串,并依次插入到双向链表中。具体的,对于当前读取的字符, 构造其对应的结点。 利用头插法(或尾插法)将该结点按照键盘输入的顺序插入到双向链表中。 3、...
C++经典算法 双向链表 采用了结构体,链表的知识。
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表
双向链表
算法学习:双向链表的创建和读取
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
package 单双向链表; /** * 单向链表增删改查操作 * */ public class LinkTest { public static void main(String[] args) { Link l=new Link(); l.addNode("A"); l.addNode("B"); l.addNode("C"); l....
Java 有序 非循环 双向 链表 算法 实例
双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成...
详细的介绍了Linux内核中使用的最频繁的双向链表
双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
实现了通用的双向链表的所有操作,可以适用于各种数据结构,并配备了内存检漏算法,保证内存不泄露。
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及左结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
通过建立双向链表,来实现双向查找,增加和删除的功能
双向链表的API和C语言实现,程序说明在我的专栏《数据结构与算法学习笔记》中双向链表相关文章。包含了双向链表的结点结构体、表头结构体、创建双向链表、销毁双向链表、获取链表长度、清空双向链表、插入一个节点...
实现双向链表的增删改查功能,dos窗口输入输出,可运行,有注释
经典的双向链表排序算法。涵盖创建,删除,排序,获取,增加等
用双向链表实现大数阶乘 输入一个不限制大小的数 即可计算出它的阶乘