双向链表

传统链表的一个潜在问题是沿链表的反向遍历是困难的，用这样一个语句current=current.next可以很方便地到达下一个链接点，然而没有对应的方法回到前一个链接点。根据应用的不同，这个限制可能会引起问题

双向链表允许向前遍历，也允许向后遍历整个链表。其中秘密在于每个链接点有两个指向其他链接点的引用，而不是一个。第一个像普通链表一样指向下一个链接点，第二个指向前一个链接点

在双向链表中，Link类定义的开头是这样声明的：

class Link{
    public long dData;
    public Link next;
    public Link previous;
}

双向链表的缺点是每次插入或删除一个链接点的时候，要处理四个链接点的引用，而不是两个：两个链接前一个链接点，两个链接后一个链接点。当然，由于多了两个引用，链接点的占用空间变大了一点

双向链表不必是双端链表（保持一个对链表最后一个元素的引用），但这种方式是有用的，所以在后面的例子中将包含双端的性质

遍历

两个显示方法说明了双向链表的遍历，displayForward()方法和在普通链表中看到的displayList（）方法一样，displayBackward()方法与它们类似，但是从表尾开始，通过每个元素的previous域，一步一步向前到达表头

Link current=last;
while(current!=null){
    current=current.previous
}

插入

在DoublyLinkedList类中已经包含了几个插入方法，insertFirst()方法在表头插入，insertLast（）在表尾插入，insertAfter（）在某一个特定元素的后面插入，除非这个链表是空的，否则insertFirst（）方法把原先指向链接点的previous字段指向新连接点，把链接点的next字段指向前者。最后把first指向新链接点

如果链表是空的，last字段必须改变，而不是first.previous字段改变，下面是insertFirst的代码：

if(isEmpty()){
    last=newLink;
}else{
    first.previous=newLink;
}
newLink.next=first;
first=newLink;

insertLast()是一个同样的过程，只不过应用在表尾；它和insertFirst方法呈镜像

insertAfter（）是在某个特定值的链接点后插入一个新的链接点。它有点复杂，因为需要建立四个链接，首先，必须找到具有特定值的链接点，然而，假设插入点不再表尾，首先建立新链接点和下一个链接点之间的两个链接，接着建立current所指链接点和新链接点之间的两个链接，如果新链接点插在表尾，它的next字段必须设为null值，last值必须指向新的链接点

if(current==last){
    newLink.next=null;
    last=newLink;
}else{
    newLink.next=current.next;
    current.next.previous=newLink;
}

newLink.previous=current;
current.next=newLink;

删除

如果被删除的链接点是第一个或者最后一个，那么就产生了特殊情况，因为first或者last必须指向前一个或后一个链接点，下面是deleteKey方法中处理链接点链接的代码

if(current==first){
    first=current.next;
}else{
    current.previous.next=current.next;
}

if(current==last){
    last=current.previous;
}else{
    current.next.previous=current.previous;
}

package 双向链表;

class Link{
    public long dData;
    public Link next;
    public Link previous;
    
    public Link(long d ){
        dData=d;
    }
    
    public void dosplayLink(){
        System.out.println(dData);
    }
}

class DoublyLinkedList{
    private Link first;
    private Link last;
    
    public DoublyLinkedList(){
        first=null;
        last=null;
    }
    
    public boolean isEmpty(){
        return first==null;
    }
    
    public void insertFirst(long dd){
        Link newLink=new Link(dd);
        
        if(isEmpty()){
            last=newLink;
        }else {
            first.previous=newLink;
        }
        newLink.next=first;
        first=newLink;
    }
    
    public void insertLast(long dd){
        Link newLink=new Link(dd);
        
        if(isEmpty()){
            first=newLink;
        }else{
            last.next=newLink;
            newLink.previous=last;
        }
        last=newLink;
    }
    
    public Link deleteFirst(){
        Link temp=first;
        
        if(first.next==null){
            last=null;
        }else {
            first.next.previous=null;
        }
        first=first.next;
        return temp;
    }
    
    public Link deleteLast(){
        Link temp=last;
        if(first.next==null){
            first=null;
        }else{
            last.previous.next=null;
        }
        
        last=last.previous;
        return temp;
    }
    
    public boolean omsertAfter(long key,long dd){
        Link current=first;
        
        while(current.dData!=key){
            current=current.next;
            if(current==null){
                return false;
            }
        }
        
        Link newLink=new Link(dd);
        
        if(current==last){
            newLink.next=null;
            last=newLink;
        }else{
            newLink.next=current.next;
            current.next.previous=newLink;
        }
        
        newLink.previous=current;
        current.next=newLink;
        return true;
    }
    
}