Delete an element from a linked list with constraints

Question

This is a fairly easy question but I'm confused:

Given a Singly Linked List, write a function to delete a given node.

1) It must accept pointer to the start node as first parameter and node to be deleted as second parameter i.e., pointer to head node is not global. 2) It should not return pointer to the head node. 3) It should not accept pointer to pointer to head node.

The solution in Java is as following:

void deleteNode(Node node, Node n) {

    if (node == n) {
        if (node.next == null) {
            System.out.println("There is only one node. The list "
                             + "can't be made empty ");
            return;
        }

        node.data = node.next.data;
        n = node.next;
        node.next = node.next.next;
        System.gc();

        return;
    }

    // When not first node, follow the normal deletion process
    // find the previous node
    Node prev = node;
    while (prev.next != null && prev.next != n) {
        prev = prev.next;
    }
    if (prev.next == null) {
        System.out.println("Given node is not present in Linked List");
        return;
    }
    prev.next = prev.next.next;
    System.gc();

    return;
}

I'm confused about why in deleting the head node, we're not modifying the head pointer but copying the fields instead (changing the content), but in deleting other nodes, it's simply prev.next = prev.next.next Does it work if we just do head = head.next instead when deleting head node?

Thank you!

Answer 1

The reason the code copies the data rather than modifying the variable referencing the head is that other users of the list will have a reference to the head node. Changing the local variable will have no effect on their references so you won't have actually deleted the node. Copying the data to the head node effectively removes it.

So, for example, if you had code that did the following:

Node head = new Node("A");
Node tail = new Node("B");
head.next = tail;
deleteNode(head, head);

Then you would expect head.data to be "B" because the original node has been deleted. If you merely do node = node.next then head will still point to the original deleted node.

There are quite a few issues with the code you've posted so please add a comment if you want suggestions on improvements that should be made. It is not a typical algorithm for deleting nodes from a linked list.

One clear issue you've asked about is the use of System.gc. It is not necessary. There are rare cases when Java code needs to take explicit control of garbage collection. This isn't one of them. There's a good explanation of this in the accepted answer to this question.

You asked in the comments why deleting the head requires moving data while deleting other nodes only requires redirection around the node. The reason is because you don't have access to references to the head (as explained in the answer above). You do have access to references to other nodes (i.e. the previous node's next) so they can be changed directly rather than having to copy data.

For your reference, a much more standard implementation is to have the list itself store a reference to the head. Then the copying of node data can be completely avoided. Also note this compares to a value because the node class is private.

static class LinkedList<T> {
    private class Node {
        private final T value;
        private Node next = null;

        public Node(T value) {
            this.value = value;
        }
    }

    private Node head = null;

    public void add(T value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
    }

    public void remove(T value) {
        while (head != null && head.value.equals(value))
            head = head.next;
        Node prev = head;
        while (prev != null && prev.next != null) {
            if (prev.next.value.equals(value))
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }
    }
}

This avoids the arbitrary restrictions in the example you provided such as not being able to delete the head if it's the only node.