数据结构与算法（四） 双向链表

一、简单介绍

双向链表是一种对称结构，它克服了单链表上指针单向性的缺点，其中每一个节点即可向前引用，也可向后引用，这样可以更方便的插入、删除数据元素。
　　由于双向链表需要同时维护两个方向的指针，因此添加节点、删除节点时指针维护成本更大；但双向链表具有两个方向的指针，因此可以向两个方向搜索节点，因此双向链表在搜索节点、删除指定索引处节点时具有较好的性能。

二、代码实现

1、节点对象

class DoubleNode {

    private int no;
    private String name;
    private DoubleNode next;
    private DoubleNode pre;

    public DoubleNode(int no,String name){
        this.name=name;
        this.no=no;
    }

    public DoubleNode getPre() {
        return pre;
    }

    public DoubleNode getNext() {
        return next;
    }

    public void setNext(DoubleNode next) {
        this.next = next;
    }

    public void setPre(DoubleNode pre) {
        this.pre = pre;
    }

    public int getNo() {
        return no;
    }

    @Override
    public String toString() {
        return "DoubleNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

2、双向链表的实现

/**
 * 双向链表
 */
public class DoubleLinkedList {

    /**
     * 头节点
     */
    private DoubleNode headNode=new DoubleNode(0,"");

    /**
     * 添加节点
     * @param doubleNode
     */
    public void add(DoubleNode doubleNode){
        if (doubleNode == null){
            throw new RuntimeException("参数不能为空");
        }
        DoubleNode temp=headNode;
        while (temp.getNext()!=null){
            if(temp.getNext().getNo() == doubleNode.getNo() ){
                throw new RuntimeException("编号不可重复");
            }
            temp=temp.getNext();
        }
        temp.setNext(doubleNode);
        doubleNode.setPre(temp);
    }




    /**
     * 根据编号删除节点
     * @param no
     */
    public void delete(int no){
        if (headNode.getNext() == null){
            throw new RuntimeException("链表为空。。。");
        }
        DoubleNode temp=headNode.getNext();
        boolean flag=false;
        while (true){
            if (temp == null) {
                break;
            }
            if(temp.getNo() == no ){
                flag=true;
                break;
            }
            temp=temp.getNext();
        }
        if (flag){
           temp.getPre().setNext(temp.getNext());
           if (temp.getNext()!=null){
               temp.getNext().setPre(temp.getPre());
           }
        }else {
            System.out.printf("编号为%d的节点没有找到\n",no);
        }
    }



    /**
     * 显示链表的数据
     */
    public void show(){
        if (headNode.getNext() == null){
            throw new RuntimeException("链表为空。。。");
        }
        DoubleNode temp=headNode;
        while (temp.getNext()!=null){
            System.out.println(temp.getNext());
            temp=temp.getNext();
        }
    }

    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList=new DoubleLinkedList();
        doubleLinkedList.add(new DoubleNode(1,"1"));
        doubleLinkedList.add(new DoubleNode(2,"2"));
        doubleLinkedList.add(new DoubleNode(3,"3"));

        doubleLinkedList.show();

        System.out.println("*******");
        doubleLinkedList.delete(9);
        doubleLinkedList.show();

    }

}