AngieCris AngieCris - 1 month ago 7
Java Question

Delete an element from a linked list with constraints

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

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.

Comments