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

Quand j'étais dehors avant, cette question en elle-même n'était pas intéressante. Le premier étage était très intéressant, et il y avait 2 personnes qui l'aimaient.
Je crains que la seule phrase 授人鱼不如授人以渔。 ait suscité l'accord, ce qui est particulièrement facile à résonner avec des problèmes comme lz.
找到空指针的引用后，就向前找这个引用的初始化的逻辑部分。Cette phrase est un peu trompeuse.
Le dernier code que j'ai posté était trop déroutant. Je n'ai même pas compris le sens de la question first.next.equals(null)Je ne veux pas me plaindre d'un tel code.
Pouvez-vous faire quelque chose de pratique ? Même comme @hsfzxjy au 2ème étage

Parlons d'abord de l'erreur. Personne n'a trouvé cette erreur ?

nowNode.next.equals(null)

xxx.equals(null) et xxx == null
La différence est que si le programme peut s'exécuter normalement,
xxx.equals(null) ne doit renvoyer que false
xxx == null peut renvoyer vrai, peut aussi renvoyer faux

Parce que si xxx est nul
xxx.equals(null) lancera NullPointerException
xxx == null renvoie true

Ensuite, il y a le problème de logique

A la dernière clé, la suivante suivante est nulle
Donc dans

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

frontNode.next pointera vers null, et nowNode pointera vers null.

Améliorations de votre 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;
            }
        }
    }

Je l'ai mis en œuvre en fonction de vos idées, en vous laissant une question.
De plus, je ne compte pas beaucoup le mode de règlement. Veuillez me pardonner si la réponse ne vous satisfait pas.

Answer 2

Lorsque first est la cible, la ligne 161 frontNode.next signalera une erreur

Lorsque la liste chaînée est vide, une erreur sera signalée aux lignes 157 et 167 nowNode.next

Vous ne pouvez pas le faire dans une année cool, pourquoi ne le suivez-vous pas étape par étape

Answer 3

——————————Contenu supplémentaire————————————————
Remarque supplémentaire : Le symbole == compare les deux côtés du signe égal Le la valeur d'une variable est , donc lorsqu'elle est utilisée pour comparer deux références d'objet, les adresses mémoire des deux références sont comparées. La méthode égale peut en effet être utilisée pour comparer le contenu spécifique des références.
Par exemple

String str1 = new String("123");

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

Donc == n'est utilisé que pour juger s'il est nul. Sinon, il est préférable d'utiliser la méthode égale si vous le pouvez, car la plupart des variables en Java sont des types référence.
——————————————————————————————————————————

Le titre a été mis à jour. Il s'agit d'une modification de la partie supprimée
Ne pas utiliser le formulaire xxx.equls(null) lorsqu'il est jugé vide. À l'avenir, vous pourrez directement utiliser le symbole == pour déterminer ou personnaliser une méthode outil booléenne isEmpty (Object o)

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;
        }
    }
}

——————————————————————————————Ancienne mise à jour———————————— ——— ———————————————————————
J'ai quand même jeté un coup d'oeil rapide.

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~");
    }

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

Après avoir signalé une erreur, java.lang.NullPointerException continue de chercher et trouve la première ligne contenant le nom du package de votre classe. Le nombre après cette ligne est le nombre de lignes où vous avez commis l'erreur.
Après avoir trouvé la référence du pointeur nul, attendez avec impatience la partie logique d'initialisation de cette référence.