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

Question

背景：菜鸟一枚，想补补基础。最近在看算法，1.3.26有一道题是：编写一个方法remove()接受一条链表和一个字符串key作为参数，删除链表中所有的item域为key的节点。

上代码：

public class Stack<Item> implements Iterable<Item> {
    private Node<Item> first; // top of stack
    private int n; // size of the stack

    // helper linked list class
    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    /**
     * Initializes an empty stack.
     */
    public Stack() {
        first = null;
        n = 0;
    }

    /**
     * Returns true if this stack is empty.
     *
     * @return true if this stack is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in this stack.
     *
     * @return the number of items in this stack
     */
    public int size() {
        return n;
    }

    /**
     * Adds the item to this stack.
     *
     * @param item
     *            the item to add
     */
    public void push(Item item) {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    /**
     * Removes and returns the item most recently added to this stack.
     *
     * @return the item most recently added
     * @throws NoSuchElementException
     *             if this stack is empty
     */
    public Item pop() {
        if (isEmpty())
            throw new NoSuchElementException("Stack underflow");
        Item item = first.item; // save item to return
        first = first.next; // delete first node
        n--;
        return item; // return the saved item
    }

    /**
     * Returns (but does not remove) the item most recently added to this stack.
     *
     * @return the item most recently added to this stack
     * @throws NoSuchElementException
     *             if this stack is empty
     */
    public Item peek() {
        if (isEmpty())
            throw new NoSuchElementException("Stack underflow");
        return first.item;
    }

    /**
     * Returns a string representation of this stack.
     *
     * @return the sequence of items in this stack in LIFO order, separated by
     *         spaces
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    }

    // 1.3.20
    public void delete(int k) {

        // 不允许大于n的值
        if (k <= n) {
            Node<Item> nowNextNode = first;
            // 要第几个就next到第几个的上一个
            for (int i = 1; (k - 1) != i; i++) {
                nowNextNode = nowNextNode.next;
            }
            // 删除节点
            Node<Item> needLinePoint = nowNextNode.next.next;
            nowNextNode.next = needLinePoint;
        } else {
            // 这里简单的打印一下
            StdOut.print("!------------------删除元素越界！------------------!");
        }
    }

    // 1.3.21
    public boolean find(String key) {
        // 其实也可以用foreach
        Node<Item> nowNode = first;
        while (true) {
            if (nowNode.item.equals(key)) {
                StdOut.print("output : true");
                return true;
                // 链表没有下一个了
            } else if (first.next.equals(null)) {
                StdOut.print("output : false");
                return false;
            }
            nowNode = nowNode.next;
            StdOut.println("then next~");
        }

    }

    // 1.3.24 
    public void removeAfter(Node<Item> node) {
        if (node == null || node.next == null) {
            // 什么也别做
        } else {
            if (isEmpty())
                throw new NoSuchElementException("Stack underflow");
            Node<Item> tempNode = node.next.next;
            node.next = null;
            node.next = node.next.next;
            n--;
        }
    }

    //1.3.26 接受一个链表和一个字符串key作为参数，删除链表中所有item域为key的节点
    // 那么为了降低难度，直接写成对this产生作用的方法
    public void remove(String key) {
        //首先肯定是一个能够不停next直到没有的循环
        //第二个就是要时时刻刻记住上一个节点，这样便于移除现在的节点
        //然后就是对等于key和不等于key的逻辑判断
          //先判断nowNode.next == null，如果是，说明已经到了尾部，结束循环
          //相等：移除节点，上一个节点还是原先的上一个节点，但会连接至“被移除节点”的next，继续循环
          //不相等：frontNode变更为nowNode，继续循环
        Node<Item> nowNode = first;
        Node<Item> frontNode = null;
        while(true){
            if (nowNode.next.equals(null)){
                StdOut.print("没有拥有该字符串的item");
                break;
            }else if (nowNode.item.equals(key)){
                    frontNode.next = nowNode.next;            
                    nowNode.next=null;
                    nowNode = frontNode.next;
                    StdOut.print("已搜索到该字符串！");
            }else {
              frontNode = nowNode;
              nowNode = nowNode.next;
            }
        }
    }

    /**
     * Returns an iterator to this stack that iterates through the items in LIFO
     * order.
     *
     * @return an iterator to this stack that iterates through the items in LIFO
     *         order
     */
    public Iterator<Item> iterator() {
        return new ListIterator<Item>(first);
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ListIterator<Item> implements Iterator<Item> {
        private Node<Item> current;

        public ListIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext() {
            return current != null;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext())
                throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

}

但是一经测试就报java.lang.NullPointerException，为什么？
详细错误：

java.lang.NullPointerException
    at Unit1.Stack.remove(Stack.java:168)
    at Unit1.StackTest.Test(StackTest.java:19)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
    at java.lang.reflect.Method.invoke(Unknown Source)
    at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
    at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
    at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
    at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
    at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
    at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
    at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
    at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
    at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
    at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
    at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
    at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:86)
    at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:459)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:678)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:382)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:192)

测试里相关的代码：

public class StackTest {

    @Test
    public void Test() {

        Stack<String> stack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (item.equals("find")) {
                stack.find("3");
            }
            else if (item.equals("remove")) {
                stack.remove("1");
            }
            else if (item.equals("del")) {
                stack.delete(3);
            }
            else if (!item.equals("-")) {
                stack.push(item);
            } 
            else if (!stack.isEmpty()) {
                StdOut.print(stack.pop() + " ");
            }

        }
        StdOut.println("(" + stack.size() + " left on stack)");
    }
}

报错行是stack里的

            if (nowNode.next.equals(null)){

以及测试里的

        stack.remove("1");

但是我认为一楼的答案并不是很好...找到空指针的引用后，就向前找这个引用的初始化的逻辑部分。
初始化部分：

        Node<Item> nowNode = first;
        Node<Item> frontNode = null;

我很同意授人鱼不如授人以渔。然而...
StdIn是一个能够不停输入的函数。
测试数据输入的是
1
2
3
4
5
remove
感谢各位！问题似乎已经解决了！附上代码：

    public void remove(String key) {
        // 首先肯定是一个能够不停next直到没有的循环
        // 然后就是对等于key和不等于key的逻辑判断
        // 先判断nowNode== null，如果是，说明已经到了尾部，结束循环。同样nowNode.next == null也是
        Node<Item> nowNode = first;
        while (true) {
            if (nowNode == null ) {
                StdOut.println("搜索结束");
                break;
            } 
            if (nowNode.item.equals(key)) {
                StdOut.println("已搜索到该字符串！");
                if (nowNode.next == null){
                    StdOut.println("已到达底端，退出！");
                    break;
                }
                //删除节点操作
                //临时存储的对象：直接让nextNode和nowNode交换
                Node<Item> nextNode ;
                nextNode = nowNode.next;
                nowNode.item = nextNode.item;
                nowNode.next = nextNode.next;
                nextNode = null;
            }
            else {
                nowNode = nowNode.next;
            }
        }
    }

Answer 1

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 false

xxx == 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<Item> nowNode = first;
        Node<Item> 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 2

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 3

——————————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<Item> nowNode = first;
    Node<Item> 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<Item> 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.