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

    //头结点
    private Node<E> first;
    //委节点
    private Node<E> last;
    //节点大小
    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;
        //若链表没有数据则把新节点赋给头节点，否则原尾结点指向新节点
        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;
        //若链表没有数据则把新节点赋给尾节点，否则原头结点的前驱节点指向新节点
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
    }

    /**
     * 默认采用队列模式添加元素
     * @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;
        //找到要插入位置的前一个节点
        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;
        //找到要删除元素的前一个节点
        for (int i = 0; i < index-1; i++) {
            node=node.next;
        }
        Node<E> q=node.next;
        node.next=q.next;
        size--;
    }

    /**
     * 删除链表中的第一个元素
     */
    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--;
    }

    /**
     * 删除链表中的最后一个元素
     */
    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;
    }

    /**
     * 获取链表中的第一个元素
     * @return
     */
    public E getFirst(){
       return getSide(() -> first);
    }

    /**
     * 获取链表中的最后一个元素
     * @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;
    }

    //节点类
    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;
        }
    }
}