摘要：雙向鏈表的實現，必須注意雙向鏈表的和兩個指針的正確指向，以及插入和刪除過程中指向操作增減的有序性。定義節點，節點數據類型為，可以通過多態方式具象化為其他類型定義從頭尾節點增加節點定義從頭尾節點刪除節點

線性表和鏈表

單向鏈表利用了類的自引用，實現了類似指針的效果。
雙向鏈表的實現，必須注意雙向鏈表的head和back兩個指針的正確指向，以及插入和刪除過程中指向操作增減的有序性。

下面幾圖從java面向對象的角度說明了單向雙向鏈表的邏輯結構，類的自引用使得邏輯指向成為可能。

以下兩圖說明了添加刪除頭尾節點時執行的順序：

  
添加頭結點時先加一個臨時節點，建立此臨時節點和原頭節點后使此臨時節點為新頭結點即可。

  刪除尾節點時先使原次頭結點為新頭結點，然后刪除原頭節點和新頭結點的連接后，再刪除新頭結點和原頭結點的連接。

尾節點的處理方法類似。
這樣的刪除方法能夠完全釋放所有的占用空間。

下面是雙向鏈表的實現過程，包括鏈表類NodeList的插入刪除操作。

public class TestList 
{
    public static void main(String[] Args) 
    {
        NodeList OhMyGod = new NodeList();

        Boolean b = Boolean.TRUE;
        Character c = new Character("$");
        Integer i = new Integer(34567);
        String s = "hello";

        OhMyGod.insertFromBack(b);
        OhMyGod.print();
        OhMyGod.insertFromHead(c);
        OhMyGod.print();
        OhMyGod.insertFromBack(i);
        OhMyGod.print();
        OhMyGod.insertFromHead(s);
        OhMyGod.print();
        System.out.println(OhMyGod.deleteFromBack());
        OhMyGod.print();
        System.out.println(OhMyGod.deleteFromBack());
        OhMyGod.print();
        System.out.println(OhMyGod.deleteFromBack());
        OhMyGod.print();
        System.out.println(OhMyGod.deleteFromBack());
        OhMyGod.print();
    }
}

class Node ///定義節點，節點數據類型為Object，可以通過多態方式具象化為其他類型
{
    private Node headPointer;
    private Object data;
    private Node backPointer;


    public Node(Node hp,Object o,Node bp)
    {
        headPointer = hp;
        backPointer = bp;
        data = o;
    }
    public Node()
    {
        this(null,null,null);
    }
    public Node(Object o)
    {
        this(null,o,null);
    }
    public Node(Node hp,Object o)
    {
        this(hp,o,null);
    }
    public Node(Object o,Node bp)
    {
        this(null,o,bp);
    }

    public Node getHeadPointer() {
        return headPointer;
    }
    public Object getData() {
        return data;
    }
    public Node getBackPointer() {
        return backPointer;
    }
    public void setHeadPointer(Node headPointer) {
        this.headPointer = headPointer;
    }
    public void setBackPointer(Node backPointer) {
        this.backPointer = backPointer;
    }
}

class NodeListEmptyExcption extends RuntimeException
{

    private static final long serialVersionUID = 5130245130776457112L;
    public NodeListEmptyExcption(String name)
    {
        super("NodeList:"+name+" is Empty !");
    }
}

class NodeList
{
    private String listName;
    private Node headNode;
    private Node backNode;
    public NodeList()
    {
        this("default");
    }
    public NodeList(String listName) 
    {
        this.listName = listName;
        headNode = backNode = null;
    }
    public Boolean isEmpty()
    {
        return headNode == null;
    }
    ///////////////////////定義從頭尾節點增加節點
    public void insertFromHead(Object o)
    {
        if(isEmpty())
            headNode = backNode = new Node(o);
        else 
        {
            //headNode = new Node(o,headNode);
            Node tempNode = new Node(o);
            tempNode.setBackPointer(headNode);
            headNode.setHeadPointer(tempNode);
            headNode = tempNode;


        }
    }
    public void insertFromBack(Object o)
    {
        if(isEmpty())
            headNode = backNode = new Node(o);
        else
        {
            Node tempNode = new Node(o);
            backNode.setBackPointer(tempNode);
            tempNode.setHeadPointer(backNode);
            backNode = tempNode;
        }
    }
    //////////////////////////定義從頭尾節點刪除節點
    public Object deleteFromHead() throws NodeListEmptyExcption
    {
        if(isEmpty())
            throw new NodeListEmptyExcption(listName);

        Object removedata = headNode.getData();

        if(headNode.equals(backNode))
        {
            headNode = backNode = null;
        }

        else 
        {
            headNode = headNode.getBackPointer();
            headNode.getHeadPointer().setBackPointer(null);
            headNode.setHeadPointer(null);  
        }
        return removedata;
    }
    public Object deleteFromBack() throws NodeListEmptyExcption
    {
        if(isEmpty())
            throw new NodeListEmptyExcption(listName);

        Object removedata = backNode.getData();
        if(headNode.equals(backNode))
        {
            headNode = backNode = null;
        }
        else 
        {
            backNode = backNode.getHeadPointer();
            backNode.getBackPointer().setHeadPointer(null);
            backNode.setBackPointer(null);
        }   
        return removedata;
    }
    public void print()
    {
        if(isEmpty())
        {
            System.out.println("Node List "+listName+" is empty !");
        return;
        }
        Node currentNode = headNode;
        while(currentNode!=null)
        {
            System.out.print(currentNode.getData().toString()+" ");
            currentNode  = currentNode.getBackPointer();
        }
        System.out.println("
");
    }
}