//节点类
class Node {
    public int date;
    public Node next;

    public Node(int date) {
        this.date = date;
        this.next = null;
    }
}

class LinkedList {
    private Node head; //头节点
    private int size; //链表长度

    //构造方法，初始化类
    public LinkedList() {
        this.head = null;
        this.size = 0;
    }

    //获取链表长度
    public int getSize() {
        return size;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return head == null;
    }

    //在后面追加元素
    public void addElement(int date) {
        if (isEmpty()) {
            head = new Node(date);
        } else {
            Node node = head;
            while (node.next != null) {
                node = node.next;
            }
            node.next = new Node(date);
        }
        size++;
    }

    //查找元素,寻找第一个符合条件的
    public int findElement(int target) {
        if (isEmpty()) return -1;
        int index = -1;
        Node node = head;
        while (node != null) {
            index++;
            if (node.date == target) {
                return index;
            }
            node = node.next;
        }
        return -1;
    }

    //打印链表
    public void printList() {
        System.out.print("[");
        if (isEmpty()) return;
        Node node = head;
        while (node != null) {
            System.out.print(node.date);
            node = node.next;
            if (node != null) {
                System.out.print(" ,");
            }
        }
        System.out.println("]");
    }

    //在固定索引插入值
    public void insertElement(int index, int element) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException();
        }
        size++;
        //如果是在头节点插入
        if (index == 0) {
            Node tmp = head;
            head = new Node(element);
            head.next = tmp;
            return;
        }
        //其他位置
        Node node = head;
        //寻找插入节点的前一个节点
        for (int i = 0; i < index - 2; i++) {
            node = node.next;
        }
        Node currentNode = node.next; //记录先前的要插入位置的节点值
        node.next = new Node(element); //给指定位置增加值
        node.next.next = currentNode; //将原来节点链接上
    }
    //删除链表某一个节点
    public void deleteNode(int var){
        Node sentinel = new Node(0);
        sentinel.next = head;

        Node prev= sentinel;
        Node current = head;
        while (current != null){
            if(current.date == var){
                prev.next=current.next;
            }else {
                prev = current;
            }
            current = current.next;
        }
        head = sentinel.next;
    }


}

class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.addElement(1);
        linkedList.addElement(1);
        linkedList.addElement(1);
        linkedList.addElement(3);
        linkedList.addElement(5);
        linkedList.addElement(7);
        linkedList.addElement(9);
        System.out.println("链表长度为：" + linkedList.getSize());
        linkedList.printList();
        System.out.println("数字3第一次出现的索引为："+linkedList.findElement(3));
        linkedList.insertElement(1, 5);
        linkedList.printList();
        System.out.println("链表长度为：" + linkedList.getSize());
        System.out.println("数字3第一次出现的索引为："+linkedList.findElement(3));
        System.out.print("删除前：");
        linkedList.printList();
        linkedList.deleteNode(1);
        System.out.print("删除后：");
        linkedList.printList();
    }
}