/**
 * Description 雙向鏈表
 * Date 2017-09-03
 * Author Edgar
 */
public class Link<E> {

    //頭結(jié)點(diǎn)
    private Node<E> first;
    //委節(jié)點(diǎn)
    private Node<E> last;
    //節(jié)點(diǎn)大小
    private int size;

    public Link(){
        size=0;
    }

    /**
     * 向鏈表尾部添加元素
     * @param e
     */
    public void addLast(E e){
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        //若鏈表沒(méi)有數(shù)據(jù)則把新節(jié)點(diǎn)賦給頭節(jié)點(diǎn)咬荷，否則原尾結(jié)點(diǎn)指向新節(jié)點(diǎn)
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
    }

    /**
     * 向鏈表頭部添加元素
     * @param e
     */
    public void addFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        //若鏈表沒(méi)有數(shù)據(jù)則把新節(jié)點(diǎn)賦給尾節(jié)點(diǎn)术瓮，否則原頭結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向新節(jié)點(diǎn)
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
    }

    /**
     * 默認(rèn)采用隊(duì)列模式添加元素
     * @param e
     */
    public void add(E e){
        addLast(e);
    }

    /**
     * 向指定位置添加原
     * @param e
     * @param index
     */
    public void add(E e,int index){
        if (index<0 || index > size){
            throw new IndexOutOfBoundsException();
        }
        if (index==size){
            addLast(e);
            return;
        }
        if (0==index){
            addFirst(e);
            return;
        }
        Node<E> node=first;
        //找到要插入位置的前一個(gè)節(jié)點(diǎn)
        for (int i = 0; i < index-1; i++) {
            node=node.next;
        }
        Node<E> newNode = new Node<>(node, e, node.next);
        node.next=newNode;
        size++;
    }

    /**
     * 刪除指定位置的元素
     * @param index
     */
    public void remove(int index){
        if (index<0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        if (0==index){
            removeFirst();
            return;
        }
        if (index==size-1){
            removeList();
            return;
        }
        Node<E> node=first;
        //找到要?jiǎng)h除元素的前一個(gè)節(jié)點(diǎn)
        for (int i = 0; i < index-1; i++) {
            node=node.next;
        }
        Node<E> q=node.next;
        node.next=q.next;
        size--;
    }

    /**
     * 刪除鏈表中的第一個(gè)元素
     */
    public void removeFirst(){
        Node<E> f=first;
        if (null==f){
            throw new NoSuchElementException();
        }
        final Node<E> next=f.next;
        first=next;
        if (null!=next){
            next.prev=null;
        }
        size--;
    }

    /**
     * 刪除鏈表中的最后一個(gè)元素
     */
    public void removeList(){
        Node<E> l=last;
        if (null==l){
            throw new NoSuchElementException();
        }
        final Node<E> la=l.prev;
        last=la;
        if (null!=la){
            la.next=null;
        }
        size--;
    }

 /**
     * 找指定位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        if (index<0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        Node<E> f=first;
        if (null==f){
            throw new NoSuchElementException();
        }
        int j=0;
        while (null!=f && j<index){
            f=f.next;
            j++;
        }
        return null==f?null:f.data;
    }

    /**
     * 獲取鏈表中的第一個(gè)元素
     * @return
     */
    public E getFirst(){
       return getSide(() -> first);
    }

    /**
     * 獲取鏈表中的最后一個(gè)元素
     * @return
     */
    public E getLast(){
        return getSide(() -> last);
    }

    /**
     * 獲取鏈表兩端的元素
     * @param supplier
     * @return
     */
    private E getSide(Supplier<Node<E>> supplier){
        final Node<E> f=supplier.get();
        if (null==f){
            throw new NoSuchElementException();
        }
        return f.data;
    }

    public int size(){
        return this.size;
    }

    //節(jié)點(diǎn)類(lèi)
    private static class Node<E>{
        E data;
        Node<E> next;
        Node<E> prev;

        public Node(Node<E> prev,E data,Node<E> next){
            this.data=data;
            this.next=next;
            this.prev=prev;
        }
    }
}