双端链表

　对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。

1、什么时双端链表：

链表中保持这对最后一个连点引用的链表

2、从头部插入

要对链表进行判断，如果为空则设置尾节点为新添加的节点

3、从尾部进行插入

如果链表为空，则直接设置头节点为新添加的节点，否则设置尾节点的后一个节点为新添加的节点

4、从头部删除

判断节点是否有下个节点，如果没有则设置节点为null

/**
 * @Auther: liuhaidong
 * Data: 2019/10/11 0011、12:07
 * Description:
 * @version: 1.0
 */
public class DoublePointLinkedList {
    private Node head;
    //头节点
    private Node tail;
    //尾节点
    private int size;
    //节点的个数
    public DoublePointLinkedList() {
        size = 0;
        head = null;
        tail = null;
    }

    //表头新增节点
    public void addHead(int data){
        Node node = new Node(data);
        if (size == 0) {
            //如果链表为空，那么头节点和尾节点都是该新增节点
            head = node;
            tail = node;
            size++;
        } else {
            node.next = head;
            head = node;
            size++;
        }
    }

    //链表尾新增节点
    public void addTail(int data) {
        Node node = new Node(data);
        if (size == 0) {
            //如果链表为空，那么头节点和尾节点都是该新增节点
            head = node;
            tail = node;
            size++;
        } else {
            tail.next = node;
            tail = node;
            size++;
        }
    }

    //删除头部节点，成功返回true，失败返回false
    public boolean deleteHead() {
        if (size == 0) {
            //当前链表节点数为0
            return false;
        }
        if (head.next == null) {
            //当前链表节点数为1
            head = null;
            tail = null;
        } else {
            head = head.next;
        }
        size--;
        return true;
    }
    /**
     * @Author liuhaidong
     * @Description 显示出所有的节点信息(已测试)
     * @param
     * @Date 10:55 2019/10/11 0011
     */
    public void displayNode(){
        if(size > 0){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){
                //当前链表只有一个节点
                System.out.println("["+node.data+"]");
                return;
            }
            while(tempSize>0){
                if(node.equals(head)){
                    System.out.print("["+node.data+"->");
                }else if(node.next == null){
                    System.out.print(node.data+"]");
                }else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
        }
    }
    /**
     * @Author liuhaidong
     * @Description 判断链表是否为空(已测试)
     * @param
     * @Date 10:27 2019/10/11 0011
     */
    public boolean isEmpty(){
        return (size == 0);
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }
}

用双端链表实现队列

/**
 * @Auther: liuhaidong
 * Data: 2019/10/11 0011、12:31
 * Description:
 * @version: 1.0
 */
public class MyQueue {
    private DoublePointLinkedList dp;
    /** Initialize your data structure here. */
    public MyQueue() {
        dp = new DoublePointLinkedList();
    }

    /** Push element x to the back of queue. */
    public void push(int data) {
        dp.addTail(data);
        dp.setSize(dp.getSize()+1);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        dp.deleteHead();
        //队尾元素
        dp.setSize(dp.getSize()-1);
        return dp.findNde(dp.getSize()).data;
    }

    /** Get the front element. */
    public int peek() {
        return dp.findNde(dp.getSize()).data;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {

        return dp.isEmpty();
    }
}

双向链表

我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。

/**
 * @Auther: liuhaidong
 * Data: 2019/10/11 0011、21:12
 * Description:
 * @version: 1.0
 */
public class TwoWayLinkedList {
    private NodeTwo head;
    //表示链表头
    private NodeTwo tail;
    //表示链表尾
    private int size;
    // 表示链表的节点个数
    public TwoWayLinkedList() {
        size = 0;
        head = null;
        tail = null;
    }

    //在链表头增加节点
    public void addHead(int value) {
        NodeTwo newNode = new NodeTwo(value);
        if (size == 0) {
            head = newNode;
            tail = newNode;
            size++;
        } else {
            head.prev = newNode;//把新的结点给原来头的前面
            newNode.next = head;//旧的头结点为新的后面
            head = newNode;//新的为新的结点
            size++;
        }
    }

    //在链表尾增加节点
    public void addTail(int value){
        NodeTwo newNode = new NodeTwo(value);
        if (size == 0) {
            head = newNode;
            tail = newNode;
            size++;
        } else {
            newNode.prev = tail;//原来的尾结点为新加的前面结点
            tail.next = newNode;//新的结点为尾结点的下一个
            tail = newNode;//新的结点为尾结点
            size++;
        }
    }

    //删除表头 并且返回
    public NodeTwo deleteHead(){
        NodeTwo tmp = head;
        if(size != 0){
            head = head.next;
            head.prev = null;
            size--;
        }
        return tmp;
    }
    //删除链表尾
    public NodeTwo deleteTail(){
        NodeTwo temp = tail;
        if(size != 0){
            tail = tail.prev;
            tail.next = null;
            size--;
        }
        return temp;
    }

    //获得链表的节点个数
    public int getSize() {
        return size;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return (size == 0);
    }
    /**
     * @Author liuhaidong
     * @Description 显示出所有的节点信息(已测试)
     * @param
     * @Date 10:55 2019/10/11 0011
     */
    public void displayNode(){
        if(size > 0){
            NodeTwo node = head;
            int tempSize = size;
            if(tempSize == 1){
                //当前链表只有一个节点
                System.out.println("["+node.data+"]");
                return;
            }
            while(tempSize>0){
                if(node.equals(head)){
                    System.out.print("["+node.data+"->");
                }else if(node.next == null){
                    System.out.print(node.data+"]");
                }else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
        }
    }
}
/**
 * @Auther: liuhaidong
 * Data: 2019/10/11 0011、21:13
 * Description:
 * @version: 1.0
 */
public class NodeTwo {
    public int data;
    public NodeTwo next;
    public NodeTwo prev;
    public NodeTwo(int data) {
        this.data = data;
    }
}