时间戳

首页 > 解决方案 > 从链表中删除对象的方法

java - 从链表中删除对象的方法

问题描述

我没有看到我的错误，请纠正我！我需要从 Linkedlist 中删除一个对象。但我收到一个错误 NPEif (current.item.equals(e))

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

标签： javalinked-list

解决方案

一些问题：

  • 你的代码太乐观了。您应该检查几种边界情况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 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<T> 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("Removed");
}

评论：

  • 之后last = last.prev;我们可以确定last不是null。如果是，那么 的原始值last等于first，那么我们永远不会到达这里。

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

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

  • 我假设最多应该删除一个节点

推荐阅读