从链表中删除对象的方法

huangapple go评论69阅读模式
英文:

Method to delete object from Linked list

问题

我没有看到我的错误,请纠正我,谢谢!
我需要从链表中删除一个对象。但是我在 if (current.item.equals(e)) 部分遇到了 NPE 错误。

   public void remove(T e) {
        if (first == null) {
            throw new IndexOutOfBoundsException("List is empty");
        }
        if (first.item.equals(e)) {
            first = first.next;
            first.next.prev = null;

        }
        if (last.item.equals(e)) {
            last = last.prev;
            last.prev.next = null;
        } else {
            Node<T> current = first;
            for (int a = 0; a < size; a++) {
                current = current.next;
                if (current.item.equals(e)) {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;

                }

            }
            size--;
            System.out.println("Removed");
        }
    }
Linkedlist<String> list = new Linkedlist<>();
list.put("Maria");
list.put("Ales");
list.put("zina");
list.put("bina");
list.put("fina");

list.remove("zina");
英文:

I do not see my mistake, correct me, please!
I need to delete an object from Linkedlist. But I got an error NPE in if (current.item.equals(e))

   public void remove(T e) {
        if (first == null) {
            throw new IndexOutOfBoundsException(&quot;List is empty&quot;);
        }
        if (first.item.equals(e)) {
            first = first.next;
            first.next.prev = null;

        }
        if (last.item.equals(e)) {
            last = last.prev;
            last.prev.next = null;
        } else {
            Node&lt;T&gt; current = first;
            for (int a = 0; a &lt; size; a++) {
                current = current.next;
                if (current.item.equals(e)) {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;

                }

            }
            size--;
            System.out.println(&quot;Removed&quot;);
        }
    }
Linkedlist&lt;String&gt; list = new Linkedlist&lt;&gt;();
        list.put(&quot;Maria&quot;);
        list.put(&quot;Ales&quot;);
        list.put(&quot;zina&quot;);
        list.put(&quot;bina&quot;);
        list.put(&quot;fina&quot;);
        

        list.remove(&quot;zina&quot;);

答案1

得分: 1

一些问题:

  • 你的代码过于乐观。有几种边界情况需要检查 null 值。

  • 处理第一个或最后一个节点匹配的代码块,重新连接了错误的节点。

  • 当删除第一个或最后一个节点时,size 值没有调整。

  • 当没有找到匹配时,size 仍然被减小。

带有注释的更正版本:

public void remove(T e) {
    if (first == null) {
        throw new IndexOutOfBoundsException("List is empty");
    }
    if (first.item.equals(e)) {
        first = first.next;
        // 现在 first 可能是 null 了!
        if (first != null) {
            // 由于已经移动了 `first` 引用,所以不应该再移动到下一个:
            first.prev = null;
        }
    } else if (last.item.equals(e)) { // 将此处改为 else if
        last = last.prev;
        // 由于已经移动了 `last` 引用,所以不应该再移动到前一个:
        last.next = null;
    } else {
        Node<T> current = first.next;  // 现在可以在这里直接移动到下一个
        // 避免 current 变为 null,所以将其作为循环条件
        while (current != null) {
            if (current.item.equals(e)) {
                current.prev.next = current.next;
                current.next.prev = current.prev;
                // 不需要继续。直接在此处退出
                break;
            }
            current = current.next;
        }
        if (current == null) return; // 未找到!我们不应该减小 size
    }
    // 在此处必须减小 size,因为它也适用于头部/尾部删除!
    size--;
    System.out.println("Removed");
}

备注:

  • last = last.prev; 之后,我们可以确定 last 不是 null。如果是的话,那么last的原始值将等于 first,而我们将永远不会进入这里。

  • if (current.item.equals(e)) { 块中,我们可以确定 current.prevcurrent.next 都不为 null。如果它们是 null,那么 current 将代表第一个/最后一个节点,而我们已经得出结论它们不匹配。

  • 我假设所有节点都保证有一个 item 属性。

  • 我假设最多只能删除一个节点。

英文:

Some issues:

  • Your code is too optimistic. There are several boundary cases you should check for null values.

  • The code blocks that deal with a match of the first or last node, rewire the wrong node.

  • The size value is not adjusted when the first or last node is removed

  • When no match is found, size is still decremented.

Corrected version with comments:

public void remove(T e) {
    if (first == null) {
        throw new IndexOutOfBoundsException(&quot;List is empty&quot;);
    }
    if (first.item.equals(e)) {
        first = first.next;
        // first can be null now!
        if (first != null) {
            // As you already moved the `first` reference, you should not go to next:
            first.prev = null;
        }
    } else if (last.item.equals(e)) { // make this an else if
        last = last.prev;
        // As you already moved the `last` reference, you should not go to prev:
        last.next = null;
    } else {
        Node&lt;T&gt; current = first.next;  // can go to next here already
        // avoid current to be null, so make it the loop condition
        while (current) {
            if (current.item.equals(e)) {
                current.prev.next = current.next;
                current.next.prev = current.prev;
                // No need to continue. Just exit here
                break;
            }
            current = current.next;
        }
        if (current == null) return; // Not found! We should not decrement the size
    }
    // Size must be decremented here, since it also applies to head/tail removals!
    size--;
    System.out.println(&quot;Removed&quot;);
}

Remarks:

  • After last = last.prev; we can be sure that last is not null. If it were, then the original value of last was equal to first, and then we would never have gotten here.

  • In the if (current.item.equals(e)) { block, we can be sure that both current.prev and current.next are not null. If they would have been, then current would represent the first/last node, for which we had already concluded that they were not a match.

  • I assumed that all nodes are guaranteed to have an item property.

  • I assumed that at most one node should be removed

huangapple
  • 本文由 发表于 2020年10月13日 00:19:10
  • 转载请务必保留本文链接:https://go.coder-hub.com/64321577.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定