Single LinkedList Remove Last Node

Question

Using the program, my professor gave me, when node p reaches the last node shouldn't it exit the loop? How would I delete the last Node?

|____|--->|____|--->|HERE|--->|NULL|

When P reaches to the last node. It satisfies p.next!=null. Hence it can never remove the last Node.

Answer 1

Although the outer for loop goes till the 2nd last element say p, the if condition in it "p.next.element.equals(e)" checks for the element after p, i.e. the last element when p is 2nd last. So the element that you check for deleting is actually p.next while p always keeps a pointer to the previous element. That way p.next = p.next.next ends up deleting p.next.

Answer 2

Here is the documentation of for loop, this is what is says about the increment operation:

The increment expression is invoked after each iteration through the loop; it is perfectly acceptable for this expression to increment or decrement a value.

So, in your case, p = p.next gets executed AFTER the iteration is complete. So, while removing 9, p will actually be on 4 and hence, p.next != null will not fail.

Answer 3

When P reaches second last node:

|____|--->|P = HERE|--->|__e__|--->|NULL| //3 elements

and e is the last node(say), then p.next.element.equals(e) becomes true, and then this happens:

|____|--->|P = HERE|--->|NULL|<---|__e__|

at this point, you have 2 elements linked list and the last node deleted.

Answer 4

The method you posted above does indeed work for deleting the last element. Let's trace through the code and pretend that we're trying to remove node 9.

Method remove() is called
p = head
First iteration:
p.next.element = 7 which doesn't equal 9
p = p.next which is node 7
Second iteration:
p.next.element = 4 which doesn't equal 9
p = p.next which is node 4
Third iteration:
p.next.element = 9 which equals 9 so now the if statement body gets executed
p points at node 4 so the result of the if statement is

Before:
head -> 7 -> 4 -> 9 -> null
After:
head -> 7 -> 4 -> null

Loop breaks and the method is over

Note that node 9 was deleted by Java's garbage collection because now that there's nothing pointing to it, there's no way to access it.

However my only issue with your method is remember to make sure to check if the head is null; otherwise the method will get a NullPointerException.

Answer 5

I think I see why this may be confusing.

The variable p will be pointing to a particular Node while iterating over the List. It starts on the head Node. Per the diagram, the head Node contains no data - it merely points to the first Node containing data. The if-condition is actually evaluating the value in the next Node. So the loop variable p will be pointing to the next-to-last Node when you remove the last Node from the List.

Using the example posted (List containing values 7,4,9) and trying to remove the value 9 which is the last element of the List. When p is pointing at the Node containing 4, the if-condition will find the 9 in p.next.element. So it will change p.nextnext variable to point to p.next.next (which is null because p.next is the last Node.