Insert node at the end of linked list

Question

There is a simple iterative solution for these kind of problems.

Node Insert(Node head,int data) {
    Node newNode = new Node();
    newNode.data = data;
    if (head == null) {
        return newNode;
    }
    Node current = head; 
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
    return head;
}

It works perfectly fine. But I want to learn recursion and see the things with that perspective. Hence I came up with the below solution, it seems elegant but I have to admit that it was just intuition and the given code worked. I want to develop a mental model for working with recursion or at least some way to verify that my code will work fine. How to verify theoretically that the below solution should work.

Recursive version

Node Insert(Node head,int data) {
    // Base case.
    if (head == null) {
        Node newNode = new Node();
        newNode.data = data;
        return newNode;
    }
    // Smaller problem instance.
    head.next = Insert(head.next, data);
    return head;
}

Answer 1

A recursive solution generally must obey these rules:

1. It has to distinguish between a general case and a base case. Then, it has to contain some type of code bifurcation (typically one if) to two blocks of code: the base block and the general block.
2. The base block has to return an immediate response (not recursive).
3. The general block has to re-invoke the same function (recursively), but not with the same arguments values (which will produce infinite recursion), but with values that are getting forward to the base case.

Of corse, this is a simple recursion model, which in practice could be more complex (more than one base case, recursion between two functions, etc).

If we analyze theoretically your proposal according to these rules, we can see it meets all of them.

Answer 2

I would take the code just a little further and remove the multiple exit points. This allows you to reason about both the effect on the list and which node mut be returned.

Node appendRecursive(Node head, int data) {
    // By default return the same list we were given.
    Node list = head;
    if (list == null) {
        // At end of list or list is empty.
        list = new Node();
        list.data = data;
    } else {
        // Recurse.
        head.next = appendRecursive(head.next, data);
    }
    return list;
}

As far as reasoning goes you generally need to use induction.

• If the list is empty (list == null) then create a new node and that becomes your list.
• If the list is not empty, your new list must be the list with the new data appended to it.

Given the above it is possible to reason that in all cases this will function correctly because either the list is empty or it is not.

Using recursion on lists is generally considered inefficient and clunky because iterative algorithms fit better with linear structures. A better exercise would be to write your own Tree structure because trees lend themselves very well to recursive algorithms. You will discover that it is often much easier and more elegant to perform the required function recursively on a tree.

static class Tree {

    Node head = null;

    class Node {

        Node left;
        Node right;
        int data;

        private Node(int data) {
            this.data = data;
        }
    }

    void insert(int data) {
        head = insert(head, data);
    }

    private Node insert(Node node, int data) {
        if (node == null) {
            // Empty tree becomes just the node.
            return new Node(data);
        } else {
            // Pick the correct branch to add this data to.
            if (data < node.data) {
                node.left = insert(node.left, data);
            } else {
                node.right = insert(node.right, data);
            }
        }
        return node;
    }

    private CharSequence toString(Node n) {
        StringBuilder s = new StringBuilder();
        if (n != null) {
            // First print the tree on the left.
            if (n.left != null) {
                s.append(toString(n.left)).append(",");
            }
            // Then the data in this node.
            s.append(n.data);
            // Then the tree on the right.
            if (n.right != null) {
                s.append(",").append(toString(n.right));
            }
        }
        return s;
    }

    @Override
    public String toString() {
        // Even toString is recursive.
        StringBuilder s = new StringBuilder("{");
        s.append(toString(head));
        return s.append("}").toString();
    }
}

public void test() {
    Tree tree = new Tree();
    for (int i : new int[]{6, 5, 4, 3, 2, 1}) {
        tree.insert(i);
    }
    System.out.println(tree);
}

Notice how simple it is to judge where to add "," in the toString method - a notoriously clunky issue when printing lists.