双端链表与传统的链表非常相似，但是它有一个新增的特性：即对最后一个链接点的引用，就像对第一个链接点的引用一样
对最后一个链接点的引用允许项在表头一样，在表尾直接插入一个链接点。当然，仍然可以在普通的单链表的表尾插入一个链接带你，方法是遍历整个链表直到直达表尾，但是这种方法效率很低
像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，比如频繁要插入队尾元素的场合
双端链表的示例程序
public FirstLastLink next;
public FirstLastLink(long dd){
dData=dd;
}
public void displayLink(){
System.out.println("{"+dData+"}");
}
}
public class FirstLastList {
private FirstLastLink first;
private FirstLastLink last;
public FirstLastList(){
first=null;
last=null;
}
public boolean isEmpty(){
return first==null;
}
public void insertFirst(long dd){
FirstLastLink newLink=new FirstLastLink(dd);
if(isEmpty()){
last=newLink;
}
newLink.next= first;
first=newLink;
}
public void insertLast(long dd){
FirstLastLink newLink=new FirstLastLink(dd);
if(isEmpty()){
first=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;
}
public void displayList(){
FirstLastLink current=first;
while(current!=null){
current.displayLink();
current=current.next;
}
}
public static void main(String[] args) {
FirstLastList firstLastList=new FirstLastList();
firstLastList.insertFirst(22);
firstLastList.insertFirst(44);
firstLastList.insertFirst(55);
firstLastList.insertLast(11);
firstLastList.insertLast(33);
firstLastList.insertLast(66);
firstLastList.displayList();
System.out.println("======");
firstLastList.deleteFirst();
firstLastList.deleteFirst();
firstLastList.displayList();
}
}
这个程序在表头和表尾各插入三个连点，显示插入后的链表。然后删除头两个链接点，再次显示
表头在重复插入操作会颠倒链接点进入的顺序，而在表尾重复插入则保持链接点进入的顺序
双端链表有两个项，first和last，一个指向链表中的第一个链接点，另一个指向最后一个链接点。如果链表中只有一个链接点，first和last都指向它，如果没有链接点，两者都为null值
插入和删除方法和普通链表的相应部分类似。然而，两个插入方法都要考虑一种特殊情况，即插入前链表是空的，如果isEmpty（）是真，那么insertFirst必须把last指向新的链接点，insertLast也必须把first指向新的链接点
如果用insertFirst （）方法实现在表头插入，first就指向新的链接点，用insertLast()方法实现在表尾插入，last就指向新的链接点。如果链表只有一个链接点，那么从表头删除也是一种特殊情况，last必须被赋值为null值
不幸的是，用双端链表也不能有助于删除最后一个链接点，因为没有一个引用指向倒数第二个链接点，如果最后一个链接点被删除，倒数第二个链接点的next字段应该变成null值，为了删除最后一个链接点，需要一个双向链表，下篇会讨论它
链表的效率
在表头插入和删除速度很快，仅需要改变一两个引用值，所以花费O(1)的时间
平均起来，查找，删除和在指定链接点后面插入都需要搜索链表中一半链接点。需要O(N)此比较，在数组中执行这些操作也需要O(N)次比较，但是链表仍然要快一些，因为当插入和删除链接点时，链表不需要移动任何东西，增加的效率是很明显的，特别是当复制时间远远大于比较时间的时候
当然，链表比数组优越的另外一个重要方面是链表需要多少内存就可以用多少内存，冰倩可以扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常由于数组太大导致效率低下，或者数组太小导致空间溢出。向量是一种可扩展的数组，它可以通过可变长度解决这个问题，但是它经常只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍数组容量），这个解决方案在内存使用效率上来说还是比链表的低
