2022年数据结构之双向链表的Java实现 .pdf

数据结构之双向链表的Java 实现单链表只能从前往后遍历， 如果链表的长度较大， 遍历到链表后半部分的时候想要往前查找，就只能回到开头，重新遍历了。双向链表提供了这个能力， 即允许前向遍历， 也允许后向遍历整个链表。 原因是双向链表的每个节点都有两个指向其他节点的引用。但这也是其缺点， 因为在插入、删除的时候需要处理四个链接点的引用，占用的空间也大了一些。如将头节点和尾节点链接起来，即成为双向循环链表。下面是 java 代码：package test; public class DoubleLink public Link first; public Link last; public DoubleLink（） / 构造器，初始化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需要改变else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - first.previous = link;/ 非空，则要在 first前插入link.next = first; first = link; public void insertLast（int idata） / 插入链表结尾Link link = new Link（idata ）；if （isEmpty （）first = link; else last.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）/ 到表尾也没有找到return false; Link link = new Link（idata ）；if （current = last） link.next = null; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 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） current = current.next; if （current = null）return null; if （current = first）first = current.next; else current.previous.next = current.next; if （current = last）last = current.previous; else current.next.previous = current.previous; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - return current; public Link delectFirst（） / 删除链表开头元素Link temp = first; if （first.next = null）/ 只有一个元素last = null; else first.next.previous = null;/first节点的 next 字段引用的链节点的previous 字段first = first.next; return temp; public Link delectLast（） / 删除链表最后的元素Link temp = last; if （first.next = null）first = null; else last.previous.next = null; last = last.previous; return temp; public void showFirst（） / 前向展示Link current = last; while （current != null） 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 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.insertFirst（1）；dlink.insertFirst（2）；dlink.insertFirst（3）；dlink.showFirst（）；dlink.insertLast（4）；dlink.insertLast（5）；dlink.showFirst（）； class Link public int idata;/ 存放的数据名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - public Link previous;/ 对前一项的引用public Link next;/ 对后一项的引用public Link（int idata） this.idata = idata; public void showLink（） System.out.print（idata + ）； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -