雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針，分別指向直接后繼和直接前驅(qū)。
所以，從雙向鏈表中的任意一個結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

雙鏈表的重要性質(zhì)就是可以根據(jù)任意節(jié)點(diǎn)快速獲取其前后節(jié)點(diǎn)，
所以提供了getPrevNode()和getNextNode()方法；

還有就是，雙鏈表遍歷節(jié)點(diǎn)時，無需實現(xiàn)任何接口，直接利用節(jié)點(diǎn)間的關(guān)系即可完成遍歷。

public class DoubleLinkedList<T> {

    private int size;//鏈表大小
    //由于是雙向，頭尾任意選擇一端即可
    private Node<T> head;//鏈表的頭節(jié)點(diǎn)
    private Node<T> tail;//鏈表的尾節(jié)點(diǎn)

    /**
     * 內(nèi)部類：節(jié)點(diǎn)
     * @param <T>
     */
    public static class Node<T>{
        private Node prev;
        private Node next;
        private T data;

        public Node(T data){
            this.data = data;
        }

        private Node(){}
    }

    /**
     * 添加到鏈尾
     * @param data
     */
    public void add(T data){
        add(size, data);
    }

    /**
     * 添加到任意index處
     * @param index
     * @param data
     */
    public void add(int index, T data){
        Node<T> node = new Node<>(data);
        if(isEmpty()){//鏈表為空
            head = node;
            tail = node;
        }else {
            if(index > size - 1){//索引超出當(dāng)前鏈表大小，則添加到鏈尾
                Node<T> temp = tail;
                tail = node;
                temp.next = tail;
                tail.prev = temp;
            }else {//原index位置處有值，索引位置大于index的元素向鏈尾移動(實際并不是移動，只是看上去)
                Node<T> origin = getNode(index);
                Node<T> prev = origin.prev;
                prev.next = node;
                node.prev = prev;
                node.next = origin;
                origin.prev = node;
            }
        }

        size++;
    }

    /**
     * 更新index位置處元素的值
     * @param index
     * @param data
     */
    public void set(int index, T data){
        if(index > size - 1 || index < 0){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        getNode(index).data = data;
    }

    /**
     * 刪除index位置處的元素
     * @param index
     */
    public void delete(int index){
        if(index > size - 1 || index < 0){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if(index == 0){//刪除鏈頭
            head = head.next;
            head.prev = null;
        }else if(index == size -1){//刪除鏈尾
            tail = tail.prev;
            tail.next = null;
        }else {//普通節(jié)點(diǎn)
            Node<T> node = getNode(index);
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            node.prev = null;
            node.next = null;
        }
        size--;
    }

    /**
     * 獲取index位置處的元素的值
     * @param index
     * @return
     */
    public T getValue(int index){
        return getNode(index) == null ? null : getNode(index).data;
    }

    public T getValue(Node<T> node){
        return node == null ? null : node.data;
    }

    /**
     * 獲取節(jié)點(diǎn)node的上一個節(jié)點(diǎn)
     * @param node
     * @return
     */
    public Node<T> getPrevNode(Node<T> node){
        return node == null ? null : node.prev;
    }

    /**
     * 獲取節(jié)點(diǎn)node的下一個節(jié)點(diǎn)
     * @param node
     * @return
     */
    public Node<T> getNextNode(Node<T> node){
        return node == null ? null : node.next;
    }

    public Node<T> getHeadNode(){
        return head;
    }

    public Node<T> getTailNode(){
        return tail;
    }

    /**
     * 獲取index位置處的元素
     * @param index
     * @return
     */
    public Node<T> getNode(int index){

        if (isEmpty() && (index > size - 1)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> result = head;
        int n = 0;
        while (n < index) {//注意這里是 n < index， 而不是n <= index
            result = result.next;
            n++;
        }
        return result;
    }

    /**
     * 獲取值為data的元素在鏈表中的位置（第一次出現(xiàn)的位置，可能含有多個）
     * @param data
     * @return
     */
    public int indexOf(T data){
        if(isEmpty() || data == null){
            return -1;
        }

        int n = 0;
        Node<T> node = head;
        while (n < size){
            if(data.equals(node.data)){
                return n;
            }
            n++;
        }

        return -1;
    }

    /**
     * 判斷是否有值為data的元素
     * @param data
     * @return
     */
    public boolean containValue(T data){
        return indexOf(data) != -1;
    }

    /**
     * 獲取鏈表的大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判斷鏈表是否為空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


}