Recursion through a linked list in Java

Question

I need to code a method that prints the contents of a linked list recursively, however my method isn't working.

 public LinkedList reverse() {
    LinkedList list = new LinkedList();
    list = reverseRecursion(list, 0);
    return list;
  }
  public LinkedList reverseRecursion(LinkedList list, int pos) {
    if (pos != size()) {
      rotate();
      list.add(get());
      pos = pos + 1;
      reverseRecursion(list, pos);
    }
    return list;
  }

  public String toString() {
    String result = "Contents of list: {";
    result = toStringRecursion(result, 0);
    return result;
  }
  private String toStringRecursion(String result, int pos) {
    if (pos != size()) {
      rotate();
      String temp = result + get().getData() + ",";
      pos = pos + 1;
      toStringRecursion(temp, pos);
    }     
    return result;
  }

the reverse function is working fine, however my toString is only showing up as the initial result "Contents of list: {", despite being passed the previous result as a parameter. If I print the result each time I pass through the toStringRecursion, I can see the desired output right before it reverts back to the inital result when the return line is reached.

xlm · Accepted Answer · 2014-02-18 01:51:50Z

2

Among other problems with your current approach, you aren't returning the result of the recursive calls to your list:

  private String toStringRecursion(String result, int pos) {
    if (pos != size()) {
      rotate();
      String temp = result + get().getData() + ",";
      pos = pos + 1;

      // Recurse upon the appended String
      return toStringRecursion(temp, pos);
    }     
    // Stop recursing
    return "}";
  }

There's actually much simpler way of approaching this but without seeing your full class definition I can't provide further meaningful feedback without giving a lengthy explanation on linked lists as recursive data structures.

edited Feb 18, 2014 at 1:51

answered Feb 18, 2014 at 1:25

xlm

7,72415 gold badges59 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user3321373 · Accepted Answer · 2014-02-18 02:13:44Z

0

You need to append the String to the return value. But in this case, using StringBuilder matches what you want to do. That's not good for performance because "+" creates new String instance every time it's called.

      public String toString() {
        StringBuilder sb = new StringBuilder("Contents of list: {");

        appendRecursion(sb, 0);
        return sb.toString();
      }
      private void appendRecursion(StringBuilder result, int pos) {
        if (pos != size()) {
          rotate();
          result.append(get().getData()).append(",");
          pos = pos + 1;
          appendRecursion(result, pos);
        }     
      }

edited Feb 18, 2014 at 2:13

user3321373

52 bronze badges

answered Feb 18, 2014 at 1:37

Kunihiko

1118 bronze badges

Collectives™ on Stack Overflow

Recursion through a linked list in Java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related