Method to delete object from Linked list

Question

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

It's possible first.item, first.next, last.item, or last.prev are null. — Dan W
– Dan W, Commented Oct 12, 2020 at 16:21
@akash why it is a mistake? I want to delete an object from the middle — bhxbr922
– bhxbr922, Commented Oct 12, 2020 at 16:33
@bhxbr922 suppose you have 2 nodes. then first = first.next; now you have one node and you already on the next node. So no more next node. So should be first.prev = null; but your code had first.next.prev = null;for last node also last.next = null; And sorry rest has no problem — akash
– akash, Commented Oct 12, 2020 at 16:36

trincot · Accepted Answer · 2020-10-12 19:39:10Z

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

Collectives™ on Stack Overflow

Method to delete object from Linked list

1 Answer 1

Remarks:

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Remarks:

Comments

Your Answer

Sign up or log in

Post as a guest

Related