Java 数据结构实现（DataStructure）1

摘要：双向链表的实现，必须注意双向链表的和两个指针的正确指向，以及插入和删除过程中指向操作增减的有序性。定义节点，节点数据类型为，可以通过多态方式具象化为其他类型定义从头尾节点增加节点定义从头尾节点删除节点

线性表和链表

单向链表利用了类的自引用，实现了类似指针的效果。
双向链表的实现，必须注意双向链表的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("
");
    }
}