CODEWITHSUNDEEP
javalinked-list
bhxbr922
bhxbr922

Reputation: 47

Method to delete object from Linked list

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

Upvotes: 0

Views: 132

Answers (1)

trincot
trincot

Reputation: 350272

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

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

Upvotes: 1

Related Questions