Adding Several Items To A Linked-List

Question

I am creating an implementation of a linked list and am having trouble with the add method. After testing it with several entries, my size() method always returns 1. what am i doing wrong.

public class Node {

    public int data;
    public Node next;

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


public class LinkedList {

    public Node first;
    public Node last;

    public LinkedList(){
        first = null;
        last = null;
    } 

    public void add(int data){    
        Node newNode = new Node(data);
        if(first == null){
            first = newNode;        
        } else {
            add(first, newNode);
        }                  
    }

    public void add(Node currentNode, Node newNode){

        if(currentNode.next != null){
            add(currentNode.next, newNode);
        }
        currentNode.next = newNode;
    }   
        public int size(){        
        if(first == null){
            return 0;
        }
        else{
            return size(first);
        }        
    }
    public int size(Node currentNode){
        //Count Starts At One Because First = 1.
        int count = 1;        
        if(currentNode == null){
            return count;
        }
        else {
            count++;
            return size(currentNode.next);
        }             
    }
}

Answer 1

You forgot the else in the 2-arg form of add. As it stands,

if(currentNode.next != null){
    add(currentNode.next, newNode);
}
currentNode.next = newNode;

will always add the new node to first and to all the other nodes in the list. If currentNode.next = newNode appears in an else clause, it will be added correctly only to the end.

Additionally, your size method always returns 1 because the final branch always returns 1. To fix this, change

count++;
return size(currentNode.next);

to

return 1 + size(currentNode.next);

Also, replace return count; with return 1;.

Basically, your implementation is almost correct. size(Node) should return the size of the list starting with that node. If the node does not have a next, the size is 1. Otherwise, its the current node (1) + the size of the remaining tail.

You should make the 2-arg versions of add and the 1-arg version of size private since you don't want to expose the internals of your list to the public (in fact, the Node class should be a private class as well).

Additionally, you never use the last field of your class. You can either remove it, or use it to avoid the need for recursion completely in add. In the latter case, you will have to update it correctly with every new addition.