Sylten Sylten - 2 months ago 14
Java Question

Java: How to write a recursive removeLast-method for a linked list?

My removeLast method are meant to return the last element in the linked list, and then return it. This is what I have so far:

public int removeLast() {
int x = getLast();
removeLast(first);
return x;
}

private void removeLast(Node n) {
if (n == null) {
throw new ListException("Empty list");
} else {
if (n.next == null) {
n = null;
} else {
removeLast(n.next);
}
}
}


first = an instance variabel in the LinkedList-class

removeLast() successfully returns the last number (well getLast() does it really, and then removeLast(Node n) is supposed to actually remove it. However, that part doesn't work.

Answer

You are not correctly setting the last node of the linked list as null. As @Kevin Esche said,
n = null sets n as null and not the node of the linked list. In my code, I refer to the node with the link reference and set it to null.

This should work.

public int removeLast(Node n){  //returns and removes the last node

    int x = getLast();
    if(n == start && n.link == null) //list has only last node
        start = null;
    else {
        if(n.link.link == null)
            n.link = null;
        else
            x = removeLast(n.link);
    }
    return x;
}

While calling the removeLast() method from somewhere, pass start or first as the argument.

Calling the method from main method

Here's an example of calling the removeLast() method from the main method.

public static void main(String[] args){
    LinkedList ll = new LinkedList();
    /* add the nodes */
    System.out.println("The original LinkedList is");
    /* display the LinkedList */
    System.out.println("The last node is "+ll.removeLast(start));
    System.out.println("After removing the last node, LinkedList is");
    /* display the current LinkedList */
}
Comments