//一个节点
class Node<E> {
    public Node next;
    public Node prev;
    public E item;
    public Node(E data) {
        this.item = data;
        next = null;
        prev = null;
    }
}

public class MyLinkedList<E> {
    private Node<E> head; //表头
    private Node<E> tail; //表尾
    private int size;  //表长
    public MyLinkedList() {
        size = 0;
        head = null;
        tail = null;
    }
    public int size() {
        return this.size;
    }
    public void add(E o) {   //将o增加到链表尾部
        Node tempNode = new Node(o);
        if(size == 0){  //节点为空节点的时候
            head = tempNode;
            tail =tempNode;
        }else {
            tail.next = tempNode;
            tempNode.prev = tail;
            tail = tempNode;
        }
        size++;
    }
    public E remove() { //从头移除元素
        return removeFirst();
    }

    public void showList(){
        Node<E> tempNode = head;
        while(tempNode != null){
            System.out.println(tempNode.item + " ");
            tempNode = tempNode.next;
        }
    }
    public void showListRevise(){
        Node<E> tempNode = tail;
        while(tempNode != null){
            System.out.println(tempNode.item + " ");
            tempNode = tempNode.prev;
        }
    }
    public E remove(int index) {  //删除指定位置的元素
        Node<E> tempNode;
        Node<E> resultNode;
        if(index<0 || index>size){
            return null;
        }else {
            if (index < (size >> 1)) {
                tempNode = head;
                for(int i=0;i<index;i++)
                    tempNode = tempNode.next;
                Node<E> par = tempNode.prev;
                Node<E> ch = tempNode.next;
                tempNode.prev.next = tempNode.next;
                tempNode.next.prev = tempNode.prev;
                resultNode = tempNode;
            } else {
                tempNode = tail;
                for(int i=size-1;index<i;i--)
                    tempNode = tempNode.prev;
                resultNode = tempNode;
                tempNode = tempNode.prev;
            }
            size--;
            return resultNode.item;
        }
    }
    public boolean remove(Object o) {
        return removeFirstOccurrence(0);
    }
    public E removeFirst() {
        Node<E> tempNode;
        if(size>0){
            tempNode = head;
            head = head.next;
            head.prev = null;
            size--;
            return tempNode.item;
        }else
            return null;
    }
    public E removeLast() {
        E temp = tail.item;
        tail = tail.prev;
        tail.next = null;
        size--;
        return temp;
    }

    public boolean removeFirstOccurrence(Object o){  //删除此列表中指定元素的第一个出现（从头到尾遍历列表时）。
        int tempSize = size;
        Node<E> tempNode = head;
        for(int i=0;i<tempSize;i++){
            if(tempNode.item.equals(o)){
                tempNode.prev = tempNode.next;
                tempNode.next = tempNode.prev;
                size--;
                return true;
            }
        }
        return false;
    }
    public void addFirst(E o) {  //将o插入链表开头
        Node tempNode = new Node(o);
        if(size==0){
            head = tempNode;
            tail = tempNode;
        }else {
            tempNode.next = head;
            tempNode.prev = null;  //前一个节点是空
            head = tempNode;
        }
        size++;
    }
    public void addLast(E o) {  //将o增加到链表尾部
        Node tempNode = new Node(o);
        if(size==0){
            head = tempNode;
            tail = tempNode;
        }else {
            tail.next = tempNode;
            tempNode.prev = tail;
            tail = tempNode;
        }
        size++;
    }
    public void clear() {  //清空链表
        head = null;
        tail = null;
        size = 0;
    }
    public boolean contains(E o) {  //判断元素o是否包含于链表
        int tempSize = size;
        Node tempNode = head;
        Boolean result = false;
        while (tempSize != 0) {
            Object o1 = tempNode.item;
            if(o.equals(o1)){
                result = true;
            }
            tempNode = tempNode.next;
            tempSize--;
        }
        return result;
    }
    public E get(int index) {  //获取指定节点
        Node<E> tempNode;
        if(index < 0 || index >= size) {
            return null;
        }else {
            if(index < (size >> 1)) {  //右移
                tempNode = head;
                for(int i=0;i<index;i++)
                    tempNode = tempNode.next;
                return tempNode.item;
            }else {
                tempNode = tail;
                for (int i = size-1; index < i; i--) {
                    System.out.println(index+ " " + i);
                    tempNode = tempNode.prev;
                }
                return tempNode.item;
            }
        }
    }
}