资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
数据结构之双向链表的 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 需要改变elsefirst.previous = link;/ 非空,则要在 first 前插入link.next = first;first = link;public void 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)/到表尾也没有找到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) 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 (first.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 showFirst() / 前向展示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.insertFirst(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 + );
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号