一、Definition

  A double-ended list(双端链表) is similar to a simple linked list, but it has an additional feature:a reference to the last link as well as to the first. It can discribe as the following picture:

二、Implement

  Now, we can implement this data structure with java language. We only add a last link which refereces to the last link at the begaining of the simple linked list, and change a littile based on the simple linked list(simple
linked list).

The implement code is like this:

public class DoubleEndedList 
{
    private Link first;
    private Link last;
    
    public DoubleEndedList()
    {
    	first=null;
    	last=null;
    }
	
    public boolean isEmpty()
    {
    	return (first==null);
    }

    
    public void insertFirst(int iData)
    {
    	Link newLink=new Link(iData);
    	
    	if(isEmpty())
    	{
    		last=newLink;
    	}
    	
    	newLink.next=first;
    	first=newLink;
    }

    
    public void insertLast(int iData)
    {
    	Link newLink=new Link(iData);
    	
    	if(isEmpty())
    	{
    		first=newLink;
    	}
    	else
    	{
    		last.next=newLink;
    	}
    	last=newLink; 	    	
    }

    
    public int deleteFirst()
    {
    	int temp=first.iData;
    	//链表中只有一个元素
    	if(first.next==null)
    	{
    		last=null;
    	}
    	first=first.next;
    	return temp;
    }

    
    public void dispaly()
    {
    	Link current=first;
    	while(current!=null)
    	{
    		current.dispaly();
    		current=current.next;
    	}
    }
    		
    
    
    
    
}

   The implemt class called DoubleEndedList has two important elements frist which references to the first link, and last which references to the last link.

  The insertion and deletion routines are similar to those in a single-ended list.However, both insertion routines must watch out for the special case when the list is empty prior to the
insertion. That is, if isEmpty() is true, then insertFirst() must set last to the new link,
and insertLast() must set first to the new link.
  If inserting at the beginning with insertFirst(), first is set to point to the new link, although when inserting at the end with insertLast(), last is set to point to the new link. Deleting from the start of the list is also a
special case if it’s the last item on the list: last must be set to point to null in this case.

(在这里用解释下：在链表头或尾插入节点时，都要判断节点是否为空。如果链表是空的，即没有节点：（1）如果在链表头插入节点时需要将last指向新插入的节点。（2）如果是在链表尾部插入节点，那么需要将first指向新插入的节点。

如果链表中只有一个节点，那么我们删除链表头的节点后，需要将last设为空。)

   insertLast() method can be discribed like the following picture:

三、Efficiency

   The efficiency of double-ended link is the same as

simple linked list. We will describe it in English here:

(1)Insertion and Deletetion
  Insertion and deletion at the beginning of a linked list are very fast which takes O(1) time. But an array is  O(N) for this operations. So the linked list is faster bacause nothing needs to be moved when an item is inserted or deleted.

(2)Finding

  Finding and Accessing a item in a linked list both takes O(n) time, but the time in an array is O(logn)and O(1) accordingly.
 (3) Memory Size

  Another important advantage of linked lists over arrays is that a linked list uses exactly as much memory as it needs and can expand  to fill all of available memory.The size of an array is fixed when it's created;this usually
ledas to inefficiency because the array is too large, or to running out of room because the array is too small.Vectors, which are expandable arrays, may solve this problem to some extent, but they usually expand in fixed-sized increments (such as doubling
the size of the array whenever it’s about to overflow). This solution is still not as efficient a use of memory as a linked list.

Reference

Data Structure and Algrithem in Java,Robert  Lafore