《数据结构之双向链表的Java实现》由会员分享，可在线阅读，更多相关《数据结构之双向链表的Java实现（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构之双向链表的 Java 实现单链表只能从前往后遍历，如果链表的长度较大，遍历到链表后半部分的时候想要往前查找，就只能回到开头，重新遍历了。双向链表提供了这个能力，即允许前向遍历，也允许后向遍历整个链表。原因是双向链表的每个节点都有两个指向其他节点的引用。但这也是其缺点，因为在插入、删除的时候需要处理四个链接点的引用， 占用的空间也大了一些。如将头节点和尾节点链接起来，即成为双向循环链表。下面是 java 代码：package test;public class DoubleLink public Link first;public Link last;public DoubleLink
2、（） / 构造器，初始化this.first = null;this.last = null;public boolean isEmpty（） / 判断是否为空return first = null;public void insertFirst（int idata） / 将元素插入链表开头Link link = new Link（idata）；if （isEmpty（）last = link;/ 如果为空，last 需要改变elsefirst.previous = link;/ 非空，则要在 first 前插入link.next = first;first = link;public voi
3、d insertLast（int idata） / 插入链表结尾Link link = new Link（idata）；if （isEmpty（）first = link;elselast.next = link;link.previous = last;last = link;public boolean insertAfter（int key, int idata） / 在某项元素后插入Link current = first;while （current.idata != key） /从头开始查找current = current.next;if （current = null）/到表尾
4、也没有找到return false;Link link = new Link（idata）；if （current = last） link.next = null;last = link; else link.next = current.next;current.next.previous = link;link.previous = current;current.next = link;return true;public Link delectKey（int key） / 删除某项元素Link current = first;while （current.idata != key）
5、current = current.next;if （current = null）return null;if （current = first）first = current.next;elsecurrent.previous.next = current.next;if （current = last）last = current.previous;elsecurrent.next.previous = current.previous;return current;public Link delectFirst（） / 删除链表开头元素Link temp = first;if （fir
6、st.next = null）/ 只有一个元素last = null;elsefirst.next.previous = null;/first 节点的 next 字段引用的链节点的previous 字段first = first.next;return temp;public Link delectLast（） / 删除链表最后的元素Link temp = last;if （first.next = null）first = null;elselast.previous.next = null;last = last.previous;return temp;public void show
7、First（） / 前向展示Link current = last;while （current != null） current.showLink（）；current = current.previous;public void showLast（） / 后向展示Link current = first;while （current != null） current.showLink（）；current = current.next;public static void main（String args） DoubleLink dlink = new DoubleLink（）；dlink.i
8、nsertFirst（1）；dlink.insertFirst（2）；dlink.insertFirst（3）；dlink.showFirst（）；dlink.insertLast（4）；dlink.insertLast（5）；dlink.showFirst（）；class Link public int idata;/ 存放的数据public Link previous;/ 对前一项的引用public Link next;/ 对后一项的引用public Link（int idata） this.idata = idata;public void showLink（） System.out.print（idata + ）；
