java - 关于单链表实现的一个stack的问题

Question

背景：菜鸟一枚，想补补基础。最近在看算法，1.3.26有一道题是：编写一个方法remove()接受一条链表和一个字符串key作为参数，删除链表中所有的item域为key的节点。 上代码： {代码...} 但是一经测试就报java.lang...

ringa_lee · Answer

Before I was outside, the question itself was not interesting. The first floor was very interesting, and there were 2 people who liked it.
I’m afraid it’s better to teach a man to fish than to teach a man to fish with just one sentence . Aroused approval, which is especially easy to resonate with issues like lz's reaching out to the party. 授人鱼不如授人以渔。引起了赞同，在lz这样类伸手党的问题下特别容易引发共鸣。
找到空指针的引用后，就向前找这个引用的初始化的逻辑部分。这句话有点误导的作用。
最后贴上来的代码也是醉了..题意都没看清，first.next.equals(null)After finding the reference of the null pointer, look forward to the initialization logic part of this reference. This sentence is a bit misleading.
The last code I posted was too confusing. I didn’t even understand the meaning of the question. I didn’t want to complain about code like first.next.equals(null). Can you do something practical? Even if it’s like @hsfzxjy on the 2nd floor

Let’s talk about the error first. Did no one find this error?

nowNode.next.equals(null)

xxx.equals(null) and xxx == null
The difference is that if the program can run normally
xxx.equals(null) must only return falsexxx == null may return true or false

Because if xxx is null
xxx.equals(null) will throw NullPointerException

xxx == null returns true

Then there’s the logic problem

At the last key, the next next is null

So at

else if (nowNode.item.equals(key)){
                    frontNode.next = nowNode.next;            
                    nowNode.next=null;
                    nowNode = frontNode.next;
                    StdOut.print("已搜索到该字符串！");
            }

frontNode.next will point to null, and nowNode will point to null.

Improvements to your code:

    public void remove(String key) {
        // 首先肯定是一个能够不停next直到没有的循环
        // 第二个就是要时时刻刻记住上一个节点，这样便于移除现在的节点
        // 然后就是对等于key和不等于key的逻辑判断
        // 先判断nowNode.next == null，如果是，说明已经到了尾部，结束循环
        // 相等：移除节点，上一个节点还是原先的上一个节点，但会连接至“被移除节点”的next，继续循环
        // 不相等：frontNode变更为nowNode，继续循环
        Node nowNode = first;
        Node frontNode = null;
        while (true) {
            n++;
            if (nowNode == null ) {
                StdOut.print("搜索结束");
                break;
            } 
            if (nowNode.item.equals(key)) {
                StdOut.print("已搜索到该字符串！");
                // 删除节点的操作
                //但是第一次就找到关键字就SB了，frontNode直接为空
                frontNode.next = nowNode.next;
                // 如果nowNode是最后一个，frontNode也会指向null
                if (frontNode.next == null ) {
                    StdOut.print("搜索结束");
                    break;
                } 
                nowNode.next = null;
                nowNode = frontNode.next;
            }
            else {
                frontNode = nowNode;
                nowNode = nowNode.next;
            }
        }
    }

I implemented it based on your ideas, leaving a question for you. In addition, I don’t count the settlement method very much. Please forgive me if the answer does not satisfy you. 🎜

迷茫 · Answer

When first 为目标时，161 行 frontNode.next an error will be reported

When the linked list is empty, an error will be reported on lines 157 and 167 nowNode.next

You can’t do it now, why don’t you follow it step by step

怪我咯 · Answer

——————————Supplementary content————————————————
Additional note: The == symbol compares the values of the variables on both sides of the equal sign , so when used to compare two object references, the memory addresses of the two references are compared. The equals method can indeed be used to compare the specific contents of references.
For example

String str1 = new String("123");

String str2 = new String("123");
str1 == str2;//这个值就是false了，虽然内容都是“123”，比较的是两个引用地址。
str1.equals(str2);/这个就是true

So == can only be used when judging whether it is null. Otherwise, it is best to use equals method if you can, because most variables in Java are reference types.
————————————————————————————————————————

The title has been updated. This is a modification of the remove part.
Don’t use the form of xxx.equls(null) when it is judged to be empty. xxx may also be empty. In the future, you can directly use the == symbol to judge or customize a boolean isEmpty (Object o) tool method

public void remove(String key) {
    //首先肯定是一个能够不停next直到没有的循环
    //第二个就是要时时刻刻记住上一个节点，这样便于移除现在的节点
    //然后就是对等于key和不等于key的逻辑判断
    //先判断nowNode.next == null，如果是，说明已经到了尾部，结束循环
    //相等：移除节点，上一个节点还是原先的上一个节点，但会连接至“被移除节点”的next，继续循环
    //不相等：frontNode变更为nowNode，继续循环
    Node nowNode = first;
    Node frontNode = null;
    while(true){
        //栈为空的时候，这里会报错，先判断栈是否为空
        //nowNode为空是结束循环
        if (isEmpty()||nowNode == null){
            StdOut.print("没有拥有该字符串的item");
            break;
        }else if (nowNode.item.equals(key)){//链表进行增删改查，在链子的首，尾，中间的算法是不同的，要分开来处理
            if(nowNode.next == null) {//目标是结尾元时，                       
                frontNode.next = nowNode.next;
                nowNode = frontNode;

            } else if(frontNode == null) {//目标是首元素时
                first = nowNode.next;
                nowNode.next = null;
            } else {                       //目标是和中间元素时
                frontNode.next = nowNode.next;
                nowNode.next=null;
                nowNode = frontNode.next;
            }
            StdOut.print("已搜索到该字符串！");
            break;

        }else {
            frontNode = nowNode;
            nowNode = nowNode.next;
        }
    }
}

——————————————————————————————Old Update—————————————— ————————————————————————
Still took a quick look.

public boolean find(String key) {

    Node nowNode = first;
    while (true) {
        //这里加上一行健壮性判断。栈空了就不要继续遍历了
        //nowNode为空也要结束循环
        if(isEmpty()||nowNode == null)                
            return false;
        if (nowNode.item.equals(key)) {
            System.out.print("output : true");
            return true;
            // 链表没有下一个了
        } else if (first.next.equals(null)) {
            System.out.print("output : false");
            return false;
        }
        nowNode = nowNode.next;
        System.out.println("then next~");
    }

}
————————————————一下原文————————————————————————————————————————————————
授人鱼不如授人以渔。

After reporting the error, java.lang.NullPointerException, continue to look down and find the first line containing the package name of your class. The number after that line is the number of lines where you made the error.
After finding the reference of the null pointer, look forward to the initialization logic part of this reference.