Recursive methods of singly linked list

Question

Can anyone review the methods? If there are better ways to write a certain method I would appreciate it if anyone could tell me.

public class Node<E> {
 E data;
 Node<E> next;
 public Node(E item) {
 setData(item);
 setNext(null);
 }
 public Node(E item, Node<E> Ref) {
 setData(item);
 setNext(Ref);
 }
 public E getData() {
 return data;
 }
 public void setData(E item) {
 data = item;
 }
 public Node<E> getNext() {
 return next;
 }
 public void setNext(Node<E> Ref) {
 next = Ref;
 }
}
class MySinglyLinkedList<E> {
 // attributes
 private int size;
 private Node<E> head;
 // methods
 public MySinglyLinkedList() {
 size = 0;
 head = null;
 }
 // Method size
 private int sizeHelper(Node<E> head) { // Helper Method
 if (head == null)
 return 0;
 else
 return 1 + sizeHelper(head.next);
 }
 public int size() { // Wrapper Method
 return sizeHelper(head);
 }
 // Method add
 private boolean addHelper(Node<E> head, E data) { // Helper Method
 if (head.next == null) {
 head.next = new Node<E>(data);
 return true;
 } else
 return addHelper(head.next, data);
 }
 public boolean add(E data) { // Wrapper Method
 if (head == null) {
 head = new Node<E>(data);
 return true;
 } else
 return addHelper(head, data);
 }
 // Method toString
 private String toStringHelper(Node<E> head) { // Helper Method
 if (head == null)
 return "";
 else
 return head.data + "\n" + toStringHelper(head.next);
 }
 public String toString() { // Wrapper Method
 return toStringHelper(head);
 }
 // Method get
 private Node<E> getNodeHelper(int i, Node<E> head) { // Helper Method
 if (i == 0)
 return head;
 else
 return getNodeHelper(i - 1, head.next);
 }
 public Node<E> getNode(int i) { // Wrapper Method
 if (head == null)
 return null;
 else
 return getNodeHelper(i, head);
 }
 // Method indexOf
 private boolean indexOfHelper(E data, Node<E> tmp) { // Helper Method
 if (tmp == null)
 return false;
 else if (tmp.data.equals(data))
 return true;
 tmp = tmp.next;
 return indexOfHelper(data, tmp);
 }
 public boolean indexOf(E data) { // Wrapper Method
 return indexOfHelper(data, head);
 }
 // Method remove
 private boolean removeHelper(Node<E> head, Node<E> pred, E outData) { // Helper Method
 if (head == null)
 return false;
 else if (head.data.equals(outData)) {
 pred.next = head.next;
 return true;
 } else
 return removeHelper(head.next, head, outData);
 }
 public boolean remove(E outData) { // Wrapper Method
 if (head == null)
 return false;
 else if (head.data.equals(outData)) {
 head = head.next;
 return true;
 } else
 return removeHelper(head.next, head, outData);
 }
 // Method insert
 public Node<E> insert(Node<E> head, int i) { // Wrapper Method
 if (head == null)
 head = new Node(i, null);
 else
 head.next = insert(head.next, i);
 return head;
 }
 // Method insertBefore
 private boolean insertBeforeHelper(E e1, E e2, Node<E> head) { // Helper Method
 if (head.next == null)
 return false;
 else if (head.next.data.equals(e1)) {
 Node<E> tmp = new Node<E>(e2);
 tmp.next = head.next;
 head.next = tmp;
 return true;
 } else
 return insertBeforeHelper(e1, e2, head.next);
 }
 public boolean insertBefore(E e1, E e2) { // Wrapper Method
 if (head == null)
 return false;
 else
 return insertBeforeHelper(e1, e2, head);
 }
 // Method reverse
 private Node<E> reverseHelper(Node<E> head, Node<E> prev) { // Helper Method
 if (head == null)
 return head;
 else if (head.next == null) {
 head.next = prev;
 return head;
 } else {
 Node<E> next = head.next;
 head.next = prev;
 return reverseHelper(next, head);
 }
 }
 public Node<E> reverse(Node<E> head) { // Wrapper Method
 return reverseHelper(head, null);
 }
 // Method replace
 private void replaceHelper(Node<E> head, E oldObj, E newObj) { // Helper Method
 if (head != null) {
 if (oldObj.equals(head.data))
 head.data = newObj;
 replaceHelper(head.next, oldObj, newObj);
 }
 }
 public void replace(E oldObj, E newObj) { // Wrapper Method
 replaceHelper(head, oldObj, newObj);
 }
}

Answer 1

The code that you have is clear, properly indented and easily readable. Internal methods are private while the public API is public, which is a very good thing.

I have a handful of comments:

• You have a member private int size; but it is unused at the moment. You might want to consider removing it - unused code should be deleted. However, a better alternative would be to use it as a cache for the size() method. In the add() method, you can increment it by one when an object is added, similarly, in the remove() method, you can decrement it by one when an object is removed.

• You should try to always write the curly braces surrounding your if / else statements, even if it might be unnecessary. It makes the code less error-prone for the future. For example, in the following code

  if (head == null)
   return 0;
  else
   return 1 + sizeHelper(head.next);
  

  you should have

  if (head == null) {
   return 0;
  } else {
   return 1 + sizeHelper(head.next);
  }
  

  or even

  if (head == null) {
   return 0;
  }
  return 1 + sizeHelper(head.next);
  

  which makes the code slightly shorter (although this might be a matter of opinion).

• Your indexOf method returns a boolean.

  public boolean indexOf(E data)
  

  this might be confusing for the callers, which would be less surprised to have that method return an int, like the standard List.indexOf(...). Consider updating that method to make it return the int representing the index of the given element, or -1 if the element isn't found.

• Your insert(element, i) element is also surprising: one would expect this method to insert the given element at the index given, like the standard List.add(index, element), but your method appends a node having the value i instead. Note that you're using a raw type in this method with new Node(i, null);, which you should never do.

Answer 2

It is a BAD idea to handle adding with scanning the whole list – a better choice is keeping a pointer to the last item instead, to access it immediately.

And even WORSE idea is doing things like scanning a list with recursion. It is quite common for the list to contain several hundred or thousands of items, but it is quite UNcommon to go several thousands levels into recursion.

Anyway, if you want to... This routine saves the if() branch in the add method at the cost of re-assigning all next references along the list during the return from recursive scan.

private Node<E> addHelper(Node<E> head, E data) { // Helper Method
 if (head == null) {
 return new Node<E>(data);
 } else {
 head.next = addHelper(head.next, data);
 return head;
 }
}
public boolean add(E data) { // Wrapper Method
 head = addHelper(head, data);
}

• Richard Chambers: Functional languages tend to rely on recursion so have tail call optimization a feature implemented for specific cases in the Java Virtual Machine. Not sure if this particular source code is tail recursive or not and if the JVM support would apply or not. See What limitations does the JVM impose on tail-call optimization.

Answer 3

• Traditional coding conventions call for parameter names to start with lower case. Some methods have a parameter named Ref
• Is there any point to the boolean return value of add and addHelper? It seems like it will always return true.
• You seem to avoid Node being part of your public interface. Accordingly, Node should not be a public class. Also, you use Node in your public insert() method.
• getNodeHelper should handle the case where i is greater than the number of nodes.
• indexOf should probably be named firstIndexOf since there could be multiple matches, but it only finds the first.
• same with remove
• not sure what it means to reverse a single Node

• Tunaki: My guess for the add method is consistency over the standard Collection.add which returns true when the collection was changed. So I find returning true the least surprising result.