//自定义异常
public class LinkedListExecption extends RuntimeException {
    public LinkedListExecption(String message) {
        super(message);
    }

    public LinkedListExecption() {
    }
}

//自定义接口   规范(添加的功能, 具体细节由实现类完成 ...)
public interface MyList<E> {

    //1.添加元素 方便添加各种类型的数据, 使用所有类型的父类Object
    //添加的功能
    void add(E e);

    //2.查询元素
    E get(int index);

    //3.查询存储元素的个数
    int size();

    //4.变更元素
    boolean set(E e, int index);

    //5.删除元素
    boolean remove(int index);

    //6.删除元素
    boolean remove(E e);
}

package com.bjsxt.service;
import com.bjsxt.execption.LinkedListExecption;
//自定义显示类, 实现接口中的规范(添加 删除 修改 变更 获取存储数量)
//双向列表的实现
public class MyLinkedList<E> implements MyList<E> {
    //创建头结点 (只要拿到头结点, 就可以获取到后续的所有结点)
    private Node<E> first;
    //创建尾结点(只要拿到尾结点, 就可以获取前边所有的结点)
    private Node<E> last;
    //记录当前链表中存储了多少个数据(链表没有下表, 此属性就是记录存入数据的个数)
    private int count;

    @Override//查询结点信息  index -> 第几个被添加的数据(从0开始)
    public E get(int index){
        //检查index是否合格
        checkIndex(index);
        return getNode(index).item;
    }


    @Override//返回链表中存储了多少个数据
    public int size() {
        return count;
    }


    //检查用户输入的index是否合格
    private void checkIndex(int index) throws LinkedListExecption {
        if(index<0 || index>count-1){
            throw new LinkedListExecption("输入的index有误, 最大index为 :"+(count-1)+" ,最小index为: 0");
        }
    }



    //创建结点的内部类  此节点内部类只有当前的双向列表需要, 所以创建为内部类
    private class Node<E>{
        //1.前一个结点的地址
        Node<E> pre;
        //2.当前结点的值
        E item;
        //3.下一个节点的地址
        Node<E> next;
        public Node(Node<E> pre, E item, Node<E> next) {
            this.pre = pre;
            this.item = item;
            this.next = next;
        }
    }



    /*
    * 头插和尾插
    *   先添加的结点作为尾节点-> 尾插
    *   先添加的结点作为尾节点-> 头插
    * */
    //尾插法(新插入的结点作为新的尾结点)
    public void addLast(E e){
        //1.将目前的尾结点存储起来(方便后续的操作属性)
        Node<E> oldLast = this.last;
        //2.创建新的结点
        Node<E> newLast = new Node<>(oldLast, e, null);
        //3.将新创建的结点设置为尾结点
        this.last = newLast;
        //4.判断
        if(oldLast == null){//此时链表中,没有任何的结点 新创建的结点即为尾结点又为头结点
            this.first = newLast;
        }else {//链表中存在尾结点, 将旧的尾结点中存储下个结点地址改变为新尾结点的地址
            oldLast.next = newLast;
        }
        count++;
    }


    //头插法(新插入的结点作为新的头结点)
    public void addFirst(E e){
        //1.存储现在的头节点
        Node<E> oldFirst = this.first;
        //2.创建新节点
        Node<E> newFirst = new Node<>(null, e, oldFirst);
        //3.指定新创建的结点尾头结点
        this.first = newFirst;
        //4.判断
        if(oldFirst == null){//5.链表中没有结点, 新插入的结点即为头结点又为尾结点
            this.last = newFirst;
        }else{
            oldFirst.pre = newFirst;
        }
        count++;
    }

    @Override//向链表中添加数据
    public void add(E e) {
        //使用add插入时, 默认尾插
        addLast(e);
    }



    @Override//修改节点中值  第几个数据从0开始
    public boolean set(E e, int index) {
        checkIndex(index); //检查index是否合格
        try {
            //1.获取要修改值得节点
            Node<E> node = getNode(index);
            //2.修改节点中的值
            node.item = e;
            return true;
        } catch (Exception ex) {
            ex.printStackTrace();
            return false;
        }
    }


    @Override//删除节点  第几个数据从0开始
    public boolean remove(int index) {
        //检查index是否合格
        checkIndex(index);
        //1.获取删除的节点(头节点 尾节点  非头非尾)
        Node<E> node = getNode(index);
        //Node<E> pre = node.pre; //该节点的上个节点
        //Node<E> next = node.next;//该节点的下个节点
        //情况一: 删除的为头节点(node.pre==null)
        if(node.pre==null){
            Node<E> next = node.next;
            next.pre = null;
            this.first = next; //设置新的头节点
        }else if(node.next==null){//情况二: 删除的为尾节点(node.next==null)
            Node<E> pre = node.pre;
            pre.next = null;
            this.last = pre;//设置新的尾节点
        }else{//情况三: 删除的为非尾节点非头节点
            /*
            * 1.将该节点的上个节点 存储下个节点的地址 改成该节点的下个节点
            * 2.将该节点的下个节点 存储上个节点的地址 改成该节点的上个节点
            * */
            Node<E> pre = node.pre; //该节点的上个节点
            Node<E> next = node.next;//该节点的下个节点
            pre.next = next;
            next.pre = pre;
        }
        node = null;
        count--;
        return true;
    }



    //获取节点方法
    private Node<E> getNode(int index){
        //查询的优化
        /*
         *   如果index < ((cout-1)>>1) 从前向后查询
         *   如果index >= ((cout-1)>>1) 从向前后查询
         * */
        /*if(index == 0){
            return this.first.item;
        }
        if(index == count-1){
            return this.last.item;
        }*/
        if (index < ((count)>>1)) { //如果index < ((cout-1)>>1) 从前向后查询
            //1.获取头结点
            Node<E> node = this.first;
            //2.根据index遍历  index->用户添加的第几个数据(从零开始计算的)
            for (int i = 0; i < index; i++) {
                //获取下一个节点 赋值给当前的node变量
                node = node.next;
            }
            return node;
        } else { //如果index > ((cout-1)>>1) 从向前后查询
            //1.获取尾结点
            Node<E> node = this.last;
            //2.根据index遍历  index->用户添加的第几个数据(从零开始计算的)
            for (int i = 0; i < count-1-index; i++) {
                node = node.pre;
            }
            return node;
        }
    }


}