How do I delete the middle node from a LinkedList?

user_11840690 0
Viewed 266

I'm trying to delete the middle node from a linked list given access to that node. I'm wondering if there is a difference between the two methods below, or do they accomplish the same thing?

public boolean deleteMiddle(Node middle){
    Node next = middle.next; //line 2
    middle.data = next.data;
    middle.next = next.next;
    return true;

}

public boolean deleteMiddle(Node middle){
    middle.data = middle.next.data;
    middle.next = middle.next.next;
    return true;

}

The first method is what the textbook recommended but it seems like creating the Node "next" in the first method(line 2) is an unnecessary line of code.

singly-linked-list java
3 Answers

I think you're probably right that they are equivalent (or certainly look that way)

In both cases it looks like there is a null pointer exception (on next.next) if the item you're deleting is the last in the list (e.g. if next is null then next.next is an error).

And if you get passed null of course that's also going to be a NPE.

user_4565610

Yes, they're equivalent. I prefer the first one because it avoids the repetition of the expression middle.next.

As @Rick pointed out, when middle is the last element, you'll get an NPE in both cases.

user_70364190

creating the Node "next" in the first method(line 2) is an unnecessary line of code.

Both snippets achieve the same result.

But what the extra variable assignment (it does not "create a Node", it just assigns a new name to an existing one) does is avoiding to call middle.next twice, avoiding doing the same "calculation" twice.

In this example that won't make any real difference, but in general, it can be a usual performance optimization to avoid redundant work (especially if method calls are involved that do some "heavy lifting"). Before engaging in these adventures, though, one should think about if it is worth making the code potentially less legible, especially given that the JVM will try to do all kinds of optimization automatically. So apply this mindset only to simple patterns or real bottlenecks.

On top of that, giving names to intermediate results can also lead to more self-explanatory code (also not much difference here).

Final remarks: Sometimes (but not here) it is necessary to introduce extra variables to store things temporarily that would otherwise be overwritten in the course of the operation, such as the famous int h = x; x = y; y = h; example.

user_149550
Related