数据结构之双向链表的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
            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 + " ");
    }
}