5
\$\begingroup\$

Method 1:

public void removeFirst() { if (first == null) throw new NoSuchElementException(); if (first == last) first = last = null; else { var second = first.next; first.next = null; first = second; } }

Method 2:

public void removeFirst() { if (first == null) throw new NoSuchElementException(); if (first == last) first = last = null; else first = first.next; }

Which method is preferable, speed and memory-wise? Stepping through the debugger, I see no differences in first, next, and last objects or their value attributes - so 'correctness' appears the same, though I ponder about garbage collection.

Base class excerpt:

public class LinkedList { private class Node { private int value; private Node next; public Node(int value) { this.value = value; } } private Node first; private Node last; } public void addLast(int value){ var new_node = new Node(value); if (first == null){ first = last = new_node; } else { last.next = new_node; last = new_node; } }
\$\endgroup\$
4
  • \$\begingroup\$ Please don't touch the code after receiving answers, it invalidates answers and tends to create a mess. \$\endgroup\$ Commented Nov 27, 2019 at 18:09
  • \$\begingroup\$ @Mast The point of my question was being missed, so I clarified it with a close equivalent. It was this or creating a "duplicate" \$\endgroup\$ Commented Nov 27, 2019 at 18:14
  • \$\begingroup\$ Yea, had we caught your edit sooner (before the answer was changed to accommodate), we'd still had to roll it back per our guidelines. If your point was being missed, that highlights why putting extra effort in the first iteration is very important on Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ Commented Nov 28, 2019 at 8:09
  • \$\begingroup\$ @Mast Fair, but my original question was already clear enough, just not as explicit as the edit - but the answer, which entirely missed the point of the question (before being revised), was being upvoted, and no alternatives were being posted. Unsure what the best course of action is then, as posting a new question risked being marked as a duplicate \$\endgroup\$ Commented Nov 28, 2019 at 8:22

1 Answer 1

Reset to default
6
\$\begingroup\$

Review points:

  • removeFirst on an empty list should be a no-op, (or throw an exception).
  • last was dangling.
  • Setting things to null of the removed first node, is not done in OOP, is left to the garbage collection. This also removes the need for an extra variable. And the resulting binary code is smaller.

So:

public void removeFirst() { if (first != null) { if (first == last) { // Either this. last = null; } first = first.next; if (first == null) { // Or this. last = null; } } }

One can only remove the first, when there is one. Then the last might be the biblical first.

This is for the single linked list, where a node has just one next pointer.

\$\endgroup\$
6
  • \$\begingroup\$ @OverLordGoldDragon setting fields/variables to null in order to help garbage collection faster saving memory, has almost no discernible gain (time gain in the future). As there is an extra assignment it might even be slower, I take it that a Node is not held outside of the list. \$\endgroup\$ Commented Nov 27, 2019 at 14:09
  • 1
    \$\begingroup\$ I like this answer, it addresses the core quesiton about having the (unnecessary) second variable, and it also resolves the issue with the possible dangling last pointer if first == last. It may need some better text to describe those aspects, but this is a review with good observations IMHO. \$\endgroup\$ Commented Nov 27, 2019 at 14:24
  • \$\begingroup\$ @rolfl , J. Eggen I tried keeping the question minimal, but apparently the intent wasn't too clear - see updated. The most relevant part of this answer is the third bullet point - but is that all there's to say on it? If so, that's fair, but that's the point that should be discussed/emphasized - the rest of the answer's not really relevant (also last = null handling is incorrect per standard implementations, as removing from an empty list should throw an exception) \$\endgroup\$ Commented Nov 27, 2019 at 15:51
  • \$\begingroup\$ My apology too. Though if the list contains one element last == first, and a removeFirst should null out last. The removed node, and neither its fields need not be nulled in garbage collected languages. It is bad style as it delivers noise to the code reader, and the code writer should better concentrate on functional code. For this reason I automatically just gave the most minimal code. \$\endgroup\$ Commented Nov 27, 2019 at 16:05
  • \$\begingroup\$ So can you (or anyone) confirm that setting to null is redundant, and happens automatically by the garbage collector? This is the main idea I'm trying to understand \$\endgroup\$ Commented Nov 28, 2019 at 8:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.