Setting LinkedList nodes to null

Question

I came across this problem earlier, in a coding book.

"Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node."

The solution given in the book is this:

public static boolean deleteNode(LinkedListNode n) {
    if (n == null || n.next == null) {
        return false; // Failure
    }
    LinkedListNode next = n.next;
    n.data = next.data;
    n.data = next.data;
    n.next = next.next;
    return true;
}

Which is a good solution, of course, being O(1). The book notes this at the end, though.

"Note that this problem cannot be solved if the node to be deleted is the last node in the linked list".

Am I missing something obvious here? Why couldn't I just, say, put a check in the method before the body to check if n.next was equal to null, and if so, just set n to be null and return true? Is there any reason I can't just do that?

Answer 1

What this code is really doing is copying the next node into the given node. The net effect is as if the current node is deleted, but really it's just being overridden with the next node.

That is, say you're deleting B in this list:

A -> B -> C -> D

The resulting list looks like this:

                 +------+
A -> B(Ccopy) ---+   C -+-> D

Now you can't do this to node D because there is no next node to copy.

Why couldn't I just, say, put a check in the method before the body to check if n.next was equal to null, and if so, just set n to be null and return true? Is there any reason I can't just do that?

Setting n to null won't do anything. n is just a reference to the list node being deleted. If you change n, you don't actually change anything on the list. For example, say you wanted to delete D in that same list. It looks like this:

               n
               |
               v
A -> B -> C -> D

If you set n to null, the end result is this:

               n---> null


A -> B -> C -> D

Note that nothing on the list changed at all.

The only way to delete D in this case would be to modify C.next to point to null. That is, you want this:

              +----> null
A -> B -> C --+ D

This requires modifying C, though, and in a singly linked list, you have no easy way to access C from D. You'd have to search from the start of the list until you find the node x such that x.next == D.

Answer 2

So suppose you've the last node n, with n-1 (the previous node) and p (reference to last node) pointing to it:

[n - 1] --> [n] <-- p

The reference you've is p. And you've to delete the node n, pointed by p. If you set p to null, you don't de-reference [n - 1] pointer. That still points to [n] node. So, that means, the node [n] is not really detached from the linked list.