摘要：雙向鏈表的實(shí)現(xiàn)，必須注意雙向鏈表的和兩個(gè)指針的正確指向，以及插入和刪除過(guò)程中指向操作增減的有序性。定義節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)據(jù)類(lèi)型為，可以通過(guò)多態(tài)方式具象化為其他類(lèi)型定義從頭尾節(jié)點(diǎn)增加節(jié)點(diǎn)定義從頭尾節(jié)點(diǎn)刪除節(jié)點(diǎn)

線性表和鏈表

單向鏈表利用了類(lèi)的自引用，實(shí)現(xiàn)了類(lèi)似指針的效果。
雙向鏈表的實(shí)現(xiàn)，必須注意雙向鏈表的head和back兩個(gè)指針的正確指向，以及插入和刪除過(guò)程中指向操作增減的有序性。

下面幾圖從java面向?qū)ο蟮慕嵌日f(shuō)明了單向雙向鏈表的邏輯結(jié)構(gòu)，類(lèi)的自引用使得邏輯指向成為可能。

以下兩圖說(shuō)明了添加刪除頭尾節(jié)點(diǎn)時(shí)執(zhí)行的順序：

  
添加頭結(jié)點(diǎn)時(shí)先加一個(gè)臨時(shí)節(jié)點(diǎn)，建立此臨時(shí)節(jié)點(diǎn)和原頭節(jié)點(diǎn)后使此臨時(shí)節(jié)點(diǎn)為新頭結(jié)點(diǎn)即可。

  刪除尾節(jié)點(diǎn)時(shí)先使原次頭結(jié)點(diǎn)為新頭結(jié)點(diǎn)，然后刪除原頭節(jié)點(diǎn)和新頭結(jié)點(diǎn)的連接后，再刪除新頭結(jié)點(diǎn)和原頭結(jié)點(diǎn)的連接。

尾節(jié)點(diǎn)的處理方法類(lèi)似。
這樣的刪除方法能夠完全釋放所有的占用空間。

下面是雙向鏈表的實(shí)現(xiàn)過(guò)程，包括鏈表類(lèi)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 ///定義節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)據(jù)類(lèi)型為Object，可以通過(guò)多態(tài)方式具象化為其他類(lèi)型
{
    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;
    }
    ///////////////////////定義從頭尾節(jié)點(diǎn)增加節(jié)點(diǎn)
    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;
        }
    }
    //////////////////////////定義從頭尾節(jié)點(diǎn)刪除節(jié)點(diǎn)
    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("
");
    }
}