package linked;

/**
 * @date 2023/4/26 22:51
 * @description 单链表
 */
public class SingleLinkedList {

    private int size = 0;

    private Node head;

    private Node tail;

    public static class Node {
        private Object data;
        private Node next;

        public Node(Object data) {
            this.data = data;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node getNext() {
            return next;
        }

        public Object getData() {
            return data;
        }
    }

    /**
     * 头插法
     * @param data
     */
    public void headAddData(Object data) {
        if(size == 0) {
            head = new Node(data);
            tail = head;
        } else {
            Node node = new Node(data);
            node.setNext(head);
            head = node;
        }
        size ++;
    }

    /**
     * 尾插法
     * @param data
     */
    public void tailAddData(Object data) {
        if(size == 0) {
            head = new Node(data);
            tail = head;
        } else {
            Node node = new Node(data);
            tail.setNext(node);
            tail = node;
        }
        size ++;
    }

    /**
     * 获取索引位置的数据
     * @param index
     * @return
     */
    public Object getData(int index) {
        if(size == 0) {
            throw new NullPointerException();
        }
        if(index < 0 || index > size - 1) {
            // todo 抛一个链表越界错误
        }
        if(index == 0) {
            return head.getData();
        }
        if(index == size - 1) {
            return tail.getData();
        }
        Node node = head;
        int i = 0;
        while (node.getNext() != null && index != i) {
            node = node.getNext();
            i ++;
        }
        return node.getData();
    }

    /**
     * 插入index的位置·
     * @param index
     * @param data
     */
    public void addData(int index, Object data) {
        if(head == null) {
            throw new NullPointerException();
        }
        if(index < 0 || index > size - 1) {
            // todo 抛一个链表越界错误
        }
        size ++;
        if(index == 0) {
            headAddData(data);
            return;
        }
        if(index == size - 1) {
            tailAddData(data);
            return;
        }
        Node node = head;
        Node preNode = null;
        int i = 0;
        while (node.getNext() != null) {
            if(i == index) {
                break;
            }
            preNode = node;
            node = node.getNext();
            i ++;
        }
        Node newNode = new Node(data);
        preNode.setNext(newNode);
        newNode.setNext(node);
    }

    /**
     * 删除目标位置的节点
     * @param index
     */
    public void delete(int index) {
        if(head == null) {
            throw new NullPointerException();
        }
        if(index < 0 || index > size - 1) {
            // todo 抛一个链表越界错误
        }
        size --;
        if(index == 0) {
            Node node = head;
            node = node.next;
            head.setNext(null);
            head = node;
            if(size == 1) {
                tail = null;
            }
            return;
        }
        Node node = head;
        Node preNode = null;
        int i = 0;
        while(node.getNext() != null) {
            preNode = node;
            node = node.getNext();
            i ++;
            if(i != index) {
                continue;
            }
            preNode.setNext(node.getNext());
            node.setNext(null);
            break;
        }
    }

    public String toString() {
        String s = "[]";
        if(size <= 0) {
            return s;
        } else if(size == 1) {
            s = "[" + head.getData() + "]";
            return s;
        } else {
            Node node = head;
            s = "[" + node.getData();
            while(node.getNext() != null) {
                node = node.getNext();
                s += "," + node.getData();
                if(node.getNext() == null) {
                    s += "]";
                }
            }
            return s;
        }
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.headAddData(1);
        singleLinkedList.headAddData(2);
        singleLinkedList.headAddData(3);
        singleLinkedList.headAddData(4);
        singleLinkedList.headAddData(5);

        singleLinkedList.addData(1, 99);


        System.out.println(singleLinkedList);
        System.out.println(singleLinkedList.getData(1));

        singleLinkedList.delete(5);
        System.out.println(singleLinkedList);
    }

}