JAVA数据结构:双端链表

双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用

定义一个Link类

public class Link {
public long dData;
public Link next;
public Link(long d){
        dData = d;
    }
public void displayLink(){
        System.out.println(dData+" ");
    }
}

双端链表的简单实现

public class FirstLastLink(){

private Link first;
private Link last;

public FirstLastLink(){
        first = null;
        last = null;
    }
public void display(){
        System.out.println("FirstLastLink: (first-->last)");
        Link current = first;
while(current !=null){
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }
public boolean isEmpty(){
return (first == null);
    }

public void insertFirst(long value){
        Link newlink = new Link(value);
if(isEmpty()){
            last = newlink;
            first = newlink;
        }else{
            newlink.next = first;
            first = newlink;
        }
    }

public void insertLast(long value){
        Link newlink = new Link(value);
if(isEmpty()){
            first = newlink;
            last = newlink;
        }else{
            last.next = newlink;
            last = newlink;
        }
    }

public long deleteFirst(){
long temp = first.dData;
if(first.next == null){
            last = null;
        }
        first = first.next;
return temp;
    }
}

双端链表不能删除最后一个链节点,因为没有引用指向最后第二个链节点.
为了方便地删除最后一个链节点,需要一个双向链表