package stackandqueue.stack.link;

/**
 * linkedlist的实现原理就是双向链表结构
 *
 * @author tianzhuang
 * @version 1.0
 * @date 2021/11/16 16:40
 */
public class DoubleLinkList {
    class Node{
        private int val;
        private Node next;
        private Node pre;

        public Node(int val) {
            this.val = val;
        }
    }

    // 头节点
    private Node first;

    // 尾节点
    private Node last;

    public DoubleLinkList() {
        this.first = null;
        this.last = null;
    }

    /**
     * 头插入数据
     * @param val
     */
    public void firstAddd(int val) {
        Node newNode = new Node(val);
        // 判断如果头指针为空，则说明链表为空，将头指针first和尾指针last指向插入的数据
        if (first == null) {
            last = newNode;
            first = newNode;
        } else {
        // 头指针不为空，将当前头节点first的pre指向新建节点，将新建节点的next指向头节点first， 然后将头节点first重新指向新建节点
            first.pre = newNode;
            newNode.next = first;
            first = newNode;
        }
        // 优化版
/*        if (first == null) {
            last = newNode;
        } else {
            first.pre = newNode;
            newNode.next = first;
        }
        first = newNode;
*/
    }

    /**
     * 尾插入
     * @param val
     */
    public void lastAdd(int val) {
        Node newNode = new Node(val);
        // 判断最后一个节点是否尾空，为空说明当前链表尾空，将头节点first和尾节点last都指向当前新建的节点
        if (last == null) {
            first = newNode;
            last = newNode;
        } else {
        // 当前节点不为空时， 将新建节点的pre指向尾节点last，next本身就为空，代表自己是最后一个节点。
            newNode.pre = last;
            // 将当前尾节点的next指向新建节点
            last.next = newNode;
            // 将尾节点last重新指向新建节点
            last = newNode;
        }
        // 优化版
/*
        if (last == null) {
            first = newNode;
        } else {
            newNode.pre = last;
            last.next = newNode;
        }
        last = newNode;
*/

    }

    /**
     * 删除最后一个节点
     * @return
     */
    public void deleteLast(){
        if (last == null) {
            throw new RuntimeException("节点为空");
        }
        // 将last节点的的pre节点的next节点指向null，然后将last节点指向pre节点，这样最后一个节点就被删除了
        Node pre = last.pre;
        pre.next = null;
        last = pre;
    }

    /**
     * 删除第一个节点
     * @return
     */
    public void deleteFirst(){
        if (first == null) {
            throw new RuntimeException("节点为空");
        }
        // 将first节点的的next节点的pre节点指向null，然后将first节点指向next节点，这样最后一个节点就被删除了
        Node next = first.next;
        next.pre = null;
        first = next;
    }

    /**
     * 删除指定位置的节点
     *
     * @param index
     */
    public void delByIndex(int index) {
        if (index < 0 || index > count()) {
            throw new RuntimeException("索引错误");
        }
        if (first == null || last == null) {
            throw new RuntimeException("链表为空");
        }
        Node node = first;
        int i = 1;
        while (node != null) {
            if (i == index) {
                // 获取指定位置的节点
                Node pre = node.pre;
                // 判断节点的pre是否为空，为空则将第一个节点删除，调用deleteFirst()方法
                if (pre == null) {
                    deleteFirst();
                    return;
                }
                // 判断节点的next是否为空，为空则将最后一个节点删除，调用deleteLast()方法
                Node cur = node.next;
                if (cur == null) {
                    deleteLast();
                    return;
                }
                // 将当前节点的pre的next指向当前节点的next，将当前节点的next的pre指向当前节点的pre
                pre.next = cur;
                cur.pre = pre;
            }
            node = node.next;
            i++;
        }
    }


    /**
     * 指定位置添加节点
     *
     * @param index
     */
    public void addByIndex(int index, int val) {
        if (index <= 0 || index > count()) {
            throw new RuntimeException("索引错误");
        }
        if (first == null || last == null) {
            firstAddd(val);
        }
        Node node = first;
        int i = 1;
        while (node != null) {
            if (i == index) {
                // 获取指定位置的节点
                Node pre = node.pre;
                // 判断节点的pre是否为空，为空则将添加的节点放到头节点，调用firstAddd()方法
                if (pre == null) {
                    firstAddd(val);
                    return;
                }
                // 判断节点的next是否为空，为空则将添加的节点放到最后，调用lastAdd()方法
                Node cur = node.next;
                if (cur == null) {
                    lastAdd(val);
                    return;
                }
                // 将当前节点node的pre指向新建节点，将新建节点的next指向当前节点node
                // 将当前节点的pre的next指向新建节点，将新建节点的pre指向当前节点的pre
                Node newNode = new Node(val);
                pre.next = newNode;
                node.pre = newNode;
                newNode.next = node;
                newNode.pre = pre;
            }
            node = node.next;
            i++;
        }
    }


    /**
     * 查询链表长度
     *
     * @return
     */
    public int count() {
        if (first == null || last == null) {
            return 0;
        }
        Node fir = first;
        int count = 0;
        while (fir != null) {
            count++;
            fir = fir.next;
        }
        return count;
    }

    /**
     * 打印所有节点
     */
    public void print() {
        if (first == null) {
            throw new RuntimeException("节点为空");
        }
        Node curr = first;
        while (curr != null) {
            System.err.print(curr.val+" ");
            curr = curr.next;
        }
    }

    public static void main(String[] args) {
        DoubleLinkList doubleLinkList = new DoubleLinkList();
        doubleLinkList.lastAdd(2);
        doubleLinkList.lastAdd(3);
        doubleLinkList.lastAdd(4);
        doubleLinkList.lastAdd(7);
        doubleLinkList.firstAddd(1);
        doubleLinkList.firstAddd(0);
        doubleLinkList.print();
        System.err.println("============分割"+doubleLinkList.count());
        // 删除最后一个节点
/*        doubleLinkList.deleteLast();
        doubleLinkList.print();*/
        // 删除头节点
/*        doubleLinkList.deleteFirst();
        doubleLinkList.print();
        System.out.println(doubleLinkList.count());*/
        // 删除指定位置的节点
        /*doubleLinkList.delByIndex(1);
        doubleLinkList.print();*/
        // 指定位置添加节点
        doubleLinkList.addByIndex(1, 8);
        doubleLinkList.print();

    }
}