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);
    }
}

Tunaki · Answer 1 · 2016-04-17 20:40:17Z

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.

CiaPan · Answer 2 · 2016-04-17 20:40:55Z

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);
}

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. — Richard Chambers, Apr 17 '16 at 21:42

Hank D · Answer 3 · 2016-04-17 20:55:24Z

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

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. — Tunaki, Apr 17 '16 at 21:05

asked	9 months ago
viewed	779 times
active	9 months ago

current community

your communities

more stack exchange communities

Recursive methods of singly linked list

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged java recursion linked-list or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Recursive methods of singly linked list

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java recursion linked-list or ask your own question.

Related

Hot Network Questions