单链表只能从前往后遍历,如果链表的长度较大,遍历到链表后半部分的时候想要往前查找,就只能回到开头,重新遍历了。
双向链表提供了这个能力,即允许前向遍历,也允许后向遍历整个链表。原因是双向链表的每个节点都有两个指向其他节点的引用。但这也是其缺点,因为在插入、删除的时候需要处理四个链接点的引用, 占用的空间也大了一些。如将头节点和尾节点链接起来,即成为双向循环链表。
下面是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 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; 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; 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) { 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 + " "); } }