2021-9-下旬 数据结构-线性表-链表-java代码实现（复习用）

链表涉及到指针了，这里我还不了解java里对指针的隐藏，又由于以前学过C++里的指针，二者混淆，导致一开始非常蒙，出了很多问题，当然后来随着边写边查，基本都解决了。
顺便学习了一下java里的泛型

//链表是一种“链式存储”的线性表，所有元素的内存地址不一定是连续的，在结构上已经完全不是数组了
//普通线性表有个大缺点，可能会造成内存空间的浪费，有些位置不存元素时也占用内存
//那么能不能用到多少就申请多少内存呢？？  所以链表出现了

//在定义链表类时，一般在定义链表大类中定义一个子类结点类
//链表在结构上，是由头结点和结点组成的，头结点存储指向第一个结点的地址，这里头结点其实就是个指针变量
//链表的大部分接口和线性表一致，但是实现方法不同，因此不能直接继承

//顺带一提，java中类 A b=a；b改变a也会改变，二者指向同一块内存
public class linkedListZH {
    public static final  int ELEMENT_NOT_FOUND = -1;

    private int size;//定义全局变量（不在函数里的）不初始化默认初始值为0，局部变量则初始值随机

    private Node headNode;
    //什么找到index为2的元素只需要两次headnode=headnode.next？？？
    //为什么老师的headNode就是第一个结点（除了所谓头结点）？？？
    //把headNode想象成单纯一个指向第一个结点的指针就通了！！！，也就是说有第一个结点时headNode就是第一个节点，没有第一个结点时，
    //headNode为null，但是具体原理在java里我依然没整明白，难道说headNode这个名本身代表的就是一个地址，所以
    //所以插入第一个元素时，headNode直接 =new Node<>（element，headNode（这时为null））就代表headNode就指向了第一个结点，也意味着在java里headnode就是第一个结点的引用？
    //如果这时候用headNode.next = node（element，headNode.next）就会报错"this.headNode" is null
    //是因为我们根本没设置headNode，headnode为null吗，导致空指针错误

    private static class Node {
        E element;
        Node next = null;
        //JAVA把指针淡化了，C中需要Node *p = next；next -> nextNode;,Java中只要next=nextNode就可以了
        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
    }

    public void clear(){
        headNode = null;
        size = 0;
    }

    public void isEmptyPrint(){
        if (headNode == null){
            System.out.println("Empty");
        }else{
            System.out.println("Not Empty");
        }
    }

    //是否包含，一定记得看看有没有多余句子写到循环里了
    public void containsPrint(E element){
        Node node = headNode;
        for(int i = 0;i < size ; i++){
            if (node.element == element){
                System.out.println("Contain");
                return;
            }
            node = node.next;
        }
        System.out.println("Not Contain");
    }

    //痛苦add，看前面，这里headNode。next和headNode的问题想了我快两个点
    public void add(int index , E element){
        if ( index == 0){
            Node node = new Node<>(element,headNode);
            headNode = node;
        }else {
            Node node = indexSearchNode(index - 1);
            node.next = new Node<>(element,node.next);
        }
        size++;
    }

    public void remove(int index){
        if (index == 0){
            headNode = headNode.next;
        }else{
            Node pre = indexSearchNode(index - 1);
            pre.next = pre.next.next;
        }
        size--;
        //别忘了动size啊啊啊啊！！！！
    }

    public void add(E element){
        add(size,element);
    }

    //根据索引返回对应结点，注意返回值是Node而不是E,该函数经常在别的函数内使用
    private Node indexSearchNode (int index){
        Node node = headNode;
        for(int i = 0; i < index ; i ++){
            node = node.next;
        }
        return node;
    }

    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append("  [");
        Node node = headNode;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(node.element);

            node = node.next;
        }
        string.append("]");
        return string.toString();
    }

}