关于单链表实现的一个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

之前在外面，这个问题本身不算有趣，一楼很有趣，还有赞他的人们，有2个。
恐怕是单单一句授人鱼不如授人以渔。引起了赞同，在lz这样类伸手党的问题下特别容易引发共鸣。
找到空指针的引用后，就向前找这个引用的初始化的逻辑部分。这句话有点误导的作用。
最后贴上来的代码也是醉了..题意都没看清，first.next.equals(null)这样的代码也是不想吐槽了。
能不能干点实在的事情？哪怕像2楼@hsfzxjy一样

那么先来说说错误，就没人发现这个错误吗？

nowNode.next.equals(null)

xxx.equals(null)和xxx == null
区别就是，如果程序能正常运行下去的话
xxx.equals(null)一定只能返回false
xxx == null可能返回true,也可能返回false

因为如果xxx是null的话
xxx.equals(null)会抛出NullPointerException
xxx == null返回true

然后是逻辑问题

在最后一个key的时候，下一个next为null
于是在

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

frontNode.next会指向null，nowNode会被指向null。

对你的代码进行了改良：

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

根据你的思路实现的，留了一个问题给你。
另外，我数结算法这一块不是很6。如果答案不能令你满意还请多多包涵。

Answer 2

当 first 为目标时，161 行 frontNode.next 会报错

当 链表为空 时，157 行 和 167 行 nowNode.next 会报错

骚年不行啊，为什么不单步跟踪一下

Answer 3

——————————补充内容——————————————————
补充一下:== 符号是比较的是等号两边的变量的值，所以在用来比较两个对象引用时，比较的就是连个引用的内存地址。equals方法确实能够用来比较引用里面具体内容。
比如

String str1 = new String("123");

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

所以==只在判断是否为null时用就好，其余时候，能用equals方法最好还是用equals，必经java绝大部分变量都是引用类型。
——————————————————————————————————————————

题主更新过了，这是remove部分的修改
判断为空时不要用xxx.equls(null)的形式,xxx也可能是空。以后直接用 == 符号判断或者自定义一个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;
        }
    }
}

————————————————————————————————旧的更新——————————————————————————————————————
还是大致看了一下。

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

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

报错后，java.lang.NullPointerException继续往下看，找到第一个包含有你的类的包名的那一行，那一行后面的数字就是你出错的行数。
找到空指针的引用后，就向前找这个引用的初始化的逻辑部分。