Using recursion for a custom linkedlist

Question

For Homework I was told to write the insert method(in order) of a custom linked list. I wrote the base case, but I still don't understand the recursion case. I know I just asked how to write the contain method and someone helped me out, but in that case I did not have to do any modifications to the list like on this method. Please help me understand what is causing my linked list to override and if there is an easier way to simplify my code.

Here is my code:

public class OrderedList {

private Node first;

//Constructor
public OrderedList() {
    this.first = null;
}

//Return the number of items in the list
public int size() {
    int counter = 0;
    Node pointer = this.first;
    while (pointer != null) {
        counter++;
        pointer = pointer.next;
    }
    return counter;
}

//Return an array of copies of the stored elements
public Comparable[] getStore() {

    Comparable[] elements = new Comparable[size()];
    Node pointer = this.first;
    if (this.first == null) {
        return elements;
    } else {
        int i = 0;
        while (pointer != null) {
            elements[i] = pointer.data;
            pointer = pointer.next;
            i++;
        }
        return elements;
    }

}
//true iff item matches a stored element
//Recursive

public boolean contains(Comparable item) {

    return containsHelper(this.first, item);

}

private boolean containsHelper(Node node, Comparable item) {
    //base case
    if (node == null) {
        return false;
    } else {
        if (node.data.compareTo(item) == 0) {
            return true;
        }

        return containsHelper(node.next, item);
    }

}
//Add item preserving the order of the elements
//Recursive

public void insert(Comparable item) {

    insertHelper(this.first, item);

}

public void insertHelper(Node pointer, Comparable item) {
    //Base case
    Node store = new Node(item);

    if (pointer == null) {
        store.next = this.first;
        this.first = store;

        return;
    }
    if (pointer.data.compareTo(item) > 0 ) {
        store.next = pointer;


        return;
    }
    if (pointer.data.compareTo(item) < 0 && pointer.next == null) {
        store.next = pointer.next;
        pointer.next = store;

        return;

    } else {

        Node save = this.first;
        this.first = this.first.next;

        insertHelper(this.first, item);

        if (pointer.data.compareTo(item) > 0) {
            save.next = store;
            this.first = save;
        } else {
            save.next = pointer;
            this.first = save;
        }

    }

}

Answer 1

I'm only giving you part of the answer at first. Consider this a clue. Then there are more clues. See if you can figure it out before you get to the bottom where a whole answer is.

clue 1

This part of the code can't be in the recursive method because it makes reference to the head of the linked list. Your recursion is moving down the list, breaking it into the head and the rest, deciding whether to insert at the head and recursing if the insertion has to be in the rest.

if (pointer == null) {
    store.next = this.first;
    this.first = store;

    return;
}

This should be modified a bit so it can go in the insert() method, which deals with the whole list.

Why?

Because this code deals with the whole list and asks the question, "Is this list empty?"

clue 2

Now, for this part of the code:

if (pointer.data.compareTo(item) > 0 ) {
    store.next = pointer;
    return;
}

Notice how it has a reference to the whole list. That's a bad thing.

Its asking the question, "Is the new item (to be inserted) supposed to go in front of the current head item?"

If the answer is yes, it needs to insert it in front of the current head, leave the current head with the current rest of the linked list attached as before and return something that lets the calling code attach a newly arranged rest of the list.

if (pointer.data.compareTo(item) > 0 ) {
    store.next = pointer; // new item goes in front of this part of list
    return store;
}

clue 3

Now, let's skip to this part of the code:

Node save = this.first;
this.first = this.first.next;

insertHelper(this.first, item);

if (pointer.data.compareTo(item) > 0) {
    save.next = store;
    this.first = save;
} else {
    save.next = pointer;
    this.first = save;
}

This code asks no questions. It just recurses since we know that no change is needed related to the head of the current linked list. When we recurse, we pass it the rest of the linked list and tell it to fix that up. We don't care how because we trust it to fix up the rest of the list by inserting the new item in the right place.

So here is what we do:

Node rest = insertHelper(pointer.next, item);
pointer.next = rest;
return pointer;

clue 4

This part of the code is the last part to consider:

if (pointer.data.compareTo(item) < 0 && pointer.next == null) {
    store.next = pointer.next;
    pointer.next = store;

    return;

} 

Now, think about why you are comparing it again. The previous code tested whether the item needed to go in front of the rest of the linked list. The answer was no.

That means there are only two possible situations left.

Either there is nothing left in the list ... and we have to put the new item on the end.

Or there is something in the list ... and clue 3 deals with that by recursing.

So this part gets a little simpler:

if (pointer.next == null) {
    return store;
} 

All we have to do is return the new node which will be the new "rest of the list", instead of there being nothing in the rest of the list.

One more note

Remember that the method signature has to change to be like this:

/**
 * Insert the 'item' into the linked list beginning with the supplied node, 'pointer'
 * @returns the new, modified linked list, with the new item in it.
 */
public Node insertHelper(Node pointer, Comparable item) {

The whole thing

This includes the changes to the 'insert' method:

public void insert(Comparable item) {
   // if there isn't anything in the list, the new item becomes the whole list
   if (first == null) {
        Node store = new Node(item);
        store.next = null;
        this.first = store;
        return;
    }

    // Otherwise let the helper fix up the list for us to store away
    this.first = insertHelper(this.first, item);
}

public Node insertHelper(Node pointer, Comparable item) {
    Node store = new Node(item);

    if (pointer.data.compareTo(item) > 0 ) {
        store.next = pointer; // new item goes in front of this part of list
        return store;
    }

    if (pointer.next == null) {
        return store; // new item becomes this part of the list
    }

    // The head of this part of the list is ok, fix the rest of the list

    pointer.next = insertHelper(pointer.next, item);
    return pointer;
}

Further comments

There is another way to do this where you store the first node in some other class and each Node only stores a pointer to the rest of the list (as next).

Then you have a method to insert that knows when it gets called that it can't be null because you couldn't call it if it was null.

There is no test for the first one being null inside insert because of that. But it means the caller has to do something like:

Node item = new Node(data);
if (list != null) {
    list.insert(item);
} else {
    list = item;
}

and the insert method looks like this:

if (this.next == null || this.data > item.data) { // pseudo code for greater than
    item.next = this.next;
    this.next = item;
    return;
}
this.next.insert(item);

And that's it.