Removing nodes from queue

Question

I had an exercise to create two methods for simple queue class, first to delete last element and second to delete element at k position. Particularly I'm not asking for better implementation. Is it good enough and elegant ? What I should change ? I'll post only mentioned methods, rest should be simple enough.

/**
 * Deletes node at position k.
 */
public void delete(int k) {
 if (k > N || isEmpty()) throw new NoSuchElementException("Cannot delete element at position: " + k);
 Node previous = first;
 int deleteIndex = 1;
 if(k == deleteIndex){ //special case for first element
 if(first.next == null)
 last = null;
 first = first.next;
 N--;
 return;
 }
 for (Node node = first; node != null; node = node.next, deleteIndex++) {
 if (k == deleteIndex) {
 previous.next = node.next;
 if (previous.next == null) last = previous; //if deleted element was the last one
 N--;
 return;
 }
 previous = node;
 }
}
/**
 * Deletes last node from the queue.
 */
public void removeLastNode() {
 if(isEmpty()) throw new NoSuchElementException("Cannot delete last element from queue");
 if (N == 1) { //special case for only one element in queue
 first = null;
 last = null;
 N--;
 return;
 }
 Node previous = null;
 for (Node node = first; node != null; node = node.next) {
 if (node.next == null) {
 previous.next = null;
 last = previous;
 N--;
 }
 previous = node;
 }
}

Answer 1

Well, your code is correct and mostly ok. Except for two things:

• You have 1-based indexing? Follow the principle of least suprise, and use zero-based indexing like all other data structures as well.

• Your variable names could be more obvious.

  • N seems to be the length or size of your list – use this longer name instead. Also, the name N does not adhere to the best practice that variables and members should start with lowercase characters.

  • k is an index – the traditional abbreviation for that is i.

  • deleteIndex is not the index which you want to delete. Rather, it is some iteration variable. I'd call it position.

Then there are some minor style issues.

• It is advisable to always use if with braces, as it tends to improve readability. If you do not use braces, I would recommend to put the body of the if on the same line. You do this with your isEmpty guards, but not at if (first.next == null).

• You have very long lines. I recommend using 80–100 characters. Your longest line seems to be 104 characters long with this intendation, which is too long. (Incidentally, your lines get shorter if you use the if with curlies...).

• Instead of an NoSuchElementException you should consider an IndexOutOfBoundsException.

Some parts of your code could be made more obvious, or structured differently:

• In delete, you have the test if (first.next == null), where you actually want to test if (size == 1).

• Finding a node at a certain position is so useful that it should have a method of its own. You want a Node previous = nodeAt(i - 1); ... instead of the for loops.

• If you don't do that, your for loops still have the problem that they do three things between iterations: previous = node; node = node.next; position++. You have put one of these at the end of the loop body, the rest in the increment statement of the for loop. It would have been better to group these together.