package test;

public class MyLinkedList<E> {

    //先初始化节点类

    private static class Node<E>{

        E element;//节点数据

        Node<E> pre;//上一个节点

        Node<E> next;//下一个节点信息

        public Node(E element,Node<E> next,Node<E> pre){

            this.element = element;

            this.pre = pre;

            this.next = next;

        }

    }

    private int size;//链表的大小

    private Node<E> first;//第一个节点

    private Node<E> last;//最后一个节点

    /**

     * 默认往链表尾部添加

     * @param e

     */

    public void add(E e){

        addAtLast(e);

    }

    /**

     * 往指定位置添加元素

     * @param e

     * @param index

     */

    public void add(E e,int index){

        //先检查是否越界

        checkRangeForAdd(index);

        if(index == size){//在尾部添加时

            addAtLast(e);

        }else{

            Node<E> curNode = node(index);

            addBeforeNode(e, curNode);

        }

    }

    /**

     * 根据index获取元素

     * @param index

     * @return

     */

    public E get(int index){

        //先检查是否越界

        checkRange(index);

        return node(index).element;

    }

    /**

     * 查找元素的下标

     * @param element

     * @return

     */

    public int indexOf(Object element){

        Node<E> cursor = first;

        int count = ;

        while (null != cursor) {

            if(null != element){

                if(element.equals(cursor.element)){

                    return count;

                }

            }else{

                if(null == element){//考虑到被查找的元素的为空的情况

                    return count;

                }

            }

            cursor = cursor.next;

            count++;

        }

        return -;

    }

    /**

     * 根据下标删除元素是，处理链表的双向关系

     * @param index

     * @return

     */

    private E deleteLink(int index){

        Node<E> node = node(index);

        E element = node.element;

        Node<E> preNode = node.pre;

        Node<E> nextNode = node.next;

        if(null == preNode){//删除的节点为第一个节点时

            first = nextNode;

        }else{

            preNode.next = nextNode;

            node.next = null;

        }

        if (nextNode == null) {//删除的为最后一个节点时

            last = preNode;

        }else{

            nextNode.pre = preNode;

            node.pre = null;

        }

        size--;

        node.element = null;

        return element;

    }

    /**

     * 根据index删除元素

     * @param index

     * @return

     */

    public E remove(int index){

        //检查数组下标是否越界

        checkRange(index);

        return deleteLink(index);

    }

    /**

     * 根据对象删除

     * @param o

     * @return

     */

    public boolean remove(Object o) {

        int index = indexOf(o);

        if (index < ){

            return false;

        }

        deleteLink(index);

        return true;

    }

    /**

     * 检查是否越界

     * @param index

     */

    private void checkRange(int index) {

        if (index >= size || index < ) {

            throw new IndexOutOfBoundsException("指定index超过界限");

        }

    }

    /**

     * 检查是否越界

     * @param index

     */

    private void checkRangeForAdd(int index) {

        if (index > size || index < ) {

            throw new IndexOutOfBoundsException("指定index超过界限");

        }

    }

    /**

     * 在链表的末尾添加新元素

     * @param e

     */

    private void addAtLast(E e){

        Node<E> oldLast = last;

        //构造一个新节点

        Node<E> node = new Node<E>(e, null, last);

        last = node;

        if(null == oldLast){//新增元素是第一个元素时

            first = node;

        }else{//新增元素不是第一个元素时

            oldLast.next = node;

        }

        size ++;

    }

    /**

     * 在指定的元素前面添加一个新元素,维持双向的地址

     * @param e

     * @param curNode

     */

    private void addBeforeNode(E e,Node<E> curNode){

        Node<E> preNode = curNode.pre;

        Node<E> newNode = new Node<E>(e, curNode, preNode);

        if(null == preNode){//插入到第一个节点前时

            first = newNode;

        }else{//非第一个节点前时,需维护前一个节点的next指向

            preNode.next = newNode;

        }

        curNode.pre = newNode;

        size++;

    } 

    /**

     * 根据index查找元素，只能从头开始找或者从尾部开始找

     * @param index

     * @return

     */

    private Node<E> node(int index){

        Node<E> node;

        //采用二分查找的方式，将index与size/2的值进行比较，确定是从头开始找，还是从尾部开始找

        if (index < (size >> )) {//从头开始找

            node = first;

            for(int i = ; i < index; i++){

                node = node.next;

            }

        }else{//从尾开始找

            node = last;

            for(int i = size -; i > index; i--){

                node = node.pre;

            }

        }

        return node;

    }

    /**

     * 链表的长度

     * @return

     */

    public int size(){

        return this.size;

    }

}