Trying to add a custom Node to the end of a LinkedList recursively

Question

Hi I seem to having trouble adding custom nodes to the back of my l inked list. The custom node is called ListNode and the linked list is called AddressList.

My program does not crash or throw any exceptions but it does not add a ListNode to the end of my AddressList. My addToFront method works but not my addToBack method. I just need someone to look at my addToBack method and see where I am going wrong.

I also have to do this recursively. Each ListNode has some values (name, telephoneNum, email, address, dob) and also a Next value which is a ListNode that should point to the next ListNode in the AddressList.

This is my code:

public ListNode(String name, String telephoneNum, String email, String address, String dob) {
    this.name = name;
    this.telephoneNum = telephoneNum;
    this.email = email;
    this.address = address;
    this.dob = dob;
}

public ListNode getNext() {
   return next;
}

public void setNext(ListNode link) {
   next = link;
}

The code section above is the constructor for the ListNode and the methods to get and set the next link in the AddressList.

public void addToBack(String name, String telephoneNum, String email, String address, String dob) {
    /*Base case.*/
    /*If the next node in the AddressList is null add the ListNode to that node.*/
    if(currentNode.getNext() == null) {
        currentNode = currentNode.getNext();
        currentNode = new ListNode(name, telephoneNum, email, address, dob);
    }
    /*Recursive case.*/
    /*If the AddressList still has nodes after the currentNode, keep going.*/
    else {
        currentNode = currentNode.getNext();
        addToBack(name, telephoneNum, email, address, dob);
    }
    currentNode = head;
}

Above is my addToBack method. I just don't understand why my program isn't throwing an exception or adding the ListNode to the back of the AddressList. Any feedback will be appreciated.

Answer 1

Separate responsibilities

I think you first better separate some responsibilities: instead of each time using arguments to advance the information of that user one step further, construct a node in advance, and pass this to the recursive method. This will boost performance a bit and make the call stack smaller. So something like:

public void addToBack(String name, String telephoneNum, String email, String address, String dob) {
    addToBack(new ListNode(name,telephoneNum,email,address,dob));
}

And then you need to work out a method like:

public void addToBack(ListNode newNode) {
    //TODO: implement
    //...
}

Avoid method state (or continuation state) in objects

A second problem is that you're AddressList seems to have a field currentNode that is modified in the recursive process. This can be very problematic: it attaches a continuation-state to your AddressList. Now imagine that later you want to make your class multi-threaded, then these threads will concurrently read and manipulate this field. In short: it is bad design, use a method variable and/or parameter.

So the first thing we do is fetch the head of the AddressList and use that:

public void addToBack(ListNode newNode) {
    this.addToBack(this.head,newNode);
}

This is not sufficient: an empty linked list has no head: head is a null reference. In that case we simply set the head to the newNode and we're done. so we rewrite this to:

public void addToBack(ListNode newNode) {
    if(this.head == null) {
        this.head = newNode;
    } else {
        this.addToBack(this.head,newNode);
    }
}

Now evidently we still need to implement the core method:

public void addToBack(ListNode current, ListNode newNode) {
    //TODO: implement
    //...
}

Implement the core-method

As you identified yourself, there are basically two cases: the base case in which the .getNext() of current is null, an the one where it is not: for the base case, we simply set the .setNext of current to our newNode:

if(current.getNext() == null) {
    current.setNext(newNode);
}

In the latter case, we advance: we fetch the .getNext node, and call the method recursively:

else {
    addToBack(current.getNext(),newNode);
}

Or all together:

public void addToBack(String name, String telephoneNum, String email, String address, String dob) {
    //separate responsibilities, by constructing the node first
    addToBack(new ListNode(name,telephoneNum,email,address,dob));
}

public void addToBack(ListNode newNode) {
    //do not use a continuation state in a class, fetch the head, inspect the head and if not null pass to the recursion method
    if(this.head == null) {
        this.head = newNode;
    } else {
        this.addToBack(this.head,newNode);
    }
}

public void addToBack(ListNode current, ListNode newNode) {
    //generic method that adds the node at the end
    if(current.getNext() == null) {//base case: current is the last node
        current.setNext(newNode);
    } else {//recursive case, current is not the next node
        addToBack(current.getNext(),newNode);
    }
}

You can make the last method a bit faster by preventing to call the .getNext method twice:

public void addToBack(ListNode current, ListNode newNode) {
    //generic method that adds the node at the end
    ListNode nx = current.getNext();
    if(nx == null) {//base case: current is the last node
        current.setNext(newNode);
    } else {//recursive case, current is not the next node
        addToBack(nx,newNode);
    }
}

but that's just a detail that will have very limited impact.

Answer 2

Here is the offending piece of code...

  /*Base case.*/
   /*If the next node in the AddressList is null add the ListNode to that node.*/
   if(currentNode.getNext() == null)
   {
      currentNode = currentNode.getNext();
      currentNode = new ListNode(name, telephoneNum, email, address, dob);
   }

If you reach the null case you need to set the next node as a new node ... I propose something like this

   if(currentNode.getNext() == null)
   {
      currentNode.setNext(new ListNode(name, telephoneNum, email, address, dob));
   }