public class linkedlist
{
    private int data;
    private linkedlist next;

    // recursive implementation of countelements
    public int countelementsr() {
        if (next == null)  // if we are the last element of the linked list
            // then there is 1 element counting us
            return 1;
        else // otherwise, there is 1 plus the count starting at the next
        // node
            return 1 + next.countelementsr();
    }
    
    // non-recursive implementation of countelements
    public int countelements() {
        int count = 0;
        linkedlist l = this; // reference the starting node (our currnent one)
        while (l != null) {
            count++; // if we are not null, we can increment the count
            l = l.next; // go to the next node
            }
        return count;
    }
    
    // recursive implementation of insert an item into the array
    public void addtoposr(int pos, int val) {
        // so we can save the reference later...
        linkedlist temp;
        
        // if we want to insert after the current item
        if (pos == 0) {
            // SAVE what we currently think of of next
            temp = next;
            // create a new node, and put it in the place of next
            // (see why we had to save in the line above?)
            next = new linkedlist();
            // set the data in the new node
            next.data = val;
            // and reattach the reference we saved to the end of our new
            // node
            next.next = temp;
        } else {
            // otherwise, move to the next node and decrement the position
            next.addtoposr(pos-1, val);
        }
    }
    
    // non-recursive version of insert an item
    public void addtopos(int pos, int val) {
        // declare a temporary value to save a reference
        linkedlist temp;
        // start off with our current node
        linkedlist l = this;
        // as long as we haven't counted down to 0
        while (pos > 0) {
            // move to the next item
            l = l.next;
            // and count down
            pos--;
        }
        // at this point l is referencing the node we want to
        // insert after, so the code at this point is basically the same
        // as in the recursive code
        temp = next;
        next = new linkedlist();
        next.data = val;
        next.next = temp;
    }
    
    // recursive version of get an item
    public int getitemr(int pos) {
        // if we want this item, return it
        if (pos == 0) return data;
        // otherwise, ask the next node and decrease the counter
        else return next.getitemr(pos-1);
        }
        
    // non-recursive version of get an item
    public int getitem(int pos) {
        // start with the first node
        linkedlist l = this;
        // as long as we haven't counted down to 0
        while (pos > 0) {
            // move forward
            l = l.next;
            // count down
            pos--;
        }
        // at this point l is referencing the node we want the data from
        return l.data;
    }
    
    // recursive version of add to the end
    public void addtoendr(int val) {
        // if the next item is null, we're at the last node
        if (next == null) {
            // if so create a new node and attach it
            // (note: by default the next in the node we are creating
            // references null)
            next = new linkedlist();
            next.data = val;
        }
        // otherwise, try the next node
        else next.addtoendr(val);
    }
    
    // non-recursive version of add to end
    public void addtoend(int val) {
        // start with the first node
        linkedlist l = this;
        // as long as the node we are looking at is not the last node
        while (l.next != null) {
            // move to the next node
            l = l.next;
        }
        // now we are looking at the last node, so we can do the same as
        // in the recursive verison
        l.next = new linkedlist();
        l.next.data = val;
    }
        
}