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

Semasa saya berada di luar dahulu, soalan ini sendiri tidak menarik di tingkat satu, dan terdapat 2 orang yang menyukainya.
Saya takut ayat tunggal 授人鱼不如授人以渔。 membangkitkan persetujuan, yang sangat mudah untuk bergema dengan isu seperti lz.
找到空指针的引用后，就向前找这个引用的初始化的逻辑部分。Ayat ini agak mengelirukan.
Kod terakhir yang saya siarkan terlalu mengelirukan saya tidak faham maksud soalan itu first.next.equals(null)Saya tidak mahu mengeluh tentang kod tersebut.
Bolehkah anda melakukan sesuatu yang praktikal? Malah seperti @hsfzxjy di tingkat 2

Mari kita bincangkan tentang ralat itu dahulu.

nowNode.next.equals(null)

xxx.equals(null) dan xxx == null
Perbezaannya ialah jika program boleh berjalan seperti biasa,
xxx.equals(null) mesti hanya mengembalikan false
xxx == null boleh kembali benar, boleh juga membalas palsu

Kerana jika xxx adalah null
xxx.equals(null) akan membuang NullPointerException
xxx == null returns true

Kemudian ada masalah logik

Pada kekunci terakhir, yang seterusnya adalah batal
Jadi dalam

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

frontNode.next akan menunjuk ke null, dan nowNode akan menunjuk ke null.

Peningkatan pada kod anda:

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

Saya melaksanakannya berdasarkan idea anda, meninggalkan soalan untuk anda.
Selain itu, saya tidak mengira kaedah penyelesaian sangat. Mohon maaf jika jawapannya tidak memuaskan hati anda.

Answer 2

Apabila first menjadi sasaran, baris 161 frontNode.next akan melaporkan ralat

Apabila senarai terpaut kosong, ralat akan dilaporkan pada baris 157 dan 167 nowNode.next

Anda tidak boleh melakukannya dalam tahun yang sejuk, mengapa anda tidak mengikutinya langkah demi langkah

Answer 3

——————————Kandungan tambahan————————————————
Nota tambahan: Simbol == membandingkan kedua-dua belah tanda sama The nilai pembolehubah ialah , jadi apabila digunakan untuk membandingkan dua rujukan objek, alamat memori kedua-dua rujukan itu dibandingkan. Kaedah equals sememangnya boleh digunakan untuk membandingkan kandungan rujukan tertentu.
Contohnya

String str1 = new String("123");

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

Jadi == hanya digunakan apabila menilai sama ada ia adalah nol. Jika tidak, sebaiknya gunakan kaedah sama jika anda boleh, kerana kebanyakan pembolehubah dalam Java adalah jenis rujukan.
———————————————————————————————————————

Tajuk telah dikemas kini Ini adalah pengubahsuaian bahagian keluarkan
Jangan gunakan bentuk xxx.equls(null) apabila ia dinilai sebagai xxx juga mungkin kosong. Pada masa hadapan, anda boleh terus menggunakan simbol == untuk menentukan atau menyesuaikan kaedah alat boolean 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;
        }
    }
}

——————————————————————————————Kemas Kini Lama———————————————— ——————————————————————
Masih melihat sekilas.

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

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

Selepas melaporkan ralat, java.lang.NullPointerException terus melihat ke bawah dan mencari baris pertama yang mengandungi nama pakej kelas anda Nombor selepas baris itu ialah bilangan baris tempat anda membuat ralat.
Selepas mencari rujukan penuding nol, nantikan bahagian logik permulaan rujukan ini.