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

Question

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

ringa_lee · Answer

之前在外面，這個問題本身不算有趣，一樓很有趣，還有讚他的人們，有2個。
恐怕是單單一句授人魚不如授人以漁。 引起了贊同，在lz這樣類伸手黨的問題下特別容易引發共鳴。 授人鱼不如授人以渔。引起了赞同，在lz这样类伸手党的问题下特别容易引发共鸣。
找到空指针的引用后，就向前找这个引用的初始化的逻辑部分。这句话有点误导的作用。
最后贴上来的代码也是醉了..题意都没看清，first.next.equals(null)找到空指標的引用後，就往前找這個引用的初始化的邏輯部分。 這句話有點誤導的作用。
最後貼上來的程式碼也是醉了..題意都沒看清，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 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;
            }
        }
    }

根據你的思路實現的，留了一個問題給你。另外，我數結算法這一塊不是很6。如果答案不能令你滿意還請多包涵。

🎜

迷茫 · Answer

當 first 为目标时，161 行 frontNode.next 會報錯

當鍊錶為空時，157 行和 167 行 nowNode.next 會報錯

騷年不行啊，為什麼不單步跟蹤一下

怪我咯 · Answer

——————————補充內容——————————————————
補充一下:== 符號是比較的是等號兩邊的變數的值，所以在用來比較兩個物件引用時，比較的就是連個引用的記憶體位址。 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 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;
        }
    }
}

————————————————————————————————舊的更新—————————————— ————————————————————————
還是大致看了一下。

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

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

報錯後，java.lang.NullPointerException繼續往下看，找到第一個包含有你的類別的包名的那一行，那一行後面的數字就是你出錯的行數。
找到空指標的引用後，就往前找這個引用的初始化的邏輯部分。

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

全部回覆(3)我來回復

騷年不行啊，為什麼不單步跟蹤一下