// 定义链表的接口
interface ILink<E>{
    public void add(E e);  // 添加元素
    public int size();     // 获取元素个数
    public boolean isEmpty();  // 判断是否为空
    public Object[] toArray();  //转为对象数组
    public E get(int index);  // 根据索引取得数据
    public void set(int index, E data);  //修改数据
    public boolean contains(E data); // 判断数据是否存在
    public boolean remove(E data);  // 链表数据
    public void clean();  // 清空链表
}
// 实现链表
class LinkImpl<T> implements ILink<T>{
    private Node<T> rootNode;  // 记录头指针
    private int count ;    // 计数统计
    private Object[] dataList; // 数据列表
    private int foot; //角标
    // 链表节点，内部类，便于外部类直接访问其私有属性
    private class Node<T>{
        private T data;   // 数据
        private Node<T> nextNode; // 下一节点
        public Node(T data){
            this.data = data ;
        }
        public void addNode(Node<T> node){
            if(!this.hasNextNode()){
                this.nextNode = node;
            } else{
                this.nextNode.addNode(node);
            }
        }
        public boolean hasNextNode(){
            return this.nextNode != null;
        }
        public void toArrayNode(){
            LinkImpl.this.dataList[LinkImpl.this.foot++] = this.data;
            if(this.hasNextNode()){
                this.nextNode.toArrayNode();
            }
        }
        public Node<T> getNode(int index){
            if(LinkImpl.this.foot++ == index){
                return this ;
            }else{
                return this.nextNode.getNode(index);
            }
        }
        public boolean containsNode(T data){
            // 比较对象 不能是null
            if(this.data.equals(data)){
                return true;
            } else {
                // 有后续节点继续
                if(this.hasNextNode()){
                    return this.nextNode.containsNode(data);
                } else {
                    // 没有找到数据
                    return false;
                }
            }
        }
        public boolean removeNode(Node<T> preNode, T data){
            if(this.data.equals(data)){
                preNode.nextNode = this.nextNode;
                return true;
            } else {
                // 有后续节点，继续移除操作
                if(this.hasNextNode()){
                    return this.nextNode.removeNode(this, data);    
                } else{
                    return false;
                }
            }
        }
    }
    public void add(T data){
        // 不接受null 类型的值
        if(!isValidData(data)){
            return;
        }
        Node<T> newNode = new Node<T>(data);
        // 添加第一个元素的时候，头节点为null
        if (this.count == 0){
            this.rootNode = newNode;
        } else {
            this.rootNode.addNode(newNode);
        }
        this.count++;
    }
    public int size(){
        return this.count;
    }
    public boolean isEmpty(){
        return this.count == 0;
    }
    public Object[] toArray(){
        if(this.isEmpty()){
            return null;
        }
        // 角标清零，创建空数组
        this.foot = 0;
        this.dataList = new Object[this.count];
        // 递归获取节点数据
        this.rootNode.toArrayNode();
        return this.dataList;
    }
    // 检查索引是否在有效范围内
    private boolean isValidIndex(int index){
        if(index < 0 || index >= count){
            return false;
        } else{
            return true;
        }
    }
    // 检查是否为有效数据
    private boolean isValidData(T data){
        if(data == null){
            return false;
        } else{
            return true;
        }
    }
    public T get(int index){
        if(!this.isValidIndex(index) || this.isEmpty()){
            return null ;
        }
        // 重置下标
        this.foot = 0;
        return this.rootNode.getNode(index).data;
    }
    public void set(int index, T data){
        if(!this.isValidIndex(index) || this.isEmpty() ){
            return ;
        }
        // 重置下标
        this.foot = 0;
        this.rootNode.getNode(index).data = data;
    }
    public boolean contains(T data){
        if(!isValidData(data) || this.isEmpty()){
            return false;
        }
        return this.rootNode.containsNode(data);
    }
    public boolean remove(T data){
        if(!isValidData(data) || this.isEmpty()){
            return false;
        }
        boolean removeResult = false;
        // 移除头节点
        if(this.rootNode.data.equals(data)){
            this.rootNode = this.rootNode.nextNode; 
            removeResult = true;
        } else{
            removeResult = this.rootNode.nextNode.removeNode(this.rootNode, data);
        }
        if(removeResult == true){
            this.count --;
        }
        return removeResult;
    }
    public void clean(){
        this.rootNode = null;
        this.count = 0;
    }
    public void printLink(){
        Object[] list = this.toArray();
        if (list == null){
            System.out.println("null");
            return;
        }
        for(int i=0; i < this.count; i++){
            if(i == 0){
                System.out.print("[ ");
            } else {
                System.out.print("-> ");
            }
            System.out.print(list[i]); 
            if (i == count - 1){
                System.out.print(" ]");
            }           
        }
        System.out.println();
    }
}
class Demo{
    public static void main(String[] args) {
        LinkImpl<Integer> link = new LinkImpl<Integer>();
        System.out.println("添加前：" + link.size() + " " + link.isEmpty());
        // 添加前：0 true
        link.add(2);
        link.add(3);
        link.add(4);
        link.add(5);
        System.out.println("添加后：" + link.size() + " " + link.isEmpty());
        // 添加后：4 false
        link.printLink();
        // [ 2-> 3-> 4-> 5 ]
        System.out.println(link.get(2));
        // 4
        link.set(2, 6);
        System.out.println(link.get(2));
        // 6
        System.out.println(link.contains(10)); // false
        System.out.println(link.contains(5)); // true
        link.printLink();
        // [ 2-> 3-> 6-> 5 ]
        link.remove(2);
        System.out.println(link.contains(2));
        link.printLink();
        // [ 3-> 6-> 5 ]
        link.clean();
        link.printLink();
        // null
    }
}