A Java recursive delete method in a linked list
Ok, let's go through this with an example. It's simplistic, but once you get the hang of it and understand the delete recursion algorithm, you can easily make the sample classes generic, take care of encapsulation, optimize the code and then go on to production.
Classes in this example
Assume, for the sake of example, that the basic Singly LinkedList and Node classes are very simplistic. The inner static Node class only stores primitive int types and it only includes a next reference to the following Node element in the list. The LinkedList only includes a head node, which is the beginning of the linked list. This is not a doubly linked list and it does not have a reference to the previous node. Traversals are done sequentially from the given Node (typically head node) through the next reference, one node after the other. I've added a toString() implementation to both, which will come handy later:
public class LinkedList {
protected Node head;
public LinkedList(Node head) {
super();
this.head = head;
}
static class Node {
protected int data;
protected Node next;
Node(int data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Node ");
builder.append(data);
if (null != next)
builder.append(" -> ");
return builder.toString();
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("LinkedList [");
Node node = head;
while (node != null) {
builder.append(node);
node = node.next;
}
builder.append("]");
return builder.toString();
}
}
Implementing a recursive delete method
Now, let's add a recursive delete() method. Deleting a node in a singly linked list can only be done by un-linking it from the previous node's next reference. The only exception to this rule is the head node, which we null to delete. Hence, it is obvious that we'll need (in addition to a starting point current node reference), a reference to the previous node.
Thus, our recursive delete() method signature can be:
private LinkedList delete(Node node, Node prev, int key)
Although the return type of this method can be omitted altogether (void) it is very useful to support chain-ability, so that API calls can become one-liner, dot separated syntax such as:
System.out.println(list.push(0).append(2).deleteAll(1));
Hence, for the sake of chain-ability, we'll return a reference to the entire LinkedList instance from this method too. As per the arguments list:
The first argument is the current node to check if it matches the given key. The next argument is the previous node, in case we need to un-link the current node. The last argument is the key we're looking for in all nodes to be deleted (unlinked).
The method modifier is private because it's not meant to be used publicly. We'll wrap it in a user friendly facade method, which will start the recursion with head as the current node and null as the previous node:
public LinkedList deleteAll(int key) {
return delete(head, null, key);
}
Now, let's see how we can implement the recursive delete(...) method and we begin with the two base conditions that will terminate the recursion; a null current node or a single node in the list, which is also the head node:
private LinkedList delete(Node node, Node prev, int key) {
if (node == null)
return this;
if (node == head && head.data == key && null == head.next) { // head node w/o next pointer
head = null;
return this;
}
//...more code here
}
Reaching the first base condition means either that we've reached the end of the linked list (found the key or not), or that the linked list is empty. We're done and we return a reference to the linked list.
The second base condition checks to see if our current node is the head node, and that it matches the key. In this case we also check if it happens to be the single node in the linked list. In such case the head node requires a 'special' treatment and must be assigned null in order to be deleted. Naturally, after deleting the head node, the list is empty and we're done, so we return a reference to the linked list.
The next condition checks if the current node matches the key, if it's the head node, but is not alone in the list.
private LinkedList delete(Node node, Node prev, int key) {
//...previous code here
if (node == head && head.data == key) { // head with next pointer
head = head.next;
return delete(head, null, key);
}
//...more code here
}
We'll later optimize this code but for now, in such a case we simply move the reference to head one step forward, so head is effectively deleted (the old reference will be garbage collected) and we recur with the new head as the current node and null is still the previous node.
The next case covers a regular (middle or tail) node matching the key:
private LinkedList delete(Node node, Node prev, int key) {
//...previous code here
if (node.data == key) {
prev.next = node.next;
return delete(prev, null, key);
}
//...more code here
}
In this case we delete the current node by un-linking the next pointer of the previous node from the current node and assigning it the next to the current node address. We essentially 'skip' the current node, which becomes grabage. We then recur with the previous node being the current node and null as the previous node.
In all of these handled cases we had a match for key. Finally, we handle the case where there's no match:
private LinkedList delete(Node node, Node prev, int key) {
//...previous code here
return delete(node.next, node, key);
}
Obviously, we recur with the next node as the current node, and the old current node as the previous node. The key remains the same through all recursion calls.
The entire (un-optimized) method now looks like this:
private LinkedList delete(Node node, Node prev, int key) {
if (node == null)
return this;
if (node.data == key && node == head && null == node.next) { // head node w/o next pointer
head = null;
return this;
}
if (node.data == key && node == head) { // head with next pointer
head = head.next;
return delete(head, null, key);
}
if (node.data == key) { // middle / tail
prev.next = node.next;
return delete(prev, null, key);
}
return delete(node.next, node, key);
}
Tail Recursion Optimization
Many compilers (javac included) can optimize recursive methods, if they use a tail-recursion. A recursive method is tail recursive when a recursive call is the last thing executed by the method. The compiler can then replace the recursion with a simple goto/label mechanism and save the extra memory space required in run-time for each recursion frame.
We can easily optimize our recursive delete(...) method to comply. Instead of returning recursively from each of the handled conditions (cases) we can keep a reference to the current node and previous node prev and assign them with appropriate values inside each case handling. This way, the only recursive call will happen at the end of the method:
private LinkedList delete(Node node, Node prev, int key) {
if (node == null)
return this;
if (node.data == key && head == node && null == node.next) { // head node w/o next pointer
head = null;
return this;
}
Node n = node.next, p = node;
if (node.data == key && head == node) { // head with next pointer
head = head.next;
n = head;
p = null;
} else if (node.data == key) { // middle / tail
prev.next = node.next;
n = prev;
p = null;
}
return delete(n, p, key);
}
To test this recursive method:
I've added a simple main test driver method to test the delete(...) method implementation, via the facade method deleteAll(...):
public static void main(String[] args) {
LinkedList list = new LinkedList(new Node(0, new Node(1, new Node(1, new Node(2, new Node(2, new Node(3, null)))))));
System.out.println(list);
System.out.println(list.deleteAll(6));
System.out.println(list.deleteAll(1));
System.out.println(list.deleteAll(3));
System.out.println(list.deleteAll(2));
System.out.println(list.deleteAll(0));
}
The output (using my supplied toString() methods) is:
LinkedList [Node 0 -> Node 1 -> Node 1 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 1 -> Node 1 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 2 -> Node 2]
LinkedList [Node 0]
LinkedList []
Although it's been 3 years since the initial post, I trust some other beginning Java programmers, if not the OP, find this explanation useful.
