Thread: Recursion Help

Hello,

I'm just learning about recursion and I need some help. I am given a class RLList (a Linked List) and told to re-implement these methods:

public void add(E newEntry);
public boolean add(int newPosition, E newEntry);
public E remove(E item);
public E remove(int position);
public boolean replace(int givenPosition, E newEntry);
public E getEntry(int givenPosition);
public boolean contains(E anEntry);
public void reverse();
public String toString();

If someone could show me how to do a couple of these and give a little explanation on how you implemented the recursion, that would really help.

Below is the RLList code:

public class RLList<E> implements ListInterface<E>{ private Node<E> firstNode; // reference to first node private int length; // number of entries in list   public RLList(){ clear(); } // end default constructor       public final void clear(){ //any function called in a constructor must be declared final firstNode = null; length = 0; } // end clear       private class Node<E>{ // private inner class private E data; // data portion private Node<E> next; // link to next node   private Node(E dataPortion){ data = dataPortion; next = null; } // end constructor       private Node(E dataPortion, Node<E> nextNode){ data = dataPortion; next = nextNode; } // end constructor } // end Node       public void add(E newEntry){ Node<E> newNode = new Node<E>(newEntry);   if (isEmpty()) firstNode = newNode; else{ // add to end of nonempty list Node lastNode = getNodeAt(length); lastNode.next = newNode; // make last node reference new node } // end if length++; } // end add           public boolean add(int newPosition, E newEntry){ boolean isSuccessful = true;   if ((newPosition >= 1) && (newPosition <= length+1)){ Node<E> newNode = new Node<E>(newEntry);   if (isEmpty() || (newPosition == 1)){ // case 1 newNode.next = firstNode; firstNode = newNode; } else{ // case 2: newPosition > 1, list is not empty Node<E> nodeBefore = getNodeAt(newPosition-1); Node<E> nodeAfter = nodeBefore.next; newNode.next = nodeAfter; nodeBefore.next = newNode; } // end if   length++; } else isSuccessful = false;   return isSuccessful; } // end add       public E remove(int givenPosition){ E result = null; // return value   if (!isEmpty() && (givenPosition >= 1) && (givenPosition <= length)){ if (givenPosition == 1){ // case 1: remove first entry result = firstNode.data; // save entry to be removed firstNode = firstNode.next; } else{ // case 2: givenPosition > 1 Node<E> nodeBefore = getNodeAt(givenPosition-1); Node<E> nodeToRemove = nodeBefore.next; Node<E> nodeAfter = nodeToRemove.next; nodeBefore.next = nodeAfter; // disconnect the node to be removed result = nodeToRemove.data; // save entry to be removed } // end if   length--; } // end if   return result; // return removed entry, or null // if operation fails } // end remove   public E remove(E item){ return item; }     public boolean replace(int givenPosition, E newEntry){ boolean isSuccessful = true;   if (!isEmpty() && (givenPosition >= 1) && (givenPosition <= length)){ Node<E> desiredNode = getNodeAt(givenPosition); desiredNode.data = newEntry; } else isSuccessful = false;   return isSuccessful; } // end replace     public E getEntry(int givenPosition){ E result = null; // result to return   if (!isEmpty() && (givenPosition >= 1) && (givenPosition <= length)) result = getNodeAt(givenPosition).data;   return result; } // end getEntry         public boolean contains(E anEntry){ boolean found = false; Node<E> currentNode = firstNode; while (!found && (currentNode != null)){ if (anEntry.equals(currentNode.data)) found = true; else currentNode = currentNode.next; } // end while   return found; } // end contains   public void reverse(){ }     /** Task: Determines whether the list is empty. * @return true if the list is empty, or false if not */ public boolean isEmpty(){ return (firstNode == null); }     /** Task: Displays all entries that are in the list, one per * line, in the order in which they occur in the list. */ public void display(){ Node<E> currentNode = firstNode; System.out.print("["); while(currentNode != null){ System.out.print(currentNode.data + " "); currentNode = currentNode.next; }   System.out.println("]"); }     /** Task: Determines whether the list is full. * @return true if the list is full, or false if not */ public boolean isFull(){ return false; }     /** Task: Gets the length of the list. * @return the integer number of entries currently in the list */ public int getLength(){ return length; }         /* < Implementations of the public methods add, remove, replace, getEntry, contains, getLength, isEmpty, isFull, and display go here. > */   // ---------------private!-----------------------------   /** Task: Returns a reference to the node at a given position. * Precondition: List is not empty; 1 <= givenPosition <= length. */ private Node<E> getNodeAt(int givenPosition){ Node<E> currentNode = firstNode;   for (int counter = 1; counter < givenPosition; counter++) currentNode = currentNode.next;   return currentNode; } // end getNodeAt         } // end LList

I recommend taking it one step at a time, and tackle each of those methods.

If someone could show me how to do a couple of these

We are here to help you through this, but not to do it for you. Like I said, break the problem down and give them a try. If you struggle, post back with a precise question about the problem you are having.